图灵机

图灵机是中央处理器的一般例子，其控制由计算机完成的所有数据操作，规范机器使用顺序存储器来存储数据。更具体地说，它是一台机器（自动机），能够枚举字母表中有效字符串的任意子集；这些字符串是递归枚举集的一部分。图灵机有一个无限长的磁带，可以在上面执行读写操作。

假设有一个黑盒，图灵机无法知道它最终是否会用给定的程序枚举子集的任何一个特定字符串。这是因为停机问题是不可解决的，这对于计算的理论极限有着重要的影响。

图灵机能够处理不受限制的语法，这进一步意味着它能够以无限多的方式鲁棒地评估一阶逻辑。众所周知，这一点通过λ演算得到了证明。

能够模拟任何其他图灵机的图灵机被称为通用图灵机（UTM，或者简称为通用机器）。阿隆佐·邱奇引入了一个更倾向于数学的定义，具有类似的“普遍”性质，他在λ微积分方面的工作，与图灵的一种被称为丘奇-图灵命题的形式计算理论中的工作紧密相关。论文指出图灵机确实掌握了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械过程”的精确定义。研究它们的抽象属性可以使我们对计算机科学和复杂性理论有更多的见解。

1.1 物理描述

图灵在1948年的论文《智能机器》中写道，他的机器包括：

……以无限的磁带的形式获得，磁带被标记成正方形，每个正方形上都可以打印一个符号。任何时候，机器中都有一个符号；它被称为扫描符号。机器可以改变扫描的符号，其行为部分由该符号决定，但是磁带上其他地方的符号不会影响机器的行为。然而，磁带可以在机器中来回移动，这是机器的基本操作之一。因此，磁带上的任何符号最终都可能有一局。      ^[17] （图灵1948，第3页      ^[18]）

图灵机用数学方法模拟了一台在磁带上机械运转的机器。在这盘磁带上有符号，机器可以用磁头一次读写一个符号。操作完全由一组有限的基本指令决定，例如“在状态42，如果看到的符号是0，写1；如果看到的符号是1，则变为状态17；在状态17中，如果看到的符号是0，则写1，并转换到状态6等等。在最初的文章中（《关于可计算的数字，应用于决策问题》，也可见下文），图灵想象的不是一个机制，而是一个他称之为“计算机”的人，他盲目地（或者正如图灵所说，“以一种杂乱无章的方式”）执行这些确定性的机械规则。

更准确地说，图灵机包括：

• 分成一个接一个单元的带子。每个单元格包含某个有限字母表中的一个符号。字母表包含一个特殊的空白符号（这里写为“0”）和一个或多个其他符号。假设磁带可以任意向左和向右扩展，即图灵机总是提供计算所需的磁带。以前未被写入的单元格被假定为用空白符号填充。在某些模型中，磁带的左端标有特殊符号；胶带向右延伸或无限延伸。
• 一种磁头，可以在磁带上读写符号，一次能左右移动磁带上的一个单元格（而且只能移动一个单元格）。在某些模型中，磁头可以移动，磁带是固定的。
• 一种存储图灵机状态的状态寄存器，是有限状态中的一种。其中包括初始化状态寄存器的特殊起始状态。图灵写道，这些状态取代了进行计算的人通常所处的“精神状态”。
• 指令的有限表^{[19] [20]} 给出了机器当前所处的状态（qi）和它在磁带上读取的符号（aj）（符号当前位于磁头下方），告诉机器按顺序执行以下操作（对于5元组模型）：

1. 擦除或写入符号（用a_j1替换a_j）。
2. 移动磁头（用dk描述，可以有值：““L”表示左移一步，“R”表示右移一步，“N”表示停留在同一位置）。
3. 假设与规定的相同或新的状态（转到状态q_i1）。

