图灵机（一）

图灵机，由艾伦·图灵于 1936-7 年首次描述，是一种简单的抽象计算设备，旨在帮助研究可计算的范围和局限性。图灵的“自动机器”是他在 1936 年命名的，专门用于计算实数。它们最初由阿隆佐·丘奇在评论图灵的论文时命名为“图灵机”（丘奇 1937 年）。如今，它们被认为是可计算性和（理论）计算机科学的基础模型之一。[1]

1. 图灵机的定义

1.1 图灵的定义

1.2 波斯特的定义

1.3 定义形式化

1.4 描述图灵机的行为

2. 用图灵机进行计算

2.1 一些（简单）示例

2.2 可计算数和问题

2.3 图灵的通用机

2.3.1 程序和行为的可互换性：符号

2.3.2 程序和行为的可互换性：一组基本函数

2.4 停机问题和判定问题

2.4.1 不可计算决策问题的直接和间接证明

2.4.2 图灵的基本问题 CIRC?, PRINT?和判定问题

2.4.3 停机问题

2.5 图灵机的变体

3. 与图灵机相关的哲学问题

3.1 人类和机器计算

3.2 论题、定义、公理或定理

4. 可计算性的替代历史模型

4.1 一般递归函数

4.2 λ-可定义性

4.3 后期制作系统

4.4 公式 1

5. 图灵机对计算机科学的影响

5.1 对理论计算机科学的影响

5.2 图灵机和现代计算机

5.3 编程理论

参考书目

学术工具

其他互联网资源

Busy Beaver

停机问题

在线图灵机模拟器

软件模拟器

硬件模拟器

相关条目

1. 图灵机的定义

1.1 图灵的定义

图灵引入了图灵机器在数学基础研究的背景下。更具体地说，他使用这些抽象设备来证明没有有效的通用方法或程序来解决、计算或计算以下问题的每个实例：

Entscheidungsproblem 决定一阶逻辑（所谓的受限函数演算，请参阅经典逻辑条目以了解简介）中每个语句是否可以在该逻辑中推导的问题。

请注意，在其原始形式（Hilbert & Ackermann 1928）中，问题是以有效性而不是可推导性来陈述的。鉴于哥德尔完备性定理（Gödel 1929），证明存在（或不存在）可推导性的有效程序也是以有效性形式解决该问题的解决方案。为了解决这个问题，需要一个形式化的“有效程序”概念，而图灵的机器正是为此而设计的。

那么，图灵机，或者图灵称之为计算机，在图灵最初的定义中，是一种能够执行一组有限配置 q1,…,qn（机器的状态，图灵称之为 m 配置）的机器。它配备了一个单向无限和一维的磁带，磁带被分成几个方块，每个方块只能携带一个符号。在任何时刻，机器都在扫描一个方块 r 的内容，该方块要么是空白的（用 S0 表示），要么包含一个符号 S1,…,Sm，其中 S1=0 和 S2=1。

该机器是一台自动机器（a 机器），这意味着在任何给定时刻，机器的行为完全由当前状态和正在扫描的符号（称为配置）决定。这就是所谓的确定性条件（第 3 节）。这些 a 机器与所谓的选择机器形成对比，后者的下一个状态取决于外部设备或操作员的决定（图灵 1936-7：232）。图灵机能够执行三种类型的操作：

打印 Si，向左移动一个方格（L）并进入状态 qj

打印 Si，向右移动一个方格（R）并进入状态 qj

打印 Si，不移动（N）并进入状态 qj

图灵机的“程序”可以写成以下形式的五元组的有限集合：

qiSjSi,jMi,jqi,j

其中 qi 是当前状态，Sj 是正在扫描的方格的内容，Si,j 是方格的新内容；Mi,j 指定机器是向左移动一个方格、向右移动一个方格还是保持在同一方格，qi,j 是机器的下一个状态。这些五元组也称为给定机器的转换规则。图灵机 TSimple 从空白磁带启动后，计算序列 S0S1S0S1…，如表 1 所示。

表 1：TSimple 的五元组表示

;q1S0S0Rq2

;q1S1S0Rq2

;q2S0S1Rq1

;q2S1S1Rq1

请注意，TSimple 永远不会进入扫描 S1 的配置，因此四个五元组中有两个是多余的。表示图灵机的另一种典型格式是转换表，图灵也使用过这种格式。表 2 给出了 TSimple 的转换表。

表 2：TSimple 的转换表

S0 S1

q1 S0Rq2 S0Rq2

q2 S1Rq1 S1Rq1

目前图灵机的定义通常只有一种符号（通常只有 0 和 1；香农证明任何图灵机都可以简化为二进制图灵机（香农 1956））图灵在他最初对所谓计算机的定义中使用了两种符号：完全由 0 和 1 组成的数字和所谓的第二类符号。这些符号在图灵机磁带上通过使用交替的数字平方和第二种符号的系统来区分。一个交替的平方序列包含数字，称为 F 平方序列。它包含机器计算的序列；另一个称为 E 平方序列。后者用于标记 F 方格，用于“辅助记忆”（图灵 1936-7：232）。E 方格的内容可能会发生变化。但是 F 方格不能改变，这意味着无法实现需要更改先前计算的数字的算法。此外，如果 F 方格之前的 F 方格尚未计算，机器将永远不会在 F 方格上打印符号。F 和 E 方格的这种用法非常有用（见第 2.3 节），但正如 Emil L. Post 所展示的那样，它会导致许多复杂情况（见第 1.2 节）。

