113
个编辑
更改
跳到导航
跳到搜索
第7行：
第7行： − + − + − 因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是判定性问题(翻译自德语Entscheidungsproblem, 英文译作decision problem)的不可计算性。+ − + − + − 图灵机是一种中央处理器单元（Central Processing Unit，即CPU），控制着计算机的所有数据操作，规范及其使用顺序内存来存储数据。更具体的，图灵机是一种能够枚举字母表有效字符串的机器（自动机）;这些字符串是字母递归可枚举集的一部分。理想情况下，图灵机有无限长的纸带，其可以在上面执行读写操作。+ − 假设有一个“黑盒子”，图灵机无法知道它最终是否会用给定的程序枚举出子集中的任何一个特定字符串。这是因为停机问题（Halting Problem）是不可解的，停机问题对计算的理论极限有着重大的影响。+ − + − 在1948年的论文《智能机器（Intelligent Machinery）》中，图灵写道他的机器包括: 以无限长纸带的形式获得的无限存储容量，纸带上标有方块，每个方块上可以打印一个符号。在任何时候，机器中都有一个符号，被称为扫描符号。机器可以改变扫描的符号，其行为部分由该符号决定，但纸带上其他地方的符号不会影响机器的行为。然而，纸带可以在机器中来回移动，这是机器的基本操作之一。因此，纸带上的任何符号最终都可能有一个局。+ 第39行：
第39行： − + 第47行：
第47行： − + 第126行：
第126行： − + 第208行：
第208行： − + 第214行：
第214行： − + 第321行：
第321行： − 任何图灵表（指令列表）都可以由上述九个5元组构成。由于技术原因，三个非打印或 "N "指令（4、5、6）通常可以省去。+ 第328行：
第328行： − 因此，任何阶段的计算进度状态完全由指令注释和纸带上的符号决定。也就是说，系统的状态可以由单个表达式（符号序列）来描述，该表达式由纸带上的符号后跟 Δ（我们假设不会出现在其他地方）和指令注释组成。这个表达式被称为“状态公式”。——《The Undecidable》,图灵，p.139–140+ − 更早时期，图灵在他的论文中进行了进一步的研究：他举了一个例子，在该示例中，他把当前 "m-配置 "的符号（指令的标签）和纸带上的所有符号一起放在扫描的方块下面（《The Undecidable》，第121页）；他把这个称为"完整的配置"（《The Undecidable》，第118页）。为了将 "完整配置 "打印在一行，他将状态标签/m-配置放在扫描符号的左边。+ − 在Kleene（1952）中可以看到这样的一个变体，Kleene展示了如何写出一台机器的 "状态"的哥德尔数：他把 "m-配置 "符号q<sub>4</sub>放在磁带上6个非空白方格的大致中心的扫描方格上(见本文图灵-纸带图)，并把它放在扫描方格的右边。但Kleene把 "q<sub>4</sub> "本身称为 "机器状态"（Kleene，第374-375页）。Hopcroft和Ullman把这种组合称为 "瞬时描述"，并遵循图灵规定，把 "当前状态"（指令标签，m-配置）放在扫描符号的左边（第149页）。+ 第338行：
第338行： − + − 图灵机情况中，应阐明 "状态 "是哪种状态。(i)当前指令，或(ii)纸带上的符号列表连同当前指令，或(iii)纸带上的符号列表连同当前指令放在扫描符号的左边或扫描符号的右边。+ 第418行：
第418行： − 图灵机相当于单堆栈下推自动机（Pushdown Automaton，PDA），它通过放宽其栈中的“后进先出”要求，使其更加灵活和简洁。此外，通过使用一个堆栈对读写头左侧的纸带进行建模，使用另一个堆栈对读写头右侧的磁带进行建模，图灵机也等效于具有标准“后进先出”语义的双堆栈PDA。+ − 常见的等价模型是多带图灵机、多道图灵机、有输入和输出的机器，以及与确定型图灵机（Deterministic Turing Machine，DTM）和非确定型图灵机（non-Deterministic Turing Machine , NDTM）(NDTM) ，后者的动作表对于每个符号和状态组合最多只有一个条目。+ − + 第431行：
第431行： − 早在1936年的论文中，图灵就对“运动......完全由配置决定”的“自动机”和“选择机”进行了区分：+ − 它的运动只是部分由配置决定…当这样一台机器达到其中一种不明确的配置时，它不能继续运行，直到外部操作者做出任意的选择。如果我们使用机器来处理公理系统，就会出现这种情况。——The Undecidable，p.118+ − 图灵(1936)除了在脚注中描述了如何使用自动机来“找到所有希尔伯特微积分的可证明公式”，而不是使用选择机之外，没有做进一步的说明。他"假设选择总是在0和1之间。那么每个证明将由i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>n</sub> (i<sub>1</sub> = 0 或 1, i<sub>2</sub> = 0 或 1, ..., i<sub>n</sub> = 0 或 1) 的选择序列决定，因此数字 2<sup>n</sup> + i<sub>1</sub>2<sup>n-1</sup> + i<sub>2</sub>2<sup>n-2</sup> + ... +i<sub>n</sub> 完全决定了证明。自动机依次执行验证1、验证2、验证3，……”+ − + 第453行：
第453行： − 使用乐高积木实现的图灵机（Lego pieces）+ 第461行：
第461行： − + 第480行：
第480行： − 罗宾•甘迪（Robin Gandy，1919-1995）是图灵（1912-1954）的学生，也是他一生的朋友，他将“计算机器”这一概念的渊源追溯到查尔斯•巴贝奇（Charles Babbage）（大约1834年），并提出了“巴贝奇论”：+ 第490行：
第490行： − + − 关于著名数学家大卫·希尔伯特（David Hilbert）在1900年提出的希尔伯特问题中，第10号问题的一个方面浮动了近30年，才被准确地框定下来。希尔伯特对10号问题的原始表述如下：+ − + 第502行：
第502行： − 1928年的国际数学家大会，希尔伯特把他的问题描述的非常的细致。第一，数学是完整的吗？第二，数学是一致的吗？第三，数学是可判定的吗？”1930年，在希尔伯特发表退休演讲的同一次会议上，库尔特·哥德尔（Kurt Gödel）回答了前两个问题；而第三个问题（判定问题）不得不等到上世纪30年代中期。+ − 问题在于，要回答这个问题，首先需要对“明确的通用规则”下一个精确定义。普林斯顿大学的教授阿朗佐•丘奇（Alonzo Church）将其称为“有效可计算性”，而在1928年并不存在这样的定义。但在接下来的6-7年里，埃米尔•波斯特（Emil Post）拓展了他的定义，即一个工人按照一张指令表从一个房间移动到另一个房间书写和擦除标记（1936），邱奇和他的两个学生斯蒂芬·克莱恩（Stephen Kleene）和（j.B. Rosser）利用邱奇的λ微积分和哥德尔的递归理论也是如此。丘奇的论文（发表于1936年4月15日）表明，判定问题确实是“无法决策的”，比图灵早了将近一年（图灵的论文1936年5月28日提交，1937年1月发表）。与此同时，波斯特在1936年秋天提交了一篇短文，所以图灵至少比波斯特更有优先权。当丘奇评审图灵的论文时，图灵有时间研究丘奇的论文，并在附录中添加了一个草图，证明邱奇的λ微积分和他的机器可以计算同样的函数。+ 第511行：
第511行： − 1935年春天，图灵作为英国剑桥大学国王学院的一名年轻硕士生，接受了这个挑战；他受到逻辑学家纽曼（Newman）的讲座的鼓舞，并从他们那里了解了哥德尔的工作和判定问题。在图灵1955年的讣告中，纽曼写道:+ − 对于“什么是'机械'过程”？图灵回答了一个特有的答案“可以由机器完成的事情”，接着他开始着手分析计算机的一般概念。——Gandy，第74页 + 第520行：
第520行： − + 第532行：
第532行： − 根据人们在计算中喜欢操作的对象(非负整数或字母数字串等)，有两种模型在基于机器的复杂性理论中获得了主导地位：+ 第726行：
第726行： − +
无编辑摘要
图灵机在一条无限长的纸带上运行，纸带被分割成若干个离散的单元格。机器的读写头在一个单元格上“读取”或“扫描”纸带上的符号。然后，图灵机根据读取的符号和机器自身在用户指定指令的“有限表”中的状态，机器(i)在单元格中写下一个符号（例如，有限字母表中的数字或字母），然后(ii)将纸带向左或向右移动一个单元，然后(iii)根据观察到的符号和机器自身在表中的状态，要么继续执行另一指令，要么停止计算。
图灵机在一条无限长的纸带上运行，纸带被分割成若干个离散的单元格。机器的读写头在一个单元格上“读取”或“扫描”纸带上的符号。然后，图灵机根据读取的符号和机器自身在用户指定指令的“有限表”中的状态，机器(i)在单元格中写下一个符号（例如，有限字母表中的数字或字母），然后(ii)将纸带向左或向右移动一个单元，然后(iii)根据观察到的符号和机器自身在表中的状态，要么继续执行另一指令，要么停止计算。
图灵机是1936年由'''阿兰·图灵（Alan Turing）'''发明，他称之为“自动机”。通过这个模型，图灵能够否定地回答两个问题:
图灵机是1936年由'''阿兰·图灵 Alan Turing'''发明，他称之为“自动机”。通过这个模型，图灵能够否定地回答两个问题:
:: 是否存在一台机器，能够确定其纸带上的任意机器是否是“循环”的(例如，死机，或无法继续其计算任务) ?
:: 是否存在一台机器，能够确定其纸带上的任意机器是否是“循环”的（例如，死机，或无法继续其计算任务）？
:: 是否存在一种机器可以确定其纸带上的任何任意机器是否曾经打印出一个特定的符号？
:: 是否存在一种机器可以确定其纸带上的任何任意机器是否曾经打印出一个特定的符号？
因此，通过提供可以进行任意计算的非常简单的装置的数学描述，他能够证明计算的一般性质，尤其是判定性问题（翻译自德语Entscheidungsproblem, 英文译作decision problem）的不可计算性。
图灵机证明了机械计算能力存在基本限制。虽然机械计算可以表达任意的计算，但最小设计使机械计算不适合在实践中计算: 与图灵机不同的是，现实世界的计算机是基于另外一种设计，即使用随机存取存储器 （Random-access memory）。
图灵机证明了机械计算能力存在基本限制。虽然机械计算可以表达任意的计算，但最小设计使机械计算不适合在实践中计算: 与图灵机不同的是，现实世界的计算机是基于另外一种设计，即使用随机存取存储器 Random-access memory。
'''图灵完备性（Turing completeness）'''是一个指令系统模拟图灵机的能力。一个图灵完备的编程语言理论上能够表达所有计算机可以完成的任务; 如果忽略有限内存的限制，几乎所有的编程语言都是图灵完备的。
'''图灵完备性 Turing completeness'''是一个指令系统模拟图灵机的能力。一个图灵完备的编程语言理论上能够表达所有计算机可以完成的任务; 如果忽略有限内存的限制，几乎所有的编程语言都是图灵完备的。
==图灵机概述==
==图灵机概述==
图灵机是一种中央处理器单元 Central Processing Unit，即CPU，控制着计算机的所有数据操作，规范及其使用顺序内存来存储数据。更具体的，图灵机是一种能够枚举字母表有效字符串的机器（自动机）；这些字符串是字母递归可枚举集的一部分。理想情况下，图灵机有无限长的纸带，其可以在上面执行读写操作。
假设有一个“黑盒子”，图灵机无法知道它最终是否会用给定的程序枚举出子集中的任何一个特定字符串。这是因为停机问题 Halting Problem是不可解的，停机问题对计算的理论极限有着重大的影响。
图灵机能够处理不受限制的语法，这意味着它能够以无限多的方式鲁棒地评价一阶逻辑。通过λ运算可以证明这一点。
图灵机能够处理不受限制的语法，这意味着它能够以无限多的方式鲁棒地评价一阶逻辑。通过λ运算可以证明这一点。
能够模拟任何其他图灵机的图灵机称为通用图灵机。'''邱奇（Alonzo Church，美国著名数学家）'''提出了一个更具有普适性的数学定义。他将在λ运算的工作和图灵在正式计算机理论中的工作融合，称为邱奇-图灵理论。在这项工作中，他指出图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。研究它们的抽象特性可以使我们对计算机科学和复杂性理论有更深入的了解。
能够模拟任何其他图灵机的图灵机称为通用图灵机。'''邱奇 Alonzo Church，美国著名数学家'''提出了一个更具有普适性的数学定义。他将在λ运算的工作和图灵在正式计算机理论中的工作融合，称为邱奇-图灵理论。在这项工作中，他指出图灵机确实抓住了逻辑和数学中有效方法的非正式概念，并提供了算法或“机械程序”的精确定义。研究它们的抽象特性可以使我们对计算机科学和复杂性理论有更深入的了解。
===物理描述===
===物理描述===
在1948年的论文《智能机器 Intelligent Machinery》中，图灵写道他的机器包括: 以无限长纸带的形式获得的无限存储容量，纸带上标有方块，每个方块上可以打印一个符号。在任何时候，机器中都有一个符号，被称为扫描符号。机器可以改变扫描的符号，其行为部分由该符号决定，但纸带上其他地方的符号不会影响机器的行为。然而，纸带可以在机器中来回移动，这是机器的基本操作之一。因此，纸带上的任何符号最终都可能有一个局。
===描述===
===描述===
* 读写头。读写头可以在纸带上读写符号，并一次将纸带左右移动一个（有且仅有一个）单元格。在某些型号的机器中，读写头移动而纸带静止。
* 读写头。读写头可以在纸带上读写符号，并一次将纸带左右移动一个（有且仅有一个）单元格。在某些型号的机器中，读写头移动而纸带静止。
* 状态寄存器。状态寄存器用来存储图灵机的状态，是有限多个状态中的一个。其中有一个特殊的启动状态，状态寄存器就是用它来初始化。图灵写道，这些状态代替了执行计算的人通常会处于的 "精神状态"。
* 状态寄存器。状态寄存器用来存储图灵机的状态，是有限多个状态中的一个。其中有一个特殊的启动状态，状态寄存器就是用它来初始化。图灵写道，这些状态代替了执行计算的人通常会处于的“精神状态”。
* 一个有限的指令表<ref>Occasionally called an ''action table'' or ''transition function''.</ref><ref>Usually quintuples [5-tuples]: q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub>, but sometimes quadruples [4-tuples].</ref>，给定机器当前所处的状态(q<sub>i</sub>)和它在纸带上读取的符号(a<sub>j</sub>)（当前读写头下的符号），告诉机器依次做以下事情（对于5元组模型）：
* 一个有限的指令表<ref>Occasionally called an ''action table'' or ''transition function''.</ref><ref>Usually quintuples [5-tuples]: q<sub>i</sub>a<sub>j</sub>→q<sub>i1</sub>a<sub>j1</sub>d<sub>k</sub>, but sometimes quadruples [4-tuples].</ref>，给定机器当前所处的状态(q<sub>i</sub>)和它在纸带上读取的符号(a<sub>j</sub>)（当前读写头下的符号），告诉机器依次做以下事情（对于5元组模型）：
# 假设与规定的状态相同或新的状态（进入状态q<sub>i1</sub>）
# 假设与规定的状态相同或新的状态（进入状态q<sub>i1</sub>）
在四元组模型中，擦除或写入符号（a<sub>j1</sub>)）和向左或向右移动读写头（d<sub>k</sub>）被指定为独立的指令。该表告诉机器（ia）擦除或写入一个符号，或者（ib）向左或向右移动读写头，然后（ii）按规定承担相同或新的状态，但在同一指令中不能同时执行（ia）和（ib）。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停; 其他模型要求填充所有条目。
在四元组模型中，擦除或写入符号（a<sub>j1</sub>)）和向左或向右移动读写头（d<sub>k</sub>）被指定为独立的指令。该表告诉机器（ia）擦除或写入一个符号，或者（ib）向左或向右移动读写头，然后（ii）按规定承担相同或新的状态，但在同一指令中不能同时执行（ia）和（ib）。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停；其他模型要求填充所有条目。
机器的每一部分（即它的状态、符号收集和在任何特定时间使用的纸带）和它的行动（如打印、擦除和纸带运动）都是有限的、离散的和可区分的；是无限的纸带和运行时间给了它无限制的存储空间。
机器的每一部分（即它的状态、符号收集和在任何特定时间使用的纸带）和它的行动（如打印、擦除和纸带运动）都是有限的、离散的和可区分的；是无限的纸带和运行时间给了它无限制的存储空间。
===其他定义===
===其他定义===
文献中的定义有时会稍有不同，以使论证或证明更容易或更清晰，但这总是以使所产生的机器具有相同的计算能力的方式进行。例如，集合可以从 <math>\{L,R\}</math> 改为 <math>\{L,R,N\}</math>其中N("无 "或 "无操作")将允许机器停留在同一纸带单元上，而不需要左右移动。这样不会增加机器的计算能力。
文献中的定义有时会稍有不同，以使论证或证明更容易或更清晰，但这总是以使所产生的机器具有相同的计算能力的方式进行。例如，集合可以从 <math>\{L,R\}</math> 改为 <math>\{L,R,N\}</math>其中N（“无”或“无操作”）将允许机器停留在同一纸带单元上，而不需要左右移动。这样不会增加机器的计算能力。
最常见的规则是根据图灵/戴维斯的规则，在“图灵表”钟永9个5元组中的一个表示每个“图灵指令”（图灵1936年在《The Undecidable》p.126-127）：
最常见的规则是根据图灵/戴维斯的规则，在“图灵表”钟永9个5元组中的一个表示每个“图灵指令”（图灵1936年在《The Undecidable》p.126-127）：
|}
|}
在下表中，图灵的原始模型只允许前三行，他称之为N1, N2, N3(参见图灵书籍《The Undecidable》p.126）。他允许通过命名第0个S<sub>0</sub>="E"或"N"，即“擦除”或者“空白”等。但是，他不允许“不打印”，所以每个指令行都包括“打印符号S<sub>k</sub>”或者“擦除E”。这些缩写是图灵在1936-1937年的原始论文之后，机器模型已经允许所有九种可能的五元组类型。
在下表中，图灵的原始模型只允许前三行，他称之为N1, N2, N3（参见图灵书籍《The Undecidable》p.126）。他允许通过命名第0个S<sub>0</sub>="E"或"N"，即“擦除”或者“空白”等。但是，他不允许“不打印”，所以每个指令行都包括“打印符号S<sub>k</sub>”或者“擦除E”。这些缩写是图灵在1936-1937年的原始论文之后，机器模型已经允许所有九种可能的五元组类型。
{| class="wikitable" style="text-align: center"
{| class="wikitable" style="text-align: center"
!
!
!
!
当前的m配置<br />(（图灵状态）
当前的m配置<br />（图灵状态）
!
!
纸带符号
纸带符号
|}
|}
任何图灵表（指令列表）都可以由上述九个5元组构成。由于技术原因，三个非打印或“N”指令（4、5、6）通常可以省去。
较少遇到使用4元组的情况：这些代表了图灵指令的进一步原子化（参见Post(1947)，Boolos & Jeffrey(1974，1999)，Davis-Sigal-Weyuker(1994)）；
较少遇到使用4元组的情况：这些代表了图灵指令的进一步原子化（参见Post(1947)，Boolos & Jeffrey(1974，1999)，Davis-Sigal-Weyuker(1994)）；
图灵机上下文中使用的“状态”一词可能会引起混淆，因为它可能意味着两件事。图灵之后的大多数研究者都使用“状态”来表示要执行的当前指令的名称/指示符——即状态寄存器的内容。但是图灵 (1936) 在他所谓的机器“m-配置”的记录和机器（或人）通过计算的“进展状态”——整个系统的当前状态——之间做出了强有力的区分。图灵所说的“状态公式”包括当前指令和纸带上的所有符号：
图灵机上下文中使用的“状态”一词可能会引起混淆，因为它可能意味着两件事。图灵之后的大多数研究者都使用“状态”来表示要执行的当前指令的名称/指示符——即状态寄存器的内容。但是图灵 (1936) 在他所谓的机器“m-配置”的记录和机器（或人）通过计算的“进展状态”——整个系统的当前状态——之间做出了强有力的区分。图灵所说的“状态公式”包括当前指令和纸带上的所有符号：
因此，任何阶段的计算进度状态完全由指令注释和纸带上的符号决定。也就是说，系统的状态可以由单个表达式（符号序列）来描述，该表达式由纸带上的符号后跟Δ（我们假设不会出现在其他地方）和指令注释组成。这个表达式被称为“状态公式”。——《The Undecidable》,图灵，p.139–140
更早时期，图灵在他的论文中进行了进一步的研究：他举了一个例子，在该示例中，他把当前“m-配置”的符号（指令的标签）和纸带上的所有符号一起放在扫描的方块下面（《The Undecidable》，第121页）；他把这个称为“完整的配置”（《The Undecidable》，第118页）。为了将“完整配置”打印在一行，他将状态标签/m-配置放在扫描符号的左边。
在Kleene（1952）中可以看到这样的一个变体，Kleene展示了如何写出一台机器的“状态”的哥德尔数：他把“m-配置”符号q<sub>4</sub>放在磁带上6个非空白方格的大致中心的扫描方格上（见本文图灵-纸带图），并把它放在扫描方格的右边。但Kleene把“q<sub>4</sub>”本身称为“机器状态”（Kleene，第374-375页）。Hopcroft和Ullman把这种组合称为“瞬时描述”，并遵循图灵规定，把“当前状态”（指令标签，m-配置）放在扫描符号的左边（第149页）。
示例：3次“移动”后，三态2符号繁忙的海狸的总状态（取自下图中的示例“运行”）：
示例：3次“移动”后，三态2符号繁忙的海狸的总状态（取自下图中的示例“运行”）：
:: 1'''A'''1
:: 1'''A'''1
这意味着：经过三次移动后，纸带上有......000110000......，读写头正在扫描最右边的1，状态为A。空白（在这种情况下用 "0 "表示）可以成为总状态的一部分，如图所示。B01；纸带上有一个 "1"，但读写头正在扫描它左边的 "0"（"空白"），状态是B。
这意味着：经过三次移动后，纸带上有......000110000......，读写头正在扫描最右边的1，状态为A。空白（在这种情况下用“0”表示）可以成为总状态的一部分，如图所示。B01；纸带上有一个“1”，但读写头正在扫描它左边的“0”（“空白”），状态是B。
图灵机情况中，应阐明“状态”是哪种状态。(i)当前指令，或(ii)纸带上的符号列表连同当前指令，或(iii)纸带上的符号列表连同当前指令放在扫描符号的左边或扫描符号的右边。
图灵的传记作者Andrew Hodges (1983:107)注意到并讨论了这种混淆。
图灵的传记作者Andrew Hodges (1983:107)注意到并讨论了这种混淆。
许多可能被认为比简单的通用图灵机有更多计算能力的机器，实际上并没有更多的能力（Hopcroft和Ullman p.159, cf. Minsky(1967)）。它们可能计算得更快，或者使用更少的内存，或者它们的指令集可能更小，但是它们不能计算更多的数学函数。（邱奇-图灵理论假设这对任何机器都是正确的：任何可以被“计算”的东西都可以被某些图灵机器计算。）
许多可能被认为比简单的通用图灵机有更多计算能力的机器，实际上并没有更多的能力（Hopcroft和Ullman p.159, cf. Minsky(1967)）。它们可能计算得更快，或者使用更少的内存，或者它们的指令集可能更小，但是它们不能计算更多的数学函数。（邱奇-图灵理论假设这对任何机器都是正确的：任何可以被“计算”的东西都可以被某些图灵机器计算。）
图灵机相当于单堆栈下推自动机 Pushdown Automaton，PDA，它通过放宽其栈中的“后进先出”要求，使其更加灵活和简洁。此外，通过使用一个堆栈对读写头左侧的纸带进行建模，使用另一个堆栈对读写头右侧的磁带进行建模，图灵机也等效于具有标准“后进先出”语义的双堆栈PDA。
在另一个极端，一些非常简单的模型变成了图灵等价模型，即具有与图灵机模型相同的计算能力。
在另一个极端，一些非常简单的模型变成了图灵等价模型，即具有与图灵机模型相同的计算能力。
常见的等价模型是多带图灵机、多道图灵机、有输入和输出的机器，以及与确定型图灵机 Deterministic Turing Machine，DTM和非确定型图灵机 non-Deterministic Turing Machine，NDTM，后者的动作表对于每个符号和状态组合最多只有一个条目。
只读、右移动的图灵机相当于 DFAs（以及通过使用 NDFA 到 DFA 转换算法转换的 NFA）。
只读、右移动的图灵机相当于 DFAs（以及通过使用NDFA到DFA转换算法转换的NFA）。
对于实际的和教学的意图，等价的 寄存器机器可以作为通常的汇编编程语言使用。
对于实际的和教学的意图，等价的 寄存器机器可以作为通常的汇编编程语言使用。
==选择C型机器、Oracle的O型机器==
==选择C型机器、Oracle的O型机器==
早在1936年的论文中，图灵就对“运动……完全由配置决定”的“自动机”和“选择机”进行了区分：
它的运动只是部分由配置决定……当这样一台机器达到其中一种不明确的配置时，它不能继续运行，直到外部操作者做出任意的选择。如果我们使用机器来处理公理系统，就会出现这种情况。——The Undecidable，p.118
图灵（1936）除了在脚注中描述了如何使用自动机来“找到所有希尔伯特微积分的可证明公式”，而不是使用选择机之外，没有做进一步的说明。他“假设选择总是在0和1之间。那么每个证明将由i<sub>1</sub>, i<sub>2</sub>, ..., i<sub>n</sub> (i<sub>1</sub> = 0 或 1, i<sub>2</sub> = 0 或 1, ..., i<sub>n</sub> = 0 或 1) 的选择序列决定，因此数字 2<sup>n</sup> + i<sub>1</sub>2<sup>n-1</sup> + i<sub>2</sub>2<sup>n-2</sup> + ... +i<sub>n</sub> 完全决定了证明。自动机依次执行验证1、验证2、验证3，……”
这通过这种技术，一个确定型的（比如，a-）图灵机可以用来模拟一个非确定型的图灵机的行为; 图灵在脚注中解决了这个问题，似乎把它从进一步的考虑中剔除了。
这通过这种技术，一个确定型的（比如，a-）图灵机可以用来模拟一个非确定型的图灵机的行为; 图灵在脚注中解决了这个问题，似乎把它从进一步的考虑中剔除了。
Oracle机或o-machine是一种图灵机器，它将计算暂停在“o”状态，同时，为了完成计算，它“等待”“oracle”——一个未指定的实体（不是一台机器）“的决定（The undecutable，p.166-168）。
Oracle机或o-machine是一种图灵机器，它将计算暂停在“o”状态，同时，为了完成计算，它“等待”“oracle”——一个未指定的实体（不是一台机器）的决定（The undecutable，p.166-168）。
==通用图灵机==
==通用图灵机==
==与实际机器的比较==
==与实际机器的比较==
使用乐高积木实现的图灵机 Lego pieces
人们常说，图灵机不同于简单的自动机，它和实际的机器一样强大，能够执行真实程序所能执行的任何操作。在这种说法中被忽略的是，由于实际的机器只能有有限的配置，所以这里的“真正的机器”其实只是一个有限的状态机。另一方面，图灵机相当于拥有无限存储空间进行计算的机器。
人们常说，图灵机不同于简单的自动机，它和实际的机器一样强大，能够执行真实程序所能执行的任何操作。在这种说法中被忽略的是，由于实际的机器只能有有限的配置，所以这里的“真正的机器”其实只是一个有限的状态机。另一方面，图灵机相当于拥有无限存储空间进行计算的机器。
# 区别只在于图灵机有能力处理无限制的数据量。然而，在有限的时间内，图灵机（像实际的机器）只能操纵处理的数据量。
# 区别只在于图灵机有能力处理无限制的数据量。然而，在有限的时间内，图灵机（像实际的机器）只能操纵处理的数据量。
# 像图灵机一样，实际的机器可以根据需要，通过获得更多的磁盘或其他存储介质，扩大其存储空间。
# 像图灵机一样，实际的机器可以根据需要，通过获得更多的磁盘或其他存储介质，扩大其存储空间。
# 使用较简单的抽象模型对真机程序的描述往往比使用图灵机的描述要复杂得多。例如，描述算法的图灵机可能有几百个状态，而给定实际机器上的等效确定性有限自动机（deterministic finite automaton，DFA）却有四千亿个状态。这使得DFA的表示方式无法分析。
# 使用较简单的抽象模型对真机程序的描述往往比使用图灵机的描述要复杂得多。例如，描述算法的图灵机可能有几百个状态，而给定实际机器上的等效确定性有限自动机 deterministic finite automaton,DFA却有四千亿个状态。这使得DFA的表示方式无法分析。
# 图灵机描述的算法与它们使用的内存多少无关。目前任何机器所拥有的内存都有一个极限，但这个极限可以在时间上任意上升。图灵机允许我们对算法做出声明，这些声明（理论上）将永远成立，而不考虑传统计算机架构的进步。
# 图灵机描述的算法与它们使用的内存多少无关。目前任何机器所拥有的内存都有一个极限，但这个极限可以在时间上任意上升。图灵机允许我们对算法做出声明，这些声明（理论上）将永远成立，而不考虑传统计算机架构的进步。
# 图灵机简化了算法的表述。在图灵机上运行的算法通常比在实际机器上运行的算法更通用，因为它们有任意精度的数据类型可用，而且永远不必处理意外情况（包括但不限于内存耗尽）。
# 图灵机简化了算法的表述。在图灵机上运行的算法通常比在实际机器上运行的算法更通用，因为它们有任意精度的数据类型可用，而且永远不必处理意外情况（包括但不限于内存耗尽）。
===历史背景：计算机器===
===历史背景：计算机器===
罗宾•甘迪 Robin Gandy，1919-1995,是图灵（1912-1954）的学生，也是他一生的朋友，他将“计算机器”这一概念的渊源追溯到查尔斯•巴贝奇 Charles Babbage（大约1834年），并提出了“巴贝奇论”：
整个发展和分析的操作现在都可以由机器来执行。（italics in Babbage as cited by Gandy, p.54）
整个发展和分析的操作现在都可以由机器来执行。（italics in Babbage as cited by Gandy, p.54）
# 条件转移（即有条件的“goto”）。
# 条件转移（即有条件的“goto”）。
Gandy指出: “可由(1)、(2)和(4)计算出来的函数恰恰是那些图灵可计算的函数。”(p.53)。他引用了其他关于“通用计算机”的理论，包括珀西·卢德盖特（Percy Ludgate， 1909年）、莱昂纳多·托雷斯·奎维多（Leonardo Torres y Quevedo，1914年）、莫里斯·d’奥卡涅（Maurice d'Ocagne，1922年）、路易斯·库夫尼纳尔（Louis Couffignal，1933年）、万尼瓦尔·布什V（annevar Bush，1936年）、霍华德·艾肯（Howard Aiken，1937年）。然而:
Gandy指出: “可由(1)、(2)和(4)计算出来的函数恰恰是那些图灵可计算的函数。”(p.53)。他引用了其他关于“通用计算机”的理论，包括珀西·卢德盖特 Percy Ludgate， 1909年、莱昂纳多·托雷斯·奎维多 Leonardo Torres y Quevedo，1914年、莫里斯·d’奥卡涅 Maurice d'Ocagne，1922年、路易斯·库夫尼纳尔 Louis Couffignal，1933年、万尼瓦尔·布什V annevar Bush，1936年、霍华德·艾肯 Howard Aiken，1937年。然而：
重点是对一个固定的可迭代的算术运算序列进行编程。条件性迭代和条件性转移对于计算机的一般理论的根本重要性没有得到承认……——Gandy，第55页
重点是对一个固定的可迭代的算术运算序列进行编程。条件性迭代和条件性转移对于计算机的一般理论的根本重要性没有得到承认……——Gandy，第55页
===判定问题: 希尔伯特1900年提出的第10号问题===
===判定问题: 希尔伯特1900年提出的第10号问题===
关于著名数学家大卫·希尔伯特 David Hilbert在1900年提出的希尔伯特问题中，第10号问题的一个方面浮动了近30年，才被准确地框定下来。希尔伯特对10号问题的原始表述如下：
10. Diophantine方程的可解性的确定。给出一个具有任意数量的未知量和有理积分系数的Diophantine方程。设计一个过程，根据这个过程可以在有限的操作中确定该方程是否可以用有理整数来解。当我们知道一个程序，允许任何给定的逻辑表达式通过有限的多次操作来决定其有效性或可满足性时，判定问题（一阶逻辑的决定问题）就解决了……判定问题必须被认为是数理逻辑的主要问题。——2008年，德尔肖维茨（Dershowitz）和古列维奇（Gurevich）引用了此译文和德文原文
10. Diophantine方程的可解性的确定。给出一个具有任意数量的未知量和有理积分系数的Diophantine方程。设计一个过程，根据这个过程可以在有限的操作中确定该方程是否可以用有理整数来解。当我们知道一个程序，允许任何给定的逻辑表达式通过有限的多次操作来决定其有效性或可满足性时，判定问题（一阶逻辑的决定问题）就解决了……判定问题必须被认为是数理逻辑的主要问题。——2008年，德尔肖维茨 Dershowitz和古列维奇 Gurevich引用了此译文和德文原文
到了1922年，“判定问题”的概念有了进一步的发展，Behmann指出：
到了1922年，“判定问题”的概念有了进一步的发展，Behmann指出：
Behmann指出：一般问题相当于决定哪些数学命题是真的问题。如果能够解决判定问题，那么人们就会有一个“解决许多（甚至所有）数学问题的程序”。
Behmann指出：一般问题相当于决定哪些数学命题是真的问题。如果能够解决判定问题，那么人们就会有一个“解决许多（甚至所有）数学问题的程序”。
1928年的国际数学家大会，希尔伯特把他的问题描述的非常的细致。第一，数学是完整的吗？第二，数学是一致的吗？第三，数学是可判定的吗？”1930年，在希尔伯特发表退休演讲的同一次会议上，库尔特·哥德尔 Kurt Gödel回答了前两个问题；而第三个问题（判定问题）不得不等到上世纪30年代中期。
问题在于，要回答这个问题，首先需要对“明确的通用规则”下一个精确定义。普林斯顿大学的教授阿朗佐•丘奇 Alonzo Church将其称为“有效可计算性”，而在1928年并不存在这样的定义。但在接下来的6-7年里，埃米尔•波斯特 Emil Post拓展了他的定义，即一个工人按照一张指令表从一个房间移动到另一个房间书写和擦除标记（1936），邱奇和他的两个学生Stephen Kleene和j.B. Rosser利用邱奇的λ微积分和哥德尔的递归理论也是如此。丘奇的论文（发表于1936年4月15日）表明，判定问题确实是“无法决策的”，比图灵早了将近一年（图灵的论文1936年5月28日提交，1937年1月发表）。与此同时，波斯特在1936年秋天提交了一篇短文，所以图灵至少比波斯特更有优先权。当丘奇评审图灵的论文时，图灵有时间研究丘奇的论文，并在附录中添加了一个草图，证明邱奇的λ微积分和他的机器可以计算同样的函数。
但邱奇所做的是完全不同的事情，而且在某种意义上是较差的。……图灵的构造更直接，并提供了最初原则的论据，从而弥补了邱奇证明中的空白。——Hodges，第112页
但邱奇所做的是完全不同的事情，而且在某种意义上是较差的。……图灵的构造更直接，并提供了最初原则的论据，从而弥补了邱奇证明中的空白。——Hodges，第112页
===阿兰图灵的机器===
===阿兰图灵的机器===
1935年春天，图灵作为英国剑桥大学国王学院的一名年轻硕士生，接受了这个挑战；他受到逻辑学家纽曼 Newman的讲座的鼓舞，并从他们那里了解了哥德尔的工作和判定问题。在图灵1955年的讣告中，纽曼写道:
对于“什么是‘机械’过程”？图灵回答了一个特有的答案“可以由机器完成的事情”，接着他开始着手分析计算机的一般概念。——Gandy，第74页
Gandy表示：
Gandy表示：
上面说过，“如果一个函数的值可以通过某种纯粹的机械过程找到，那么它就是有效的可计算的”。我们可以从字面上理解这句话，用纯粹的机械过程来理解可以由机器来完成的过程。我们有可能以某种正常形式对这些机器的结构进行数学描述。这些想法的发展导致了作者对可计算函数的定义，以及对可计算性与有效可计算性的认同。要证明这三个定义（第三个是λ-微积分）是等价的并不困难，虽然有些麻烦。——图灵（1939）在《The Undecidable》一书中，第160页
上面说过，“如果一个函数的值可以通过某种纯粹的机械过程找到，那么它就是有效的可计算的”。我们可以从字面上理解这句话，用纯粹的机械过程来理解可以由机器来完成的过程。我们有可能以某种正常形式对这些机器的结构进行数学描述。这些想法的发展导致了作者对可计算函数的定义，以及对可计算性与有效可计算性的认同。要证明这三个定义（第三个是λ-微积分）是等价的并不困难，虽然有些麻烦。——图灵（1939）在《The Undecidable》一书中，第160页
当图灵回到英国后，他负责破解名为“英格玛”的加密机创造的德国密码；他还参与了ACE（自动计算引擎）的设计。“图灵的ACE建议实际上是自成一体的，其根源不在于EDVAC（美国的倡议），而在于他自己的通用机器”（Hodges p.318）。关于被Kleene（1952年）命名为 “图灵论文”的起源和性质的争论仍在继续。但是，图灵用他的计算机模型所证明的东西出现在他的论文中“On Computable Numbers, with an Application to the Entscheidungsproblem”。
当图灵回到英国后，他负责破解名为“英格玛”的加密机创造的德国密码；他还参与了ACE（自动计算引擎）的设计。“图灵的ACE建议实际上是自成一体的，其根源不在于EDVAC（美国的倡议），而在于他自己的通用机器”（Hodges p.318）。关于被Kleene（1952年）命名为 “图灵论文”的起源和性质的争论仍在继续。但是，图灵用他的计算机模型所证明的东西出现在他的论文中“关于可计算数及其在Entscheidungs型问题中的应用”。
希尔伯特-判定问题不可能有解……因此我建议，不可能有一个一般的过程来确定函数微积分K的一个给定公式U是否可证明，也就是说，不可能有一台机器在提供任何一个公式U的情况下，最终会说出U是否可证明。——摘自图灵的论文，详见《The Undecidable》，第145页
希尔伯特-判定问题不可能有解……因此我建议，不可能有一个一般的过程来确定函数微积分K的一个给定公式U是否可证明，也就是说，不可能有一台机器在提供任何一个公式U的情况下，最终会说出U是否可证明。——摘自图灵的论文，详见《The Undecidable》，第145页
如今，计数器、寄存器和随机存取机以及它们的先驱图灵机仍然是理论家们研究计算理论问题的首选模型。特别是，计算复杂性理论也使用了图灵机。
如今，计数器、寄存器和随机存取机以及它们的先驱图灵机仍然是理论家们研究计算理论问题的首选模型。特别是，计算复杂性理论也使用了图灵机。
根据人们在计算中喜欢操作的对象（非负整数或字母数字串等），有两种模型在基于机器的复杂性理论中获得了主导地位：
离线多带图灵机——它代表了面向字符串计算的标准模型，以及Cook和Reckhow提出的随机存取机(RAM) ，它是理想化的冯诺依曼式计算机的模型。——van Emde Boas 1990:4
离线多带图灵机——它代表了面向字符串计算的标准模型，以及Cook和Reckhow提出的随机存取机(RAM) ，它是理想化的冯诺依曼式计算机的模型。——van Emde Boas 1990:4
只有在算法分析的相关领域，这个角色才能被RAM模型所取代。——van Emde Boas 1990:4
只有在算法分析的相关领域，这个角色才能被RAM模型所取代。——van Emde Boas 1990:4
----
----
本中文词条由Moonscar、[[用户:Solitude|Solitude]]、[[用户:Langenfeng|Langenfeng、Swarma]]编译，AvecSally、[[用户:ZQ|ZQ]]及用户[[用户:SyouTK|SyouTK]]审校，编辑，如有问题，欢迎在讨论页面留言。
本中文词条由Moonscar、[[用户:Solitude|Solitude]]、[[用户:Langenfeng|Langenfeng、Swarma]]编译，AvecSally、[[用户:ZQ|ZQ]]审校，SyouTK编辑，如有问题，欢迎在讨论页面留言。
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''
'''本词条内容源自wikipedia及公开资料，遵守 CC3.0协议。'''