在4元组模型中，擦除或写入符号（aj1）和向左或向右移动磁头（dk）被指定为单独的指令。具体来说，该表告诉机器（1a）擦除或写入符号或（1b）向左或向右移动磁头，然后（ii）按照规定假设相同或新的状态，但不能在同一指令中同时采取动作（1a）和（1b）。在某些模型中，如果表中没有当前符号和状态组合的条目，则机器将停止运行；其他模型要求填写所有条目。

请注意，机器的每个部分（即其状态、符号集合和任何给定时间使用的磁带）及其动作（如打印、擦除和磁带运动）都是有限的、离散的和可区分的；正是无限量的磁带和运行时给了它无限量的存储空间。

跟据霍普克罗夫特和乌尔曼（1979，p . 148），图灵机（单磁带）可以正式定义为7元组    其中：

•     是一个有限的非空状态集；
•     是一组有限的、非空的磁带字母表符号；
•     是 空白符号 （在计算过程中的任何步骤中，唯一允许在磁带上无限频繁出现的符号）；
•     是一组输入符号，即允许在初始磁带内容中出现的符号集；
•    为初始状态；
•     是一组最终状态或接受状态。如果初始磁带内容最终停止在    的状态，则说它被    接受。
•     是一个名为转换函数的部分函数，其中L是左移，R是右移。（相对不常见的变体允许“不移位”，称为N，是后者集合的第三个元素。）如果     未在当前状态和当前磁带符号上定义，则机器停止；^[21]

任何按照这些规格操作的东西都是图灵机。

三态繁忙海狸的7元组如下所示（参见图灵机示例中关于繁忙海狸的更多信息）：

•     （状态）；
•     （磁带字母表符号）；
•     （空白符号）；
•     （输入符号）；
•     （初始状态）；
•     （最终状态）；
•     参见下面的状态表（转换函数）。

最初，所有磁带单元都用   标记。

用van Emde Boas （1990）的话来说，第6页：“集合理论对象[他的与上面类似的七元组描述]只提供了关于机器如何运行以及计算结果的部分信息。”

例如，

• 需要对这些符号的实际外观做出许多决定，并且需要一种万无一失的方式来无止境地读写符号。
• 左移和右移操作可以使磁带头在磁带上移动，但是当实际构建图灵机时，更实际的做法是让磁带在磁头下来回滑动。
• 磁带可以是有限的，并且根据需要用空白自动扩展（这最接近数学定义），但是更常见的是将它想象成在一端或两端无限扩展，并且预先填充空白，除非磁头位于明确给定的有限片段上。（当然，这在实践中是不可行的。）磁带的长度不能固定，因为这不符合给定的定义，并且会严重限制机器可以执行的计算范围，使其局限于线性有界自动机。

4.1 替代定义

文献中的定义有时略有不同，以使论点或证明更容易或更清楚，但这总是以最终的机器具有相同的计算能力的方式完成。例如，集合可以从    更改为   ，其中 N （“无”或“无操作”）将允许机器停留在同一磁带单元上，而不是向左或向右移动。这不会增加机器的计算能力。

根据图灵/戴维斯（图灵，1936年）的惯例，最常见的是用九个五元组中的一个来表示“图灵表”中的每个“图灵指令” （《不可判定》第126-127页和戴维斯（2000年） 152页）：

（定义1）： (q_i, S_j, S_k/E/N, L/R/N, q_m)  

（当前状态q _i ，符号扫描S _j ，打印符号S _k/擦除E/none N，移动_tape_one_square左/右R/none N，新状态q _m ）

其他作者（明斯基（1967） 119页，Hopcroft和Ullman （1979）第158页， 斯通（1972）第9页）采用不同的约定，新的状态q_m 在扫描符号后立即列出_j以下内容：

（定义2）： （q _i，S _j，q _m，S _k/东/北，左/右/北）

（当前状态q _i ，符号扫描 _j ，新状态q _m ，打印符号 _k/擦除E/none N，移动_tape_one_square左/右R/none N）

在本文的剩余部分，将使用“定义1”（图灵/戴维斯公约）。