关于图灵机设置，有两件重要的事情需要注意。第一件事情涉及机器本身的定义，即机器的磁带可能是无限的。这对应于机器的内存（可能）是无限的假设。第二个涉及图灵可计算的定义，即如果存在一组指令，使得图灵机可以计算该函数，而不管计算所需的时间，那么该函数就是图灵可计算的。我们可以认为这是假设有无限的时间来完成计算。

这两个假设旨在确保计算结果的定义不会太狭隘。也就是说，它确保没有可计算函数会仅仅因为没有足够的时间或内存来完成计算而无法实现图灵可计算。因此，可能存在一些图灵可计算函数，现有的计算机可能无法执行这些函数，这可能是因为现有的机器没有足够的内存来执行该任务。一些图灵可计算函数在实践中可能永远无法计算，因为它们可能需要比使用宇宙中所有（有限数量的）原子所能构建的内存更多的内存。如果我们进一步假设物理计算机是图灵机的有限实现，并且图灵机可以作为计算机的良好形式模型，那么表明函数不是图灵可计算的结果是十分强的，因为这意味着我们建造的任何计算机都无法执行计算。第 2.4 节表明，有些函数不是图灵可计算的。

1.2 Post 的定义

图灵的定义通过 Post 在 1947 年对它的（一些）修改而标准化。在那篇论文中，Post 证明了数学中被称为 Thue 问题或半群字问题的一个问题不是图灵可计算的（或者，用 Post 的话来说，是递归不可解的）。Post 的主要策略是表明如果它是可判定的，那么图灵 1936-7 年的以下决策问题也将是可判定的：

打印？ 决定每个图灵机的问题它是否会打印一些符号（例如，0）。

然而，通过图灵打印证明了这一点？ 不是计算的，所以你的问题也是如此。

虽然印刷的无疑性？ 邮政在帖子证明中发挥着核心作用，据信“确定了”虚假图案“的证明受”虚假图案“（第1947：9），VIZ的影响。 F和E范围的系统。 因此，发布引入了图灵机的修改版本。 帖子和图灵定义之间最重要的差异是：

邮政的图灵机，当处于给定状态时，打印或移动，因此其过渡规则更为“原子”（它没有移动和打印的复合操作）。 这导致图灵机的四重符号，其中每个四级是表3的三种形式之一：

表3：帖子的四重符号

qisjsi，jqi，j

qisjlqi，j

qisjrqi，j

帖子的图灵机只有一种符号，因此不依赖于F和E-Squares的图灵系统。

柱的图灵机具有双向无限磁带。

帖子的图灵机会在到达没有定义任何操作的状态时停止。

注意，TING Machine的帖子的重构非常植根于1936年的帖子中。（一些）帖子的图灵定义的修改成为图灵机的定义的一部分标准工程，如Kleene 1952和Davis 1958。从那时起，几个时间（逻辑上等效）已经介绍了定义。 如今，在某些方面，图灵机的标准定义更接近邮政的图灵机比图灵的机器。 在下文中，我们将使用Minsky 1967的标准定义上的变体，它使用了Quintuple符号，但没有E和F正方形，包括特殊的停留状态H.它还只有两个移动操作，viz，l和r，所以行动不使用机器打印。 除了机器启动时，磁带是空白的，除了磁带的一些有限部分。 注意，空白方块也可以表示为包含符号S0或简单的方形的正方形。磁带的有限含量也将被称为磁带上的DataWord。

1.3定义正式化

谈论“磁带”和“读写头”旨在帮助直觉（并揭示某些时间的图灵写入的时间），但在图灵机的定义中发挥着重要作用。 在需要进行图灵机的正式分析的情况下，在更多数学术语中阐明机械和程序的定义是合适的。 纯粹是正式的图测机器可以指定为四重奏T =（Q，σ，s，δ），其中：

Q是一组有限的状态Q

σ是有限符号

s是初始状态s∈q

Δ是确定下一个移动的过渡功能：

δ：（q×σ）→（σ×{l，r}×q）

机器T的转换功能是从计算状态到计算状态的函数。 如果δ（qi，sj）=（si，j，d，qi，j），则当机器的状态是qj时，读取符号sj，t替换si，j，方向移动d∈{l，r}并转到州qi j。

1.4描述了图灵机的行为

我们介绍了一个表示，它允许我们描述图灵机TN的行为或动态，依赖于今天也知道的完整配置（图4 1936-7：232）的符号作为瞬时描述（ID）（Davis 1982：6）。 在TI计算的任何阶段，其ID由：

（1）磁带的内容，即其数据字

（2）阅读头的位置

（3）机器的内部状态

因此，考虑到在状态Qi扫描符号SJ的一些图灵机T，它的ID由PQISJQ给出，其中P和Q是包含符号SJ的正方形的左侧和右侧的有限字。 图1给出了状态qi扫描磁带的一些图灵机T的ID的视觉表示。

