第四章考虑哥德尔定理及其意义。图灵关心的希尔伯特问题（判决问
题）超越出任何按照公理系统的特殊的数学形式。问题在于，是否存在能在原则上一个接一个地解决所有（属于某种适当定义的族的）数学问题的某种一般的机械步骤？
回答这一问题的部分困难在于决定什么叫做“机械过程”。这概念处于当时正常的数学概念之外。为了掌握它，图灵设想如何才能把“机器”的概念表达出来，它的动作被分解成基本的项目。这一些似乎是清楚的，图灵也把人脑当成在他意义上的“机器”的例子。这样，由人类数学家在解决数学问题时进行的任何活动，都可以被冠以“机械步骤”之名。
虽然这一有关人类思维的观点似乎对于图灵发展他的极重要概念很有价值，我们却绝没有必要去附和它。的确，图灵在把机械过程的含义弄精确时，向我们展示出存在一些完好定义的数学运算，在任何通常的意义上，都不能被称为机械的！图灵本人的这一方面工作现在可间接地为我们提供了他自己有关精神现象性质观点的漏洞。这个事实也许不无讽刺意味。然而，这不是我们此刻所关心的。我们首先要弄清图灵心目中的机械过程究竟是什么。图灵概念我们设想实现某种（可以有限地定义的）计算步骤的一台仪器。这样仪器会采取什么样的一般形式呢？我们必须准备理想化一些，而且不必为实用性过份担心：我们是真正地考虑一台数学上理想化的“机器”。我们要求该仪器具有有限 （虽然也许非常大的）数目的不同可能态的分立集合。
我们把这些称作仪器的内态。但是我们不限制该仪器在原则上要实现的计算的尺度。回顾一下上述的欧几里德算法。在原则上不存在被该算法作用的数的大小的限制。不管这些数有多大，算法或者一般计算步骤都是同样的。对于非常大的数，该步骤的确要用非常长的时间，而且需要在数量可观的“粗纸”上面进行实际的计算。但是不管这些数有多大，该算法是指令的同一有限集合。这样，虽然我们仪器只有有限个内态，它却能够处理大小不受限制的输入。 此外， 为了计算应允许该仪器召来无限的外存空间 （我们的 “粗纸”）；而且能够产生大小不受限制的输出。由于该仪器只有有限数目的不同的内态，不能指望它把所有外部数据和所有自己计算的结果“内化”。相反地，它必须只考察那些立即处理的数据部分或者早先的计算，然后进行需要对它们进行的任何运算。也许可在外存空间把那个运算的相关结果记下来，然后以一种精确决定的方式进行下一个阶段的运算。正是输入、计算空间和输出的无限性质告诉我们，我们正在考虑的仅仅是一种数学的理想化，而不是在实际上可真正建造的某种东西（见图2.1）。但这是极其关键的理想化。对于大多数实用目的而言，当代电脑技术的奇迹为我们提供了无限的电子存储仪器。
事实上，在上述讨论中称为“外部的”存储空间的类型，可实际上被认为是现代电脑的内部工作的一部分。存储空间的某一确定部分是否被当作内部的或外部的， 也许只是术语的问题。 按照硬件和软件是划分 “仪器”和“外部”的一种方法。内部可当成硬体，而外部为软体。我将不必拘泥于此，但是不管从那个角度看，当代电子电脑是图灵的理想化的极好近似。图2.1一台严格的图灵机需要无限的磁带图灵是按照在上面作记号的 “磁带”来描述其外部数据和存储空间的。一旦需要，仪器就会把该磁带召来“阅读”，而且作为其运算的一部分，磁带可前后移动。仪器可把记号放到需要的地方，可抹去旧的记号，允许同一磁带像外存（也就是“粗纸”）以及输入那样动作。因为在许多运算中，一个计算的中间结果起的作用正如同新的数据，所以事实上在“外存”和“输入”之间不做任何清楚的区分也许是有益的。我们记得在欧几里德算法中，不断地用计算不同阶段的结果去取代原先的输入（数A和B）。
类似地，这同一磁带可被用作最后输出（也就是“答案”）。只要必须进行进一步的计算，该磁带就会穿过该仪器而不断地前后移动。当计算被最后完成时，仪器就停止，而计算的答案会在停于仪器一边的磁带的部分上显示出来。为了确定起见，我们假定，答案总是在左边显示，而输入的所有数据以及要解的问题的详细说明总是由右边进去。
让我们有限的仪器前后移动一条潜在地无穷长的磁带，我自己觉得有点不舒服。不管其材料是多么轻，移动无限长的磁带是非常困难的！相反地，我宁愿把磁带设想成代表某一外部环境，我们有限的仪器可以通过这环境进行移动。（当然用现代电子学，既不需要“磁带”也不需要“仪器”作实际的、在通常物理意义上的“运动”，但是这种“运动”是一种描述事体的便利方法。）依此观点，该仪器完全是从这个环境接受它的输入。它把环境当成它的“粗纸”。最后将其输出在这同一个环境中写出。
在图灵的描述中，“磁带”是由方格的线性序列所组成，该序列在两个方向上都是无限的。在磁带的每一方格中或者是空白的或者包含有一个单独的记号①。我们可利用有记号或者没有记号的方格来阐释，我们的环境（也就是磁带）可允许被细分并按照分立（和连续相反的）元素来描述。如果希望仪器以一种可靠并绝对确定的方式工作。这似乎是合情理的要做的事。然而，我们允许该“环境”是（潜在地）无限的，把这作为我们使用的数学理想化的特征。但是，在任何特殊的情形下，输入、计算和输出必须总是有限的。这样，虽然可以取无限长的磁带，但是在它上面只应该有有限数目的实在的记号。磁带在每一个方向的一定点以外必须是空白的。我们用符号“0”来表示空白方格，用符号“1”来代表记号方格，例如：0 0 0 1 1 1 1 0 1 0 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 0 0我们要求该仪器“读”此磁带，并假定它在一个时刻读一个方格，在每一步运算后向右或向左移动一个方格。这里没有损失任何涉及到的一般性。
可以容易地由另一台一次只读和移动一个方格的仪器去仿照一台一次可读n个方格或者一次可移动k个方格的仪器。 k方格的移动可由一个方格的k次移动来积累，而存储一个方格上的n种记号的行为正和一次读n个方格一样。这样的一台仪器在细节上可做什么呢？什么是我们描述成“机械的”
东西作用的最一般方式呢？我们记得该仪器的内态在数目上是有限的。除了这种有限性之外，我们所需要知道的一切是该仪器的行为完全被其内态① 事实上，图灵在他原先的描述中允许磁带有更复杂的记号，但这并没有什么本质上的差别。更复杂的记号总能被细分成记号和空白的序列。我将随意地对他原先的详细说明作各种不重要的变通。和输入所确定。我们已把输入简化成只是两个符号“0”或“1”之中的一个。仪器的初态和这一输入一给定，它就完全确定地运行；它把自己的内态改变成某种其他（或可能是同样的）内态，它用同样的或不同的符号0或1来取代它刚读过的0或1；它向右或向左移动一个方格；最后它决定是继续还是终止计算并停机。为了以明白的方式定义该仪器的运算，我们首先，譬如讲用标号0， 1，2，3，4，5，……，来为不同的内态编号；那么，用一张显明的代换表可以完全指定该仪器或图灵机的运行，譬如：
00→00R01→131L10→651R11→10R20→01R STOP21→661L30→370R 2100→31 2580→00R.STOP2590→971R2591→00R.STOP箭头左边的大写的数字是仪器在阅读过程中磁带上的符号，仪器用右边中间的大写的数字来取代之。R告诉我们仪器要向右移动一个方格，而L告诉我们它要向左移动一个方格。（如果，正如图灵原先描述的那样，我们认为磁带而不是仪器在移动，那么我们必须将R解释成把磁带向左移动一个方格，而L为向右移动一个方格。）词STOP表示计算已经完成而且机器就要停止。特别是，第二条指令01→131L告诉我们，如果仪器内态为0而在磁带上读到1，则它应改变到内态13，不改变磁带上的1，并沿着磁带向左移一格。最后一条指令2591→00R.STOP告诉我们，如果仪器处于态259而且在磁带上读到1，那么它应被改变为态0，在磁带上抹去1而产生0，沿着磁带向右移一格，然后终止计算。
如果我们只用由0到1构成的符号，而不用数字0，1， 2，3，4， 5……
来为内态编号的话，则就和上述磁带上记号的表示更一致。如果我们有选择的话，可简单地用一串n个1来标号态n，但这是低效率的。相反地，我们使用现在人们很熟悉的二进位记数系统：0→0，1→1，2→10，3→11，4→100，5→101，6→110，7→111，8→1000，9→1001，10→1010，11→1011，12→1100，等等正如在标准的（十进位）记数中一样，这里最右边的数字代表“个位”，但是紧在它前面的位数代表“二”而不是“十”。再前面的位数代表“四”
而不是“百”，更前面的是“八”而不是“千”等等。随着我们向左移动，每一接续的位数的值为接续的二的幂：1，2，4（=2×2），8（=2×2×2），16（=2×2×2×2），32（=2×2×2×2×2）等等。 （为了将来的其他目的，我们有时发现用二和十以外的基来表示自然数是有助的：例如基数为三，则十进位数64就可被写成2101，现在每一位数都为三的幂：64=（2×33）