在下表中，图灵的原始模型只允许他称之为N1、N2、N3的前三行（参见《图灵在不可判定中》，第126页）。他允许通过命名第0个符号S0 = "擦除"或"空白"等来擦除"扫描方块"。然而，他不允许非打印，所以每条指令行都包括“打印符号Sk”或“擦除”（参见《footnote 12 in Post》（1947），《不可判定》第300页）。缩写是图灵的（《不可判定》，第119页）。继图灵1936-1937年的原始论文之后，机器模型允许所有九种可能的五元组类型：

任何图灵表（指令列表）都可以由上述九个5元组构成。出于技术原因，通常可以省去三个非打印或“N”指令（4、5、6）。有关示例，请参见图灵机示例。

较少遇到使用4元组的情况：它们代表图灵指令的进一步原子化（Post（1947）、Boolos & Jeffrey（1974、1999）、Davis-Sigal-Weyuker（1994））；也可以参见图灵机（Post–Turing machine）。

4.2 “状态”

图灵机上下文中使用的“状态”这个词可能会引起混淆，因为它有两个意思。图灵之后的大多数评论者都使用“状态”来表示要执行的当前指令的名称/指示符——即状态寄存器的内容。但是图灵（1936）通过计算（整个系统的当前状态），在他所说的机器的“m配置”记录和机器（或人）的“进展状态”记录之间做了很大的区分。图灵所说的“状态公式”包括当前指令和磁带上的所有符号：

因此，计算在任何阶段的进展状态完全由磁带上的说明和符号决定。也就是说，系统的状态可以用一个表达式（符号序列）来描述，该表达式由磁带上的符号后跟Δ（我们认为Δ不会出现在其他地方）组成，然后是指令的注释。这个表达式叫做“状态公式”。

——《不可判定》第139-140页，强调部分增加

早些时候，图灵在他的论文中更进一步阐述了这点：他举了一个例子，在扫描方块下放置了当前“m-配置”的符号——指令的标签——以及磁带上的所有符号（《不可判定》，第121页）；他称之为“完整的配置”（《不可判定》，第118页）。为了在一行上打印“完整配置”，他将状态标签/m配置放在扫描符号的左侧。

这方面的一个变体出现在1952年，克莱尼展示了如何写机器“状况”的哥德尔数：他将“m配置”符号q4放在被扫描的方块上，大致位于磁带上6个非空白方块的中心（参见本文图灵-磁带图），并将其放在被扫描方块的右侧。但是克莱尼把“q4”本身称为“机器状态”（Kleene，第374-375页）。霍普克罗夫特和乌尔曼称这种组合为“瞬时描述”，并遵循图灵惯例，将“当前状态”（指令标签，m配置）放在扫描符号的左侧（第149页）。

示例：3次“移动”后，3状态2符号繁忙河狸的总状态（取自下图中的示例“运行”）

1 A1

这意味着：移动了三次之后，磁带……000110000……在它上面，磁头正在扫描最右边的1，状态为a。空白（在本例中用“0”表示）可以是总状态的一部分，如下所示：B01；磁带上只有一个1，但磁头正在扫描左边的0（“空白”），状态为b。

图灵机上下文中的“状态”应明确描述的是：（1）当前指令，或（2）磁带上的符号列表和当前指令，或（3）磁带上的符号列表和放置在扫描符号左侧或右侧的当前指令。

图灵的传记作者安德鲁·霍奇斯（Andrew Hodges，1983： 107）已经注意到并讨论了这种矛盾。

4.3 图灵机“状态”图

右边：上表表示为“状态转换”图。

较大的表通常最好作为表（Booth，第74页）。它们更容易被计算机以表格形式模拟（Booth，第74页）。然而，某些概念——例如具有“复位”状态的机器和具有重复模式的机器（参见Hill and Peterson，第244页及以下）——在被视为图时更容易被看到。

图是否代表对其表格的改进，必须由读者在特定上下文中决定。有关详细信息，请参见有限状态机。