一个图灵机：链接扩展

描述下面

图1：一些图灵机T的完整配置。[图1的扩展描述是补充。]

因此，表示法允许我们通过其连续ID捕获机器及其磁带的开发行为。 图2使用图形表示给出了Tsimple的前几个连续的ID。

图2：Tsimple图形表示的动态。 （动画可以通过单击图片来开始，然后使用左箭头和右箭头来移动它。）[图2的扩展说明在补充中。]

使用其符号表示，人们还可以明确打印连续的ID。 这导致了图灵机的行为的状态图。 所以，对于我们得到的tsimple（请注意

¯

0

意味着0s的无限重复）：

¯

0

q10的

¯

0

¯

0

0q20

¯

0

¯

0

01q10

¯

0

¯

0

010q20

¯

0

¯

0

0101q10

¯

0

¯

0

01010q20

¯

0

⋮

2.用图灵机计算

正如秒所解释的那样。 1.1，图灵机最初旨在将可计算性的概念正式化，以解决数学的基本问题。 独立于图灵，Alonzo教堂提供了不同但逻辑上等效的制定（见第4章）。 如今，大多数计算机科学家都同意图灵或任何其他逻辑上等效的正式概念捕获了所有可计算问题，viz。 对于任何可计算问题，有一个计算它的图灵机。 这被称为教会图论论文，图灵的论文（当参考只参考工作时）或教会的论文（当参考只对教会的工作）时。

它意味着，如果接受，则无需任何有限的装置而不可通过任何有限装置计算的任何问题。 事实上，由于它是为了捕获“[全部]可以在计算数字中进行的可能进程而设计的雄心，因此，如果我们接受图灵的分析：

无需通过图灵机可计算的任何问题在绝对意义上不是“可计算”（至少，相对于人类绝对），参见第3节）。

对于我们认为可计算的任何问题，我们应该能够构建计算它的图灵机。 把它放在图灵的措辞中：

我的争论是[计算机器] [计算机]的操作包括所有在计算的计算中使用的所有争论。 （图灵1936-7：231）

在该部分中，将给出示例，其示出了图灵机模型的计算功率和边界。 第3节然后讨论了与图灵论文相关的一些哲学问题。

2.1一些（简单）的例子

为了谈谈从人类角度有所了解的东西，我们必须提供对磁带上记录的符号的解释。 例如，如果我们想设计一台将计算一些计算一些数学函数的机器，那么我们将需要描述如何解释作为数字上显示的磁带上的零和零。

在遵循的示例中，我们将表示数字n作为磁带上符号'1'的n + 1份的块。 因此，我们将表示为单个“1”的数字0，而第3号作为四个'1的块。 这称为一元符号。

当机器启动时，我们还必须对磁带的配置进行一些假设，并且在完成时，以解释计算。 我们将假设如果要计算的函数需要n个参数，则图灵机将以其头部扫描1的N块块的最左侧的“1”开始。 表示参数的'1的块必须通过符号'0'的单个发生来分隔。 例如，为了计算SUM 3 + 4，图灵机将以图3所示的配置开始。

一个图灵机：链接扩展

描述下面

图3：用于两个数字n和m的计算的初始配置。 [图3的扩展描述是补充。]

这里假设的加法机需要两个代表要添加的数字的参数，从第一个参数的最左边启动。 参数根据需要由单个0分隔，第一个块包含四个'1的，表示数字3，第二个块包含五个'1，表示数字4。

机器也必须以标准配置完成。 必须有一个单个符号块（表示表示某种输出的一些数字或符号的1S序列，并且机器必须扫描该序列的最左侧符号。 如果机器正确计算函数，则此块必须表示正确的答案。

采用该公约用于终止配置图定型机器意味着我们可以通过将一台机器的最终状态识别下一个的初始状态来编写机器。

添加两个数字n和m

表4给出了图灵机TADD2的过渡表，它增加了两个自然数N和M。 我们假设机器在状态Q1中开始扫描N + 1的最左侧1。

表4：TADD2的过渡表

0 1

第1季度/ 0rq2

第2季度1lq3 1rq2

第3季度0rq4 1lq3

第4季度/ 0rqhalt

使用Unary表示时，使用图灵机进行添加的想法是将最左边的N个正方形转移到右侧。 这是通过擦除N + 1的最左侧1来实现的（这在状态Q1）中，然后在N + 1和M + 1到1之间设置0（状态Q2）。 然后我们有n + m + 2，因此我们仍然需要擦除一个额外的1.这是通过擦除最左边的1（状态Q3和Q4）来完成的。 图4显示了3 + 4的该计算。

图4：TADD2的计算3 + 4（可以通过单击图片来启动动画，然后使用左右箭头来移动透过它。）[图4的扩展说明在补充中。]

添加n个数字

我们可以将TADD2概括为图灵机Taddi，以添加整数N1，N2，...，NJ的任意数量I。 我们再次假设机器在状态Q1中扫描N1 + 1的最左侧1。 表5中给出了这种机器Taddi的过渡表。