对上面图灵机的内态使用这种二进位记号，则原先的指令表便写成：
00→00R0１→1101１R1０→1000001１L1１→1０R10０→0１STOPR10１→1000010１L11０→100101０R 11010010０→11１L 100000010１→0０STOP100000011０→1100001１R100000011１→0０STOP我还在上面把R.STOP简写成STOP，这是由于可以假定L.STOP从来不会发生，以使得计算的最后一步结果，作为答案的部分，总是显示在仪器的左边。现在假定我们的仪器处于由二进位序列1010010代表的特殊内态中，它处于计算的过程中，第43页给出了它的磁带，而且我们利用指令11010010０→11１L；在磁带上被读的特殊位数（这里是位数“０”）由一个更大写的数字指示，符号串的左边表示内态。在由上面（我多多少少是随机造出的）部分地指定的图灵机例子中，读到的“０”会被“1”所取代，而内态变成‘11’，然后仪器向左移动一格：
该仪器现在已准备好读另一个数字，它又是“０”。根据该表，它现在不改变这个“０”，但是其内态由“100101”所取代，而且沿着磁带向右移回一格。现在它读到“１”，而在表的下面某处又有如何进一步取代内态的指令，告诉它是否改变所读到的数，并向那个方向沿着磁带移动。它就用这种方式不断继续下去，直到达到STOP为止，在该处（在它向右再移一格之后）我们可以想象听到一声铃响，警告机器操作员计算完毕。我们将假定机器总是从内态“0”开始，而且在阅读机左边的磁带原先是空白的。所有指令和数据都是在右边输进去。正如早先提到的，被提供的这些信息总是采用０和１的有限串的形式，后面跟的是空白带（也就是０）。当机器达到STOP时，计算的结果就出现在阅读机左边的磁带上。由于我们希望能把数字数据当作输入的一部分，这样就需要有一种描述作为输入部分的通常的数（我这里是说自然数0，1，2，3，4，…）的方法。一种方法可以是简单地利用一串n个1代表数n（尽管这会给我们带来和自然数0相关的困难）：1→1，2→11，3→111，4→1111，5→11111，等等。
这一初等的记数系统（相当非逻辑地）被称作一进位系统。那么符号‘O’可用作不同的数之间的分隔手段。这种把数分隔开的手段是重要的，这是由于许多算法要作用到数的集合，而不仅仅是一个数上面。例如，对于欧几里德算法，我们的仪器要作用到一对数 A和B上面。图灵机可以很容易地写下执行该算法的程序。作为一个练习，某些勤奋的读者也许介意去验证下面的一台图灵机（我将称它为EUC）的显明的描述，当应用到一对由０分隔的一进位数时，的确会执行欧几里德算法：0０→0０R，0１→1１L，1０→10１R，1１→1１L，10０→1010０R，10１→11０R，11０→100０R，11１→11１R，100０→100０R，100１→101０R，101０→111０L，101１→110１L，110０→110０L，110１→1１L，111０→111０L，111１→1000１L，1000０→1001０L，1000１→1000１L，1001０→10０R，1001１→1１L，1010０→0０STOP， 1010１→1010１R。
然而， 任何读者在进行此事之前， 从某种简单得多的东西， 譬如图灵机UN+1开始将更为明智：0０→0０R，0１→1１R，1０→0１STOP，1１→0１R。
它简单地把一加到一个一进位数上。为了检查UN+1刚好做到这点，让我们想象，譬如讲把它应用到代表数4的磁带上去：…０００００１１１１０００００…。
我们使仪器在开始时从某处向左为一些1。它处于内态０并且读到0。根据第一条指令，它仍保留为０，向右移动一格，而且停在内态0上，在它遇到第一个1之前，它不断地这么进行并向右移动。然后第二条指令开始作用：它把1留下来不变并且再向右移动，但是现在处于内态１上。按照第四条指令，它停在内态1上，不改变这些1，一直向右移动，一直达到跟在这些１后面的第一个０为止。第三条指令接着告诉它把那个０改变成１，向右再移一步（记住STOP是表示R，STOP），然后停机。这样，另一个１已经加到这一串１上。正如所要求的，我们例子中的4已经变成了5。作为更费神的练习，人们可以验证，下面所定义的机器UN×2，正如它所希望的，把一个一进位数加倍：0０→0０R，0１→1０R，1０→10１L，1１→1１R，10０→11０R10１→100０R，11０→0１STOP，11１→11１R，100０→101１L，100１→100１R，101０→10１L，101１→101１L。
在EUC的情形、为了得到有关的概念，人们可用一些明显的数对譬如6和8来试验。正如以前一样，阅读机处于态0，并且初始时处在左边，而现在磁带一开始的记号是这样子的：
…０００００００００００１１１１１１０１１１１１１１１０００００…在许多步之后，图灵机停止，我们得到了具有如下记号的磁带：
…００００１１００００００００００００…
而阅读机处于这些非零位数的右边。这样，所需的最大公约数正是所需要的（正确的）2。要完全解释为何EUC（或者UN×2）在实际上完成所预想的，牵涉到许多微妙之处，而且解释本身比机器更复杂，这是电脑程序的通常特征！ （为了完全理解一个算法步骤为何能做到所预想的，牵涉到洞察。“洞察”本身是算法的吗？这是一个对我们以后颇为重要的问题。）我不想在这里为EUC或UN×2提供解释。真正做过检验的读者会发现，为了在所需的方案中把事情表达得更精密一些，我自作主张地对欧几里德算法作了一些不重要的变通。EUC的描述仍然有些复杂，对于11种不同的内态包含有22条基本指令，大部分复杂性是纯粹组织形式的。例如，可以看到在22条指令中，只有三条真正涉及到在磁带上改变记号！（甚至对于UN×2用了12条指令，其中只有一半涉及到改变记号。）数据的二进位码用一进位系统表示大数极端无效率。正如早先描述的，我们将相应地用二进位计数系统。然而，不能直接地把磁带当作二进位数来读。如果这样做的话，就没有办法告知一个数的二进位表示何时结束，以及无限个０的序列是否代表右端开始的空白。我们需要某种终结一个数的二进位描述的记号。此外，我们还经常要输进几个数，正如欧几里德算法需要一对数2那样。问题在于，我们不能把数之间的间隔和作为单独的一个数的二进位表示中的一部分的０或一串０区分开来。此外，我们或许在输入磁带中包括所有种类复杂的指令和数。为了克服这些困难，让我们采用一种我称之为收缩的步骤。按照该步骤，任何一串０或一串１（共有有限个）不是简单地被当作二进位数来读，而是用一串0，1，2，3等来取代。其作法是，第二个序列的每一数字就是在第一个序列中的连续的０之间的１的个数。例如序列０１０００１０１１０１０１０１１０１０００１１１０１０１０１１１１００１１０就可被取代成：我们现在可以把数2，3，4，…当作某种记号或指令来读。让我们把2简单地当作表示两个数之间间隔的“逗号”，而根据我们的愿望，3， 4，5，…可以代表各种有兴趣的指令或记号，诸如“负号”、“加”、“乘”“到具有下面号码的位置”，“递归进行前面的运算如下面数目那么多次”等等。我们现在有了由更高的数分开的各种０和１的串。后者代表写成二进位的通常的数。这样上面可读成（“逗号”为2）：（二进位数１００１）逗号（二进位数11）逗号……。
使用标准的阿拉伯记号“9”，“3”，“4”，“0”来写相应的二进位１００１，１１，１００，０，我们就得到整个序列：9，3，4（指令3）3（指令4）0，特别是，这一步骤给了我们一种简单地利用在结尾处逗号终结描述一个数的手段（并因此把它和在右边的无限长的空白带区分开来）。此外，它还使我们能对以二进位记号写成０和丨的单独序列的自然数的任何有限序列编码。让我们看看在一特定情形下这是怎么进行的。例如，考虑序列5，13，0，1，1，4在二进位记号中这是１０１，１１０１，０，１，１，１００，它可用扩展（也就是和上面收缩相反）的步骤在磁带上编码成…００００１００１０１１０１０１００１０１１００１１０１０１１０１０１１０１０００１１０００…为了直截了当地得到这个码，我们可在原先的二进位数序列上作如下代换：０→０１→１０，→１１０然后在两端加上无限个０。如果我们把它列出，就能更清楚地看出，如何把这个应用到上面的磁带上：００００１００１０１１０１０１００１０１１００１１０１０１１０１０１１０１０００１１０００我将把这种数（的集合）的记号称为扩展二进位记号。（这样，例如13的扩展二进位形式为１０１００１０）关于这种编码还有最后一点必须提及。这只不过是个技巧，但是为了完备起见是需要的3。在自然数的二进位（或十进位）表示中处于表式最左端的0是不“算”的，它通常可被略去，这里有些多余。例如００１１００１０和１１００１０是两个相同的二进位数（而0050和50为相同的十进位数）。这一多余可适合于数0本身，它也可写成000或00。一个空白的空间的确也应该逻辑地表示0！在通常的记号下这会导致巨大的混淆，但是它和上面刚描述的记号可相安无事。这样，在两个逗号之间的0可只写成两个连在一起的逗号（，，），它在磁带上被编码成两对由单独的０隔开的１１：
…００１１０１１００…
这样，上面的六个数的集合也可用二进位记号写成１０１，１１０１，，１，１，１００，而且在磁带上可以扩展的二进位方式编码成…００００１００１０１１０１０１００１０１１０１１０１０１１０１０１１０１０００１１０００… （有一个０已从我们以前的序列中略去）。
现在我们可以考虑让一台图灵机，譬如讲欧几里德算法，把它应用到以扩展二进位记号写出的一对数上。例如，这一对数是我们早先考虑的6，8，不用以前用的…０００００００００００１１１１１１０１１１１１１１１０００００…
而考虑6和8的二进位表示，也就是分别为110和1000。这一对为6，8，在二进位记号也就是１１０，１０００扩展后在磁带上编码成…０００００１０１００１１０１００００１１００００００…
对于这一对特殊的数，并没有比一进位形式更紧凑。然而，譬如说我们取（十进位数）1583169和8610。在二进位记号中它们是１１０００００１０１００００１０００００１，１００００１１０１０００１０，这样，我们在磁带上把这一对编码成…００１０１００００００１００１０００００１００００００１０１１０１０００００１０１００１００００１００１１０…只要用一行就可将其全部写出， 而如果用一进位记号的话， 表示 “1583169，8610”的磁带用这一整本书都写不下。当数用扩展二进位记号表示时，一台执行欧几里德算法的图灵机，如果需要的话，可以简单地把适当的一对在一进位和扩展二进位之间互相翻译的子程序算法接到EUC上去而得到。然而，由于一进位计数系统的无效率仍在“内部”存在，并且在仪器的迟缓以及需要大量的外部“粗纸” （它是磁带的右手部分）方面表现出来，实际上这是极其无效率的。可以给出全部用扩展二进位运算的、更有效率的、欧几里德算法的图灵机，但是它在这里对我们并无特别启发之处。
相反地，为了阐明如何使一台图灵机能对扩展二进位数运算，让我们尝试某种比欧几里德算法简单得多的东西，即是对一个自然数加一的过程。这可由（我称之为XN+1的）图灵机来执行：
0０→0０R，0１→1１R，1０→0０R，1１→10１R，10０→11０L，10１→10１R，11０→0１STOP，11１→100０L，100０→101１L，100１→100１L，101０→110０R，101１→10１R，110１→111１R，111０→11１R，111１→111０R，某些勤奋的读者可把它应用到，譬如讲数167上去，以再次验证这一台图灵机在实际上做到了所预想的。这一个数的二进位表示可由下面的磁带给出：
…００００１００１０００１０１０１０１１０００…
为了把一加到这个二进位数上，我们简单地找到最后的那个0，并把它改成1，然而用0来取代所有跟在后面的1。例如167+1=168在二进位记号下写成１０１００１１１+１=１０１０１０００.这样，我们的“加一”图灵机应把前面的磁带用…００００１００１００１００００１１０００００…来取代，它的确做到了这一点。
我们注意到，甚至这种简单加一的非常基本的运算在用这种记号时都会显得有些复杂，它使用了十五条指令和八种不同的内态！由于在一进位系统中“加一”只是把1的串再延长一个而已，事情当然是简单得多。所以我们的机器UN+1更为基本，这一点也不奇怪。然而，对于非常大的数，由于所需的磁带非同寻常地长，UN+1就会极慢。而用更紧凑的扩展二进位记号运算的更复杂的机器XN+1就会更好。作为旁白，我愿意指出对于扩展二进位比一进位图灵机显得更简单的一个运算，这就是乘二。在这里由0０→0０R，0１→1０R，1０→0１R，1１→10０R，10０→11１R，11０→0１STOP，给出的图灵机XN×2能在扩展的二进位上实现这个运算，而前面描述的相应于一进位的机器UN×2就要复杂得多！
我们从这里得到了，关于图灵机在非常基础水平上可做到的一些事情的概念。正如预料得到的，当进行某些复杂的运算时，它们会变得极为复杂。这种仪器的终极能力是什么呢？让我们在下面讨论这一个问题。撤屈――图灵主题人们一旦对建造简单的图灵机稍有一些熟悉，下面这些事实就很容易使他们感到满意。特殊的图灵机的确能执行各种基本的算术运算，诸如把两个数加到一起，或把它们相乘，或求一个数的到另一个数的方次。显明提供其结果为一对自然数的运算，譬如带有余数的除法，或者其结果为任意大数目的数的有限集合。此外，可以这样地建造图灵机，即预先没有必要指定它要做何种运算，其运算的指令由磁带提供。需要实行的特定运算也许在某一阶段依赖于该机器在某个更早阶段的需要进行的某个计算的结果。（“如果那个计算的结果比某数大，则做这个；否则就做那个。”）
一旦人们理解到，他可制造实现算术或简单的逻辑运算的图灵机，则很容易想象如何使之进行具有算法性质的更复杂的任务。在他们捣弄了好一阵之后，很容易坚信，这类机器的确能实行不管什么样的机械运算！在数学上，可以很合情合理地把机械运算定义为可被这样的一台机器所执行的运算。数学家用名词“算法”以及形容词“可计算的”、“递归的”和“有效的”来表示能由这类理论机器――图灵机实行的机械运算。一个步骤只要是足够清楚并且机械的，则可合理地相信能找到一台执行它的图灵机。
这正是我们（也就是图灵）引进图灵机概念本身的初步讨论的全部要点。
另一方面，人们仍会感到，这些机器的设计不必这么局限。初看起来，只允许仪器在一个时刻读一个二进位位数（０或１），并且一次沿着一个单独的一维磁带只移动一格似乎是限制。为什么不允许大数目或相互联结的阅读机一下子跑过四条或五条甚至一千条分开的磁带呢？为什么不允许０和１的方格的整个平面（或者甚至一个三维的阵列），而坚持只用一维的磁带呢？为什么不允许从某种更复杂的计数系统或字母来的其他符号呢？事实上，虽然这些改变中的一些会对运算的经济性造成一定程度的不同（正如允许用多于一条的磁带一定会是这种情形那样），但是所有这一切都不会对我们在原则上要得到的东西造成丝毫的影响。即使我们在所有这些方面一下子推广该定义，这种归于“算法”的名下（或“计算”、“有效步骤”或“递归运算”）所实现的运算种类刚好和推广以前的完全相同！
我们可以看到，没有必要有多余一条的磁带。只要该仪器需要时总能在给定的磁带不断地找到新的空白。为此，也许必须不断地把数据从磁带的一处往另一处调度。这也许是“低效率的”，但是它不限制在原则上可以得到的极限4。类似地，利用多于一台并行动作的图灵机――这在近年由于和想更接近地仿照人脑试图相关联而变得很时髦――不能在原则上得到任何新东西（虽然在某种情形下可改善动作的速度）。拥有两台分开的、不直接相互联络的仪器并不比两台相互联络的得到更多，而且如果它们联络，则实际上只不过是一台单独的仪器！关于图灵的对于一维磁带的限制能说些什么呢？如果我们认为该磁带代表“环境”，也许宁愿把它当作一个平面或许一个三维空间，而不当作一维磁带。一个平面似乎比一维磁带更接近于一个“流程图”（正如在上面对欧几里德算法运算的描述） 所需要的①。 然而， 在原则上没有困难以 “一维的”形式（也就是利用流程图的通常术语来描述）写出流程图的运行。在二维平面上显示只是为了我们的便利和容易理解，它对原则上能得到的并没造成什么影响。人们总能把一个二维平面上甚至三维空间上的一个记号或对象的地址，直截了当地在一维磁带上编码。（事实上，使用一个二维平面完全等效于用两根磁带。这两根磁带提供为在二维平面上指明一点所需的两个“座标”；正如三根磁带可作为一个三维空间的一点的“座标”
一样。）这一维的编码再次可能为“低效率的”，但是它在原则上不限制我们的目标。尽管所有这一切，我们仍然可心询问，图灵机的概念是否真的和我们希望叫做“机械的”每一逻辑或数学运算相统一。在图灵写他的开创性文章的时候，这一点比今天模糊得多，所以他觉得有必要把情形解释得更清楚一些。图灵的严密论证从以下事实得到了额外的支持，这就是美国逻辑学家阿伦佐?撤屈（在S.C.克利涅的协助下）完全独立地（并实际上稍早一些）提出了一种方案，也是旨在解决希尔伯特的判决问题的拉姆达计算。尽管它不如图灵的那么明显地为一种完全广泛的机械的方案，但在数学结构上的极端经济性方面有些优点。（我将在本章的结尾描述撤屈的杰出的计算。） 还存在其他一些解决希尔伯特问题的和图灵相独立的设想 （见甘迪1988），尤其是波兰――美国逻辑学家爱弥尔?波斯特的设想（比图灵稍晚些，但其思想和图灵比和撤屈更相像许多）。所有这些方案很快就被证明是完全等效的。 这就给现在称作撤屈――图灵主题的观点增加了许多份量，即图灵机（或等效的）概念实际在数学上定义了我们认为是算法（或有效、或递归、或机械的）步骤的东西。现在，高速电脑已变成我们生活中如此熟悉的部分，很少人似乎觉得有必要去问这些主题的原始形式。相反地，已有不少人转去注意真正的物理系统（假定包括人脑）――精确服从物理定律的东西――是否能够实行比图灵机更多、更少或刚好一样多的逻辑和数学运算。我本人是非常喜欢撤屈――图灵主题的原先的数学形式。另一方面，它和实在物理系统的行为的关系是我们以后在本书主要关注的另外一个单独的问题。① 正如这里所描述的，这一流程图本身实际上是“仪器”的一部分，而不是外部环境的“磁带”。我们在磁带上表示的正是实际的数A，B，A-B 等等。然而，我们还要以一个线性的一维形式来表达该仪器的详细指明。正如我们将要看到的，和普适图灵机相关的，在一台特殊仪器的详细指明和对该仪器可能的“资料”
（或“程序”）的详细指明之间有个密切关系。所以，使这两者都处于一维形式是方便的。不同于自然数的数我们在上述的讨论中考虑了自然数的运算，并且注意到了这一显著的事实，即尽管每台图灵机只有固定的有限数目的不同内态，它却可能处理任意大小的自然数。然而，人们经常需要使用比这更复杂的其他种类的数，诸如负数、分数或无理数。图灵机可以容易地处理负数和分数（例如像-
597/26），而且我们可取任意大的分母和分子。我们所要做的全部是对 “-”
和 “/” 作适当的编码。 这可容易地利用早先描述的扩展二进位记号做到 （例如，“3”表示“-”以及“4”表示“/”，它们分别在扩展二进位记号中编码成1110和11110）。人们就是这样地按照自然数的有限集合来处理负数和分数的。这样，就可计算性的一般问题而言，它们没有告诉我们什么新的东西。
类似地，由于长度不受限制的有限小数表式仅仅是分数的特殊情形，它们并没给我们带来什么新问题。例如，无理数π的由3.14159265给出的有限小数近似，简单地就是分数314159265/100000000。然而，无限小数表式，譬如完全无限展开π=3.14159265358979…
出现了一定的困难。严格地讲，无论是图灵机的输入或者输出都不是无限小数。人们也许会想到，我们可以找到一台图灵机，在其输出磁带上产生由π的小数展开的、所有的一个接一个位数3，1，4，1，5，9，…。我们就简单地让机器一直开下去好了。但这对于一台图灵机来讲，是不允许的。我们必须等待机器停了以后（铃声响过！）才允许去检查输出。只要机器还没有到达停止命令，其输出就可能要遭受到改变，所以不能对它信任。另一方面，在它到达停止时，其输出必须是有限的。
然而，存在一种合法地使图灵机以与此非常类似的方法，一个位数跟着另一个位数产生位数的步骤。如果我们希望产生一个数，譬如讲π的无限小数展开，我们可以让一台图灵机作用于0上以产生整数部分了；然后使机器作用到1上，产生第一小数位1；然后使其作用于2上，产生第二小数位4；然后作用于3上，产生1，这样不断地下去。事实上，一定存在在这个意义上产生π的全部小数展开的图灵机，尽管要把它明显地造出来颇费一点周折。类似的评论也适用于许多其他无理数，譬如 2=1.414213562…。然而，正如在下一章将要看到的，人们发现有些无理数（非常引人注目地）根本不能由任何图灵机产生。能以这种方式产生的数叫作可计算的（图灵1937）。那些不能的（实际上是绝大多数！）是叫作不可计算的。我们将在后面的章节中回到这件事体及有关的问题上来。按照物理理论，用可计算的数学结构能否足够地描述实在的物理对象（也就是人脑），是我们要关心的问题。
一般地讲，可计算性是数学中的一个重要问题。人们不应该只将其当成只适合于这类数的事体。人们可有直接作用于诸如代数或三角的数学公式上的图灵机，或可进行微积分的形式运算的图灵机。人们所需的一切是某种准确地把所有涉及的数学符号编码成0和1序列的形式，然后再利用图灵机的概念。这毕竟是图灵在着手解决判决问题时心里所想的，即寻求回答具有一般性质的数学问题的算法步骤。我们将很快地回到这上面来。普适图灵机我还未描述普适图灵机的概念。虽然其细节是复杂的，但是它背后的原则并不十分复杂。它的基本思想是把任意一台图灵机T的指令的表编码成在磁带上表示成0和1的串。然后这段磁带被当作某一台特殊的被称作普适图灵机U的输入的开始部分，接着这台机器正如T所要进行的那样，作用于输入的余下部分。普适图灵机是万有的模仿者。“磁带”的开始部分赋予该普适机器U需要用以准确模拟任何给定机器T的全部信息！
为了了解这是如何进行的，我们首先需要一种给图灵机编号的系统方式。考虑定义某个特殊的，譬如讲在前面描述的图灵机的一个指令表。我们必须按照某种准确的方案把这表编码成0和1的串。我们可借助于以前采用的“收缩”步骤来办到。因为，如果我们用数2，3，4，5和6来分别代表符号R、L、STOP、箭头（→）以及逗点，那么我们就可以用１１０、１１１０、１１１１０、１１１１１０以及１１１１１１０的收缩把它们编码。这样，出现在该表中的这些符号实际的串可以采用分别被编码成０和１０的位数0和１。由于在该图灵机的表中，在二进位计数的结尾大写的数的位置足以把大写的０和１从其他小写的阿拉伯数字中区分开来，所以我们不需要用不同的记号。这样，110１将被读成二进位数1101，而在磁带上被编码成１０１００１０。特别是，0０读作00，它可毫不含糊地被编码成０，或者作为被完全省略的符号。实际上我们可以不必对任何箭头或任何在它紧前头的符号进行编码，而依靠指令的数字顺序去标明哪些符号必须是什么。尽管在采用这个步骤时，在必要之处要提供一些额外的“哑”指令，以保证在这个顺序中没有缝隙。这样的做法具有相当好的经济性。（例如，图灵机XN+1没有告诉我们对110０要做什么的命令，这是因为这条指令在机器运行时从不发生，所以我们应该插入一条“哑”指令，譬如讲110０→0０R，它可合并到表中而不改变任何东西。类似地，我们应该把10１→0０R插入到XN×2中去。）若没有这些“哑的”，表中后面的指令的编码就会被糟蹋了。因为在结尾处的符号L或R足以把一条指令和另一条隔开，所以我们在每一指令中实际不需要逗号。因此，我们采用下面的编码：０表示0或０，１０表示1或１，１１０表示R，１１１０表示L，１１１１０表示stop。作为一个例子，让我们为图灵机XN+1编码 （插入指令110０→0０R）。
在去掉箭头和在它们紧前面的位数以及逗号之后，我们得到0０R 1１R 0０R 10１R 11０L 10１R 0１STOP100０L 101１L 100１L110０R10１R0０R111１R11１R 111０R为了和早先说的相一致，我们可以去掉每一个００，并把每一个01简单地用1来取代，这样得到R1１RR10１R11０L10１R１STOP100０L101１L100１L110０R10１RR111１R11１R111０R如下是在磁带上的相应的码：１１０１０１０１１０１１０１００１０１１０１０１００１１１０１００１０１１０１０１１１１０１００００１１１０１００１０１０１１１０１０００１０１１１０１０１０００１１０１００１０１１０１１０１０１０１０１０１１０１０１０１０１１０１０１０１００１１０我们总是可以把开始的１１０（以及它之前的无限的空白磁带）删去。由于它表示0０R，这代表开头的指令0０→0０R。而我已隐含地把它当作所有图灵机共有的。这样仪器可从磁带记号左边任意远的地方向右跑到第一个记号为止。而且，由于所有图灵机都应该把它们的描述用最后的１１０结束（因为它们所有都用R、L或STOP来结束），所以我们也可把它（以及假想跟在后面的０的无限序列）删去。这可以算作两个小节约。所得到的二进位数是该图灵机的号码，它在XN+1的情况下为：
１０１０１１０１１０１００１０１１０１０１００１１１０１００１０１１０１０１１１１０１００００１１１０１００１０１０１１１０１０００１０１１１０１０１０００１１０１００１０１１０１１０１０１０１０１０１１０１０１０１１０１０１０１００。这一特殊的数在标准十进位记号下为450813704461563958982113775643437908。我们有时不严格地把号码为n的图灵机称为第n台图灵机，并用Tn来表示。这样，XN+1是第450813704461563958982113775643437908台图灵机！我们必须顺着这图灵机的“表”走这么远，才找到一台甚至只进行如此平凡的（在扩展二进位记号上）对自然数加一的运算，这真使人印象深刻！（尽管在我的编码中还可以有很少的改善余地，但我认为自己进行得相当有效率。）实际存在某些更低号码的有趣的图灵机。例如，UN+1的二进位号码为１０１０１１０１０１１１１０１０１０它只是十进位制的177642！这样，只不过是把一个附加的1加到序列1的尾巴上的特别平凡的图灵机UN+1是第177642台图灵机。 为了好奇的原因，我们可以注意在任一种进位制中“乘二”是在图灵机表中这两个号码之间的某处。我们找到XN×2的号码为10389728107，而UN×2的号码为1492923420919872026917547669。
人们从这些号码的大小，也许会毫不奇怪地发现，绝大多数的自然数根本不是可工作的图灵机的号码。现在我们根据这种编号把最先的十三台图灵机列出来：
T0：0０→0０R，0１→0０R，T1：0０→0０R，0１→0０L，T2：0０→0０R，0１→0１R，T3：0０→0０R，0１→0０STOP，T4：0０→0０R，0１→1０R，T5：0０→0０R，0１→0１L，T6：0０→0０R，0１→0０R，1０→0０R，T7：0０→0０R，0１→？？？，T8：0０→0０R，0１→10０R，T9：0０→0０R，0１→1０L，T10：0０→0０R，0１→1１R，T11：0０→0０R，0１→0１STOP，T12：0０→0０R，0１→0０R，1０→0０R。其中，T0简单地就是向右移动并且抹去它所遇到的每一件东西，永不停止并永不往回退。机器T1最终得到同样的效应。但它是以更笨拙的方法，在它抹去磁带上的每个记号后再往后跳回。机器T2也和机器T0一样无限地向右移动，但是它更有礼貌，简单地让磁带上的每一件东西原封不动。由于它们中没有一台会停下，所以没有一台可以合格地被称为图灵机。T3是第一台可敬的机器。它的确是在改变第一个（最左边）的１为０后便谦虚地停止。
T4遭遇了严重的问题。它在磁带上找到第一个１后就进入了一个没有列表的内态，所以它没有下一步要做什么的指令。T8、T9和T10遇到同样的问题。T7的困难甚至更基本。把它编码的０和１的串涉及到五个接续的１的序列：１１０１１１１１０。对于这种序列不存在任何解释，所以只要它在磁带上发现第一个1就被绊住。（我把T7或其他任何机器Tn，它的n的二进位展开包含多于四个１的序列称为不是正确指明的。）机器T5、T6和T12遭遇到和T0、T1和T2类似的问题。它们简单地、无限地、永远不停地跑下去。所有T0、T1、T2、T4、T5、T6、T7、78、T9、T10和T12都是伪品！只有T3和T11是可工作的， 但不是非常有趣的图灵机。 T11甚至比T3更谦虚，它在第一次遇到1时就停止，并且没有改变任何东西！我们应该注意到，在表中还有一个多余。由于T6和T12从未进入内态1，机器T12和T6等同，并在行为上和T0等同。我们既不必为这个多余，也不必为表中的图灵机伪品而烦恼。人们的确可以改善编码以摆脱许多伪品和大大减少重复。所有这些都是以使我们可怜的普适图灵机变得更复杂作为代价。普适图灵机必须把所读到的号码n解码并假装成图灵机Tn。如果我们可以把所有伪品（或者多余量）取走，这还是值得做的。但是，我们很快就会看到，这是不可能的！这样，我们就不触动我们的编码好了。
例如，可方便地把具有…０００１１０１１１００１００００…接续记号的磁带解释成某个数字的二进位表示。我们记得０在两端会无限地继续下去，但是只有有限个１。我还假定１的数目为非零（也就是说至少有一个１）。我们可以选择去读在第一个和最后一个1（包括在内）之中的有限的符号串，在上述的情况是为一自然数的二进位写法１１０１１１００１，它在十进位表示中为441。然而，这一过程只能给我们奇数（其二进位表示以１结尾的数）。而我们要能表示所有的自然数。这样，我们采取移走最后的１的简单方案（这个１仅仅被当作表示这一程序的终止记号），而把余下来的当成二进位数来读5。因此，对于上述的例子，我们有二进位数１１０１１１００，它是十进位的220。这个步骤具有零也用磁带上的记号代表的好处，也就是…００００００１００００００…
我们考虑图灵机Tn对我们从右边提供给它的磁带上（有限的）０和１的串的作用。根据上面给出的方案，可方便地把这串也考虑作某一个数，譬如m的二进位代表。我们假定，机器Tn在进行了一系列的步骤后最终到达停止（即到达STOP）。现在机器在左边产生的二进位数串是该计算的答案。让我们也以同样方式把这当作，譬如是p的二进位代表来读。我们把表达当第n台图灵机作用到m上时产生p的关系写成：Tn(m)=p。
现在，以稍微不同的方式看这一关系。我们把它认为是一种应用于一对数n和m以得到数p的一个特别运算。（这样，若给定两个数n和m，视第n台图灵机对m作用的结果而得出p。）这一特别运算是一个完全算法的步骤。所以它可由一台特殊的图灵机U来执行。也就是说，U作用到一对(n， m)上产生p。 由于机器U必须作用于n和m两者以产生单独结果p，我们需要某种把一对(n，m)编码到一条磁带上的方法。为此，我们可假定n以通常二进位记号写出并紧接着以序列１１１１１０终结。 （我们记得，任一台正确指明的图灵机的二进位数都是仅仅由０，１０，１１０，１１１０和１１１１０组成的序列，因此它不包含比四个１更多的序列。这样，如果Tn是正确指明的机器，则１１１１１０的发生的确表明数n的描述已终结。）按照我们上面的规定，跟着它的每一件东西简单地是代表m的磁带（也就是，紧跟二进位数m的是１０００…）。这样，这第二个部分简单地就是Tn假设要作用的磁带。
作为一个例子，如果我们取n=11和m=6当作U要作用的磁带，其记号序列为…０００１０１１１１１１１０１１０１００００…
这是由以下组成的：…００００（开始的空白带）
１０１１（11的二进位表示）
１１１１１０（终结n）
１１０…（6的二进位表示）
１００００…（余下的磁带）。
在Tn作用到m上的运算的每一接续的步骤，图灵机U要做的是去考察n的表达式中的接续数位的结构，以使得在m的数位（也就是Tn的磁带）上可进行适当的代换。在原则上（虽然在实践中肯定很繁琐）不难看到人们实际如何建造这样的一台机器。它本身的指令表会简单地提供一种，在每一阶段读到被编码到数n中的“表”中，应用到m给出的磁带的位数时，合适元素的手段。肯定在m和n的数位之间要有许多前前后后的进退，其过程会极为缓慢。尽管如此，一定能提供出这台机器的指令表，而我们把它称为普适图灵机。把该机器对一对数n和m的作用表为U(n,m)，我们得到：
U(n,m)=Tn(m)。
这儿Tn是一台正确指明的图灵机6。当首先为U提供数n时，它准确地摸拟第n台图灵机！因为U为一台图灵机，它自身也必须有一号码；也就是说，我们有U=Tu此处号码u待定。u究竟是多少呢？事实上我们可以准确地给出u=7244855335339317577198395039615711237952360672556559631108144796606505059404241090310483613632359365644443458382226883278767626556144692814117715017842551707554085657689753346356942478488597046934725739988582283827795294683460521061169835945938791885546326440925525505820555989451890716537414896033096753020431553625034984529832320651583047664142130708819329717234151056980262734686429921838172157333482823073453713421475059740345184372359593090640024321077342178851492760797597634415123079586396354492269159479654614711345700145048167337562172573464522731054482980784965126988788964569760906634204477989021914437932830019493570963921703904833270882596201301773727202718625919914428275437422351355675134084222299889374410534305471044368695876405178128019437530813870639942772823156425289237514565443899052780793241144826142357286193118332610656122755531810207511085337633806031082361675045635852164214869542347187426437544428790062485827091240422076538754264454133451748566291574299909502623009733738137724162172747723610206786854002893566085696822620141982486216989026091309402985706001743006700868967590344734174127874255812015493663938996905817738591654055356704092821332221631410978710814599786695997045096818419062994436560151454904880922084480034822492077304030431884298993931352668823496621019471619107014619685231928474820344958977095535611070275817487333272966789987984732840981907648512726310017401667873634776058572450369644348979920344899974556624029374876688397514044516657077500605138839916688140725455446652220507242623923792115253181625125363050931728631422004064571305275802307665183351995689139748137504926429605010013651980186945639498（或者至少是这等数量级的其他的可能性）。这个数无疑是极其巨大，但是我似乎没有办法使它变小许多。虽然我的图灵机编码步骤和号码指定是相当合理和简单的，但是在一台实际的普适图灵机的编码中仍然不可避免地导向这么大的一个数7。我曾说过，实际上所有现代通用电脑都是普适图灵机。我并不是说，这种电脑的逻辑设计必须在根本上和我刚刚给出的普适图灵机的描述非常相似。其要点可以简述为，首先为任一台普适图灵机提供一段适当的程序（输入磁带的开始部分）可使它摸拟任何图灵机的行为！在上面的描述中，程序简单地采取单独的数（数n）的形式。但是，其他的步骤也是可能的，图灵原先方案就有许多种变化。事实上，在我自己的描述中，已经有些偏离图灵的原型。但是对于我们当前目的，这些差别中没有一个是重要的。希尔伯特问题的不可解性我们现在回到当初图灵提出其观念的目的，即解决希尔伯特的范围广泛的判决问题：是否存在某种回答属于某一广泛的、但是定义得很好的集合的所有数学问题的机械步骤？图灵发现，他可以把这个问题重述成他的形式，即决定把第n台图灵机作用于数m时实际上是否会停止的问题。该问题被称作停机问题。很容易建造一个指令表使该机器对于任何数m不停。 （例如，正如上面的n=1或2或任何别的在所有地方都没有STOP指令的情形）。也有许多指令表，不管给予什么数它总停（例如n=11）；有些机器对某些数停，但对其他的数不停。人们可以公正地讲，如果一个想象中的算法永远不停地算下去，则并没有什么用处。那根本不够格被称作算法。所以一个重要的问题是，决定Tn应用在m时是否真正地给出答案！如果它不能（也就是该计算不停止），则就把它写成Tn(m)=□。