读者应该再次注意，这些图表代表了他们的表在时间上冻结的快照，而不是计算在时间和空间上的过程（“轨迹”）。尽管每次繁忙的海狸机器“运行”时，它总是遵循相同的状态轨迹，但对于可以提供可变输入“参数”的“复制”机器来说，情况并非如此。

“计算进度”图表显示了三态繁忙海狸从开始到结束的计算的“状态”（指令）进度。最右边是图灵在每一步的“完整配置”（克莱尼的“情况”，霍普克罗夫特-乌尔曼的“即时描述”）。如果机器被停止并清除为空白的 “状态寄存器”和整个磁带，这些“配置”可以用于在计算过程中的任何地方重新启动计算（参见图灵（1936）《不可判定》，第139-140页）。

许多可能被认为比简单的通用图灵机有更多计算能力的机器可以证明没有更多的能力（Hopcroft and Ullman，第159页，cf. Minsky（1967））。他们可能计算得更快，或者使用更少的内存，或者他们的指令集可能更小，但是他们不能更强有力地计算（即更多的数学上的功能）。（回想一下，丘奇-图灵论文假设这对于任何类型的机器都是正确的：任何可以“计算”的东西都可以被某个图灵机器计算出来。）

图灵机相当于单栈下推自动机（PDA），通过放宽栈的后进先出要求，它变得更加灵活和简洁。此外，图灵机也相当于具有标准后进先出语义的双栈下推自动机，使用一个堆栈对图灵机的右侧建模，另一个堆栈对左侧建模。

在其他极端条件下，一些非常简单的模型被证明是图灵等效的，即具有与图灵机模型相同的计算能力。

常见的等效模型是多磁带图灵机、多磁道图灵机、具有输入和输出的机器，以及与确定性图灵机（DTM）相对的非确定性图灵机（NDTM），而确定性图灵机（DTM）的动作表对于符号和状态的每个组合最多有一个条目。

只读、向右移动的图灵机等价于非确定有限状态自动机（NFAs）（以及通过使用NDFA到非确定有限状态自动机转换算法进行转换的确定有限状态自动机）。

出于实际和教学目的，等效的寄存器机器可以用作普通的汇编编程语言。

一个有趣的问题是，由具体编程语言表示的计算模型是否等价于图灵。虽然真实计算机的计算基于有限状态，因此不能模拟图灵机，但编程语言本身不一定有这种限制。Kirner等人2009年的研究表明，在通用编程语言中，一些是图灵完备的，而另一些不是。例如，ANSI C并不图灵等价，因为ANSI C的所有实例化（不同的实例化是可能的，因为标准故意让某些行为因遗留原因而未定义）意味着有限空间内存。这是因为内存引用数据类型的大小在语言内部是可访问的。然而，像Pascal 这样的其他编程语言没有这个特性，这使得它们在原则上是图灵完备的。这只是原则上的图灵完备，因为编程语言中的内存分配是允许失败的，这意味着当忽略失败的内存分配时，编程语言可以是图灵完备的，但是在真实计算机上可执行的编译程序不可能是图灵完备的。

图灵早在他的论文（1936）中，就对就对“自动机器”（ 它的“运动”……完全由“配置”决定）和“选择机器”进行了区分：

……其运动仅部分由配置决定……当这种机器达到这些模糊的配置之一时，它不能继续运行，直到外部操作者做出一些任意的选择。如果我们用机器来处理公理系统，就会出现这种情况。

——《不可判定》，第118页

图灵（1936）除了在脚注中描述了如何使用a机“找到[希尔伯特]微积分的所有可证明公式”，而不是使用选择机器之外，没有做进一步的阐述。他“假设选择总是在两种可能性0和1之间。每个证明将由一系列选择i₁、i₂，...，i_n （i₁ = 0或1，i₂ = 0或1，...i_n = 0或1）决定，因此是2ⁿ + i₁2^n-1 + i₂2^n-2 +...+i_n 完全决定了证明。自动机依次执行证明1、证明2、证明3、……”（《不可判定》第138页的脚注）。

这确实是一种技术，通过这种技术，图灵机可以用来模拟非确定性图灵机的动作；图灵在脚注中解决了这个问题，并且似乎不再深究。

预言机或o机是一种图灵a机，它将计算暂停在“o”状态，而为了完成计算，它“等待”谕示（“除了说它不能是一台机器”的一个未指明的实体）的“决定”（Turing（1939）《不可判定》第166-168页）。

正如图灵在第128页的《不可判定》中所写的那样(斜体是附加的):

发明一台可以用来计算任何可计算序列的机器是可能的。如果给这台机器提供了磁带，磁带的开头写着由一些计算机M的分号分隔的五元组串，那么U将计算出与M相同的序列。

这一发现现在被认为是理所当然的，但在当时（1936年），它被认为是一个惊人的发现。图灵称其为“通用机器”的计算模型——简称“U”——被一些人（参见戴维斯（2000））认为其导致存储程序计算机概念的基本理论突破。

图灵的论文...本质上包含了现代计算机的发明和伴随它而来的一些编程技术。

——Minsky (1967)，第104页

就计算复杂性而言，多磁带通用图灵机只需要比它模拟的机器慢对数因子。这个结果是在1966年由亨利和斯特恩斯获得的。（阿罗拉和巴拉克，2009，定理1.9）

人们常说图灵机不同于更简单的自动机，它和真实的机器一样强大，能够执行真实程序所能执行的任何操作。在这个陈述中被忽略的是，因为一个真实的机器只能有有限数量的配置，这个“真实的机器”实际上只不过是一个线性有界自动机。另一方面，图灵机相当于拥有无限计算存储空间的机器。然而，图灵机不是用来模拟计算机的，而是用来模拟计算本身的。从历史上看，只在（固定的）内部存储器上计算的计算机是后来才发展起来的。

有许多方法可以解释图灵机为什么是真实计算机的有用模型：

1. 真正的计算机可以计算的任何东西，图灵机也可以计算。例如：“图灵机可以模拟编程语言中的任何类型的子程序，包括递归过程和任何已知的参数传递机制”（霍普克罗夫特和乌尔曼第157页）。一个足够大的FSA 也可以模拟任何真正的计算机，不考虑输入输出。因此，关于图灵机局限性的陈述也将适用于真实的计算机。
2. 区别仅在于图灵机处理无限量数据的能力。然而，给定有限的时间，图灵机（像真正的机器）只能处理有限的数据量。
3. 像图灵机一样，真正的机器可以根据需要通过获取更多的磁盘或其他存储介质来扩大其存储空间。
4. 使用更简单的抽象模型对真实机器程序的描述通常比使用图灵机的描述复杂得多。例如，描述一个算法的图灵机可能有几百个状态，而给定真实机器上的等价确定性有限自动机有数万亿个状态。这使得DFA表示无法分析。
5. 图灵机描述的算法与它们使用的内存无关。任何当前机器拥有的内存都有一个限制，但是这个限制可以随时间任意增加。图灵机允许我们对（理论上）将永远有效算法进行陈述，而不管传统计算机体系结构的进展如何。
6. 图灵机简化了算法的陈述。运行在图灵等价抽象机器上的算法通常比运行在真实机器上的算法更通用，因为它们具有任意精度的可用数据类型，并且从不需要处理意外情况（包括但不限于内存不足）。

8.1 图灵机的局限性

计算复杂性理论

图灵机的一个局限是它们不能很好地模拟特定排列的强度。例如，现代存储程序计算机实际上是一种更具体形式的抽象机器的实例，称为随机存取存储程序机器或RASP机器模型。像通用图灵机一样，RASP将其“程序”存储在其有限状态机“指令”之外的“存储器”中。与通用图灵机不同，RASP有无限数量的可区分的、编号的但无限制的“寄存器”——可以包含任何整数的记忆“单元”（参见埃尔戈特和罗宾逊（1964）、哈特曼尼斯（1971），特别是库克-雷乔（1973）；引用自随机存取机器）。RASP的有限状态机具备间接寻址能力（例如，一个寄存器的内容可以用作指定另一个寄存器的地址）；因此RASP的“程序”可以处理寄存器序列中的任何寄存器。这种区别的结果是可以实现基于内存索引的计算优化，这在一般图灵机中是不可能的；因此，当图灵机被用作限定运行时间的基础时，在某些算法的运行时间上可以证明“错误的下限”（由于图灵机的错误简化假设）。这方面的一个例子是二进制搜索，当使用RASP计算模型而不是图灵机模型时，这种算法可以表现得更快。

并发

图灵机的另一个局限性是它们不能很好地模拟并发。例如，整数的大小有一个界限，可以由总是停止不确定的图灵机从空白磁带开始来计算。（参见关于无界非确定性的文章。）相比之下，总有一些没有输入的暂停并发系统能够计算出一个无界大小的整数。（可以使用本地存储创建一个进程，该本地存储用计数0初始化，同时向自身发送停止和开始消息。当它接收到go消息时，它将计数增加1，并向自己发送go消息。当它接收到停止消息时，它会在其本地存储中以无界数字停止。）

互动

在计算的早期，计算机的使用通常限于批处理，即非交互式任务，每个任务从给定的输入数据产生输出数据。可计算性理论反映了这一实践，该理论研究从输入到输出的函数的可计算性，图灵机就是为此而发明的。

自20世纪70年代以来，计算机的交互使用变得更加普遍。原则上，可以通过让外部代理从磁带中读取数据并在图灵机的同时向磁带中写入数据来对此进行建模，但这很少与交互实际发生的方式相匹配；因此，在描述交互性时，通常首选诸如输入/输出自动机这样的替代方法。

艾伦·图灵在1936年描述了它们。

9.1 历史背景：计算机器

罗宾·甘迪（1919-1995）——艾伦·图灵（1912-1954）的学生，也是他一生的朋友的——将“计算机器”的概念追溯到查尔斯·巴贝奇（大约1834年），并实际上提出了“巴贝奇的论文”：

分析的整个开发和操作现在都能够由机器来执行。

——甘迪引用的《Babbage》，斜体，第54页)

甘迪对Babbage分析引擎的分析描述了以下五种操作（参见第52-53页）：

1. 算术函数+，−, ×，其中，如果y ≥ x，则-表示“正确”减法x- y = 0。
2. 任何操作序列都是一个操作。
3. 操作的迭代（重复n次操作）。
4. 条件迭代（以测试测试的“成功”为条件，重复n次操作）。
5. 条件转移（即条件“转到”）。

甘迪指出，“可以由（1）、（2）和（4）计算的函数正是图灵可计算的那些函数。”（p.53）。他引用了其他关于“通用计算机器”的建议，包括珀西·路德盖特（1909）、莱昂纳多·托雷斯·奎韦多（1914）、莫里斯·德·奥坎尼（1922）、路易·库菲格纳（1933）、万尼瓦尔·布什（1936）、霍华德·艾肯（1937）的建议。然而：

…重点是对一系列固定的算术运算进行编程。条件迭代和条件转移对于一般计算机器理论的根本重要性还没有被认识到...

——Gandy，第55页

9.2 恩茨基敦问题（“决策问题”）：希尔伯特1900年的第十个问题

关于著名数学家戴维·希尔伯特在1900年提出的希尔伯特问题，问题10的一个方面在它被精确地确定之前已经流传了将近30年。希尔伯特对#10的最初表述如下：

10.丢番图方程可解性的确定。给定一个具有任意数量未知量和有理积分系数的丢番图方程:设计一个过程，根据这个过程可以在有限次数的运算中确定方程在有理整数中是否是可解的。当我们知道一个允许任何给定逻辑表达式通过有限的多次运算来决定其有效性或可满足性的过程时，就解决了恩茨基敦问题[一阶逻辑的决策问题]... 数理逻辑的主要问题是恩茨基敦问题。

——2008年，在德绍维茨和古列维奇的译本和德语原文中被引用

到1922年，“恩茨基敦问题”的概念有所发展，H. Behmann说：

...需要一个相当明确的普遍适用的指示，它将允许一个人在有限的步骤中判定一个给定的纯逻辑断言的真假...

——Gandy第57页，引用贝曼的话

贝曼说...一般问题相当于决定哪些数学命题是正确的问题。

——同上

如果一个人能够解决恩茨基敦问题，那么他就会有一个“解决许多(甚至所有)数学问题的程序”。

——同上，第92页

到1928年国际数学家大会时，希尔伯特“使他的问题相当精确”。首先，是数学完备...第二，是数学一致...第三，是数学判定”（霍奇斯第91页，霍金第1121页）。1930年，在希尔伯特发表退休演说的同一次会议上，库尔特·哥德尔回答了前两个问题（这让希尔伯特非常懊恼）；第三个问题——恩茨基敦问题——必须等到20世纪30年代中期。

问题是，答案首先需要“明确的普遍适用的指示”的精确定义，普林斯顿大学的阿隆佐·邱奇教授称之为“有效的可计算性”，而在1928年并不存在这样的定义。但是在接下来的6-7年里，埃米尔·波斯特发展了他的定义，即对工人从一个房间到另一个房间，在一个指令清单上写上或擦除标记 （波斯特，1936年），丘奇和他的两个学生斯蒂芬·克莱尼和约翰逊利用丘奇的λ演算和哥德尔的递归理论（1934年）也做了一样的事情。丘奇的论文（发表于1936年4月15日）表明恩茨基敦问题确实是“不可判定的”，并且比图灵抢先了将近一年（图灵的论文提交于1936年5月28日，发表于1937年1月）。与此同时，埃米尔·波斯特在1936年秋天提交了一份简短的论文，所以图灵至少比波斯特有优先权。当丘奇引用图灵的论文时，图灵有时间研究丘奇的论文，并添加了附录，在附录中他概述了丘奇的λ演算和他的机器可以计算出相同的函数。

但是丘奇所做的是一些相当不同的事情，在某种意义上更弱。...图灵结构更直接，并从第一原理提供了一个论据，弥补了丘奇演示中的不足。

——Hodges第112页

波斯特只提出了可计算性的定义，并批评了丘奇的“定义”，但没有证明什么。

9.3 艾伦·图灵的机器

1935年春天，图灵作为英国剑桥国王学院的年轻硕士学生接受了挑战；他受到逻辑学家纽曼的演讲的启发，并从这些演讲中了解哥德尔的工作和恩茨基敦问题...纽曼用了“机械”这个词...纽曼在1955年图灵的讣告中写道：

对于“什么是“机械”过程”这个问题图灵返回了典型的答案“机器可以做的事情”，他开始了非常合心意的任务，即分析计算机的一般概念。

——Gandy，第74页

甘迪说：

我想，但不知道，图灵，从他工作的一开始，就以证明恩茨基敦问题的不确定性为目标。他告诉我，1935年夏天，当他躺在格兰切斯特草地时，他想到了论文的“主要想法”。“主要想法”可能是他对计算的分析，或者是他意识到有一个通用的机器，以及证明不可解性的对角论证。

——同上, 第76页

虽然甘迪认为纽曼的上述说法是“误导性的”，但并非所有人都认同这一观点。图灵一生都对机器感兴趣：“艾伦小时候就梦想发明打字机；图灵夫人有一台打字机；他本可以从问问自己称打字机为“机械的”是什么意思开始的（霍奇斯第96页）。在普林斯顿攻读博士学位时，图灵建立了一个布尔逻辑乘法器（见下文）。他的博士论文题为“基于序数的逻辑系统”，包含以下“可计算函数”的定义：

上面说过，“如果一个函数的值可以通过一些纯粹的机械过程找到，那么这个函数是可以有效计算的”。我们可以从字面上理解这句话，理解为一个纯粹的机械过程，一个可以被机器执行的过程。有可能以某种形式给出这些机器结构的数学描述。这些思想的发展导致了作者对可计算函数的定义，以及对可计算性和有效可计算性的识别。证明这三个定义[第三是λ演算]是等价的并不难，尽管有些费力。

——图灵 (1939)在《不可判定》第160页

图灵回到英国后，他最终共同负责破解由被称为“谜”的加密机创造的德国秘密代码；他还参与了自动计算引擎的设计，“[图灵]的自动计算引擎提案实际上是自成一体的，其根源不在于美国发明的离散变量自动电子计算机”，而在于他自己的通用机器”（霍奇斯，第318页）。关于克莱尼（1952）图灵论文命名的起源和性质的争论仍在继续。但是图灵在他的论文用他的计算机器模型做出了证明《论可计算的数字，及其在恩茨基敦问题的应用》（1937）中：

[认为]希尔伯特恩茨基敦问题不可能有解决办法...因此，我提议证明，没有一般的过程来确定函数微积分的给定公式是否是可证明的，也就是说，没有一台机器，只要被提供了这些公式中的任何一个，最终会说U是否是可证明的。

——图灵的论文转载于《不可判定》第145页

图灵的例子（他的第二个证明）：如果一个人要求一个通用程序来告诉我们：“这台机器曾经打印0吗”，这个问题是“不可判定的”。

9.4 1937-1970：“数字计算机”，即“计算机科学”的诞生

1937年，当图灵在普林斯顿攻读博士论文时，他从头开始建造了一个数字（布尔逻辑）乘法器，制造了自己的机电继电器（霍奇斯第138页）。“艾伦的任务是将图灵机的逻辑设计体现在继电器控制的开关网络中……”（霍奇斯第138页）。虽然图灵最初可能只是好奇和试验，但在德国（康拉德·楚泽（1938））和美国（霍华德·艾肯）和乔治·斯蒂比兹（1937），朝着相同方向非常认真地工作正在进行；他们劳动的成果在第二次世界大战中被轴心国和盟军使用（参见霍奇斯第298-299页）。20世纪50年代初至中期，王昊和马文·明斯基将图灵机简化为一种更简单的形式（马丁·戴维斯的后图灵机的前身）；与此同时，欧洲研究人员正在将新型电子计算机简化为一种类似计算机的理论对象，相当于现在所谓的“图灵机”。在20世纪50年代末和60年代初，梅尔扎克和兰贝克（1961）、明斯基（1961）、谢泼德森和斯特吉斯（1961）的巧合的并行发展进一步推进了欧洲的工作，并将图灵机简化为一种更友好的、类似计算机的抽象模型，称为计数器机；埃尔戈和罗宾逊（1964年）、哈特曼尼斯（1971年）、库克和雷克霍（1973年）利用寄存器机和随机存取机模型进一步推进了这项工作——但基本上它们都只是带有类似算术指令集的多磁带图灵机。

9.5 1970年至今：图灵机作为计算模型

今天，计数器、寄存器和随机存取机器以及它们的父辈图灵机仍然是研究计算理论问题的理论家的选择模型。特别是，计算复杂性理论利用图灵机：

根据人们在计算中喜欢操纵的对象(非负整数或字母数字串等数字)，两种模型在基于机器的复杂性理论中占据了主导地位:

离线多轨迹图灵机...，它表示面向字符串的计算的标准模型，还有

库克和里克霍介绍的随机存取机...，它模拟了理想化的冯•诺依曼风格的计算机。

——van•埃姆德•博阿斯(van Emde Boas)1990:4

只有在算法分析的相关领域，这一角色才由内存模型接管。

——van•埃姆德•博阿斯(van Emde Boas)1990:4