图灵机（二）_数学联邦政治世界观

表 5：TAddi 的转换表

0 1

q1 / 0Rq2

q2 1Rq3 1Rq2

q3 0Lq6 1Lq4

q4 0Rq5 1Lq4

q5 / 0Rq1

q6 0Rqhalt 1Lq6

TAddi 机器使用将加数右移的原理，该原理也用于 TAdd2。更具体地说，Taddi 从左到右计算 n1+1、n2+1、… ni+1 的总和，即按如下方式计算该总和：

N1 =n1+n2+1

N2 =N1+n3

N3 =N2+n4

⋮

Ni =Ni−1+ni+1

TAd2 和 TAddi 之间最重要的区别是 TAddi 需要验证最左边的加数 Nj,1<j≤i 是否等于 Ni。这是通过检查 Nj 右侧的第一个 0 后面是否跟着另一个 0（状态 q2 和 q3）来实现的。如果不是，则至少还有一个加数 nj+1 需要添加。请注意，与 TAdd2 的情况一样，机器需要从加数 nj+1 中删除一个额外的 1，这通过状态 q5 完成。然后它返回到状态 q1。另一方面，如果 Nj=Ni，机器将移动到 Ni=n1+n2+…+ni+1 的最左边的 1 并停止。

2.2 可计算数和问题

图灵的原始论文涉及可计算（实）数。如果存在一台图灵机可以计算该数的任意精确近似值，则该（实）数是图灵可计算的。所有代数数（具有代数系数的多项式的根）和许多超越数学常数（例如 e 和 π）都是图灵可计算的。图灵给出了几个图灵机可计算的数类示例（参见图灵 1936-7 年第 10 节“可计算的大量数类示例”），作为启发式论证，表明图灵机可以计算多种数类。

然而，人们可能想知道，在何种意义上，用数字进行计算，即计算，可以解决非数字但可计算的问题，以及图灵机如何解决确定某事是否属实的所有通用和有效程序。此类问题的示例包括：

“对于任何给定的 x，确定 x 是否表示素数”

“对于任何给定的 x，确定 x 是否是图灵机的描述”。

一般来说，这些问题的形式如下：

“对于任何给定的 x，确定 x 是否具有属性 X”

计算理论和具体进步（通常与其他学科交织）的一个重要挑战是提供对 X 的解释，以便可以通过计算解决。举一个具体的例子，在日常计算实践中，可能重要的是要有一种方法来决定任何数字“源”是否可以信任，因此需要对信任进行计算解释。

谓词的特征函数是当给定适当的参数时具有 TRUE 或 FALSE 值的函数。为了使此类函数可计算，图灵依靠哥德尔的洞察力，认为这类问题可以编码为数字问题（参见哥德尔不完备定理和下一节 2.3）。图灵的措辞是：

“有一个确定……”的通用过程已被用作 [此处] […] 等同于“有一台机器将确定……”。当且仅当我们能够证明“可计算”的定义时，这种用法才是合理的。对于这些“一般过程”中的每一个，问题都可以表示为有关确定给定整数 n 是否具有属性 G(n) 的一般过程的问题 [例如，G(n) 可能意味着“n 令人满意”或“n 是可证明公式的哥德尔表示”]，这相当于计算一个数字，如果 G(n) 为真，则第 n 位为 1，如果为假，则第 n 位为 0。（1936–7：248）

将“一般过程”问题编码为数值问题的可能性对于图灵构建通用图灵机及其在证明中的作用至关重要，该证明表明存在图灵机无法计算的问题。

2.3 图灵的通用机器

通用图灵机是为了证明某些问题的不可计算性而构建的，粗略地说，它是一台能够计算任何其他图灵机计算的内容的图灵机。假设图灵机概念完全涵盖了可计算性（因此图灵的论点是有效的），这意味着任何可以“计算”的东西也可以由该通用机器计算。相反，任何通用机器无法计算的问题都被认为是不可计算的。

这就是通用机器概念的修辞和理论力量，即一种相对简单的形式化设备可以捕获所有“计算数字时可能执行的过程”（图灵 1936-7）。这也是图灵被追溯为计算机科学创始人之一的主要原因之一（见第 5 节）。

那么，如何从我们掌握的基本操作集合中构建通用机器 U？图灵的方法是构建一个机器 U，它能够 (1)“理解”任何其他机器 Tn 的程序，并基于这种“理解”，(2)“模仿”Tn 的行为。为此，需要一种方法，允许交替处理程序和 Tn 的行为，因为这两个方面都是在同一条磁带上由同一台机器操作的。图灵通过两个基本步骤实现了这一点：开发 (1) 符号方法 (2) 一组基本函数，该函数将该符号视为要比较、复制、删除等的文本（无论它是在形式化程序还是 Tn 的行为）。换句话说，图灵开发了一种技术，允许在同一级别上处理程序和行为。

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

给定某个机器 Tn，图灵的基本思想是构造一个机器 T

′

，它不是直接打印 Tn 的输出，而是打印出 Tn 的连续完整配置或瞬时描述。为了实现这一点，T

′

：

[…] 可以依赖于将 [Tn] 的操作规则 […] 写在其内部的某个地方 […] 每个步骤都可以通过参考这些规则来执行。（图灵 1936–7：242）

换句话说，T

′

通过将 Tn 的程序写入其磁带来打印出 Tn 的连续完整配置。因此，图灵需要一种符号方法，使其能够在同一条磁带上“捕获”图灵机的两个不同方面，以便同一台机器可以处理它们，即：

（1）它应该做什么的描述——五元组符号

（2）它正在做什么的描述——完整配置符号

因此，在构造 U 时，第一步，也许是最重要的一步是五元组和完整配置符号以及将它们放在同一磁带上的想法。更具体地说，磁带被分成两个区域，我们在这里将其称为 A 和 B 区域。A 区域包含 Tn 的“程序”符号，B 区域包含 Tn 的连续完整配置符号。在图灵的论文中，它们被一个附加符号“::”分隔开。

为了简化 U 的构造并将任何图灵机编码为唯一数字，图灵开发了第三种符号，允许仅用字母来表示五元组和完整配置。这是由 [请注意，我们使用图灵的原始编码。当然，有各种各样的可能的编码，包括二进制编码] 决定的：

将 Tn 的五元组中的每个状态 qi 替换为

A…A

⏟

，

因此，例如 q3 变为 DAAA。

将 Tn 的五元组中的每个符号 Sj 替换为

C…C

⏟

，

因此，例如，S1 变为 DC。

使用这种方法，某个图灵机 Tn 的每个五元组都可以用大写字母序列来表示，因此任何机器 Tn 的“程序”都可以用符号集 A、C、D、R、L、N 和 ; 来表示。这就是所谓的图灵机的标准描述 (S.D.)。因此，例如，TSimple 的 S.D. 是：

;DADDRDAA;DADCDRDAA;DAADDCRDA;DAADCDCRDA

这本质上是图灵版本的哥德尔编号。事实上，正如图灵所展示的，人们可以通过替换以下内容轻松获得图灵机 Tn 的数值描述表示或描述数 (D.N.)：

“A” 替换为“1”

“C” 替换为“2”

“D” 替换为“3”

“L” 替换为“4”

“R” 替换为“5”

“N” 替换为“6”

“;”用“7”表示

因此，TSimple 的 D.N. 为：

7313353117313135311731133153173113131531

请注意，每台机器 Tn 都有一个唯一的 D.N.；一个 D.N. 只代表一台机器。

显然，用于确定某台机器 Tn 的 S.D. 的方法也可用于写出 Tn 的连续完整配置。使用“：”作为连续完整配置之间的分隔符，TSimple 的前几个完整配置为：

:DAD:DDAAD:DDCDAD:DDCDDAAD:DDCDDDDAD

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

具有一种符号方法，可以将某台机器 Tn 的程序和连续完整配置写在另一台机器 T 的同一盘磁带上

是图灵建造U的第一步一些图灵机的操作]为他人“（图灵1936-7：242）。 viz。，它应该不能只是计算，而且还可以计算，也是教堂，哥特尔和邮政等人处理的问题，这些问题也使用自己的正式设备处理。例如，它应该能够“识别”它是否在区域A或B中，并且它应该能够确定一定序列是否是需要执行的下一个状态Qi。

这是通过建造一系列图灵计算问题，例如：

找到一系列符号的最左派或最右边的发生

用一些符号标记一系列符号A（记住图灵使用两种交替正方形）

比较两个符号序列

复制符号序列

图灵开发了一种据此一种称为骨架表的符号技术，用于这些功能，这些功能用作完整的图灵机表的一种简写符号，但是可以轻松地用于构造来自先前的机器的更复杂的机器。该技术非常让人想起组成的递归技术（参见：递归函数）。

为了说明这种功能如何进行计算，我们更详细地讨论了一个这样的功能，viz。比较功能。它是基于许多其他图灵计算功能构造的，该功能基于彼此的顶部构建。为了了解这些功能如何工作，请记住，图灵使用了一个交替的F和E形方块的系统，其中F方块包含实际的Quintulple和完整配置，并且E形方格用作标记机器磁带的某些部件的方式。对于两个序列S1和S2的比较，S1的每个符号将由一些符号A标记，并且S2的每个符号将被一些符号B标记。

定义定义的九种不同功能，以显示如何使用图灵机计算比较功能：

find（qi，qj，a）：此机器功能搜索最左派的发生。如果找到A，则机器移动到状态QI eys移动到状态QJ。这是通过使机器首先移动到磁带的开头（由特殊标记表示）来实现的，然后将其移动到右侧，直到它找到或达到磁带上最右边的符号。

findl（qi，qj，a）：与查找相同但在找到后，机器将一个方形移动到左侧。这用于需要在F范围的符号上计算的函数，该符号由符号A中的符号A标记。

擦除（qi，qj，a）：机器计算找到。如果找到了一个，它会删除一个并进入状态qi它进入状态qj。

erase_all（qj，a）= erase（erase_all，qj，a）：机器在反复上计算擦除，直到所有A都已删除。然后它移动到QJ。

平等（qi，qj，a）：机器检查当前符号是否为a。如果是，它将移动到状态qi其他它移动到州qj。

cmp_xy（qi，qj，b）= findl（等于（qi，qj，x），qj，b）：无论当前符号x如何，机器在b上计算findl（因此查找标有b的符号）。如果有一个标有B的符号y，则机器计算等于x和y，否则，机器进入状态Qj。换句话说，cmp_xy（qi，qj，b）比较当前符号是否与标记为b的最左边的符号相同。

COMPARE_MARKED（QI，QJ，QN，A，B）：机器检查标记A和B的最左边的符号是否相同。如果没有标记A或B的符号，则机器进入状态Qn; 如果有一个标记A和一个标记的B且它们相同，则机器进入状态Qi，否则机器进入状态QJ。该函数被计算为FindL（CMP_XY（QI，QJ，B），查找（QJ，QN，B），a）。

compare_erase（qiqj，qn，a，b）：与compare_mark相同，但是当标记a和b的符号相同时，标记a和b被删除。这是通过计算擦拭第一在a然后b上的擦除来实现的。

COMPARE_ALL（QJ，QN，A，B）机器将分别与A和B的标记的序列A和B进行比较。这是通过反复计算A和B的Compare_Erase来完成的。如果A和B相等，则所有A和B都将被删除并且机器移动到状态QJ，否则，它将移动到州Qn。它是计算的

compare_erase（compare_all（qj，qn，一个，b），qj，qn，一个，b）

因此通过递归调用compare_all。

以类似的方式，图灵定义了以下功能：

复制（qi，a）：复制标有一个完整配置右侧的符号序列并删除标记。

COPYN（QI，A1，A2，...，AN）：将标记为A1的序列复制到最后完整配置的右侧，擦除所有标记AI。

替换（qi，a，b）：替换所有字母a by b。

mark_next_config（qi，a）：用字母a标记机器头部右侧的第一个配置qisj。

find_right（qi，a）：找到最右边的符号a。

使用基本功能副本，更换和比较，图灵构造了一个通用的图灵机。

下面是通用图灵机的概要，指示这些基本功能的确实如何实现通用计算。假设在初始化后，您的磁带是S.D. 一些图灵机TN。请记住，图灵使用交替F和E形方块的系统，因此，例如，S.D。 Tsimple将写在你的录像带上：

; _d_a_d_d_r_d_a_a _，_ d_a_d_c_d_r_d_a_a _，_ d_a_a_d_d_c_r_d_a _，_ d_a_a_d_c_d_c_r_d_a_

其中“_”表示未标记的E-Square。

init：在T_N最右边的Quintuple的右侧，U打印:: _：_ d_a_，其中_表示未标记的E-Square。

find_next_state：机器的第一个标记（1）与y配置QCC，ISCC，j的最右边（且上次）的j键在磁带的B部分中计算，（2）与x配置qq，msq，msq，n的最左边Quintuple未在磁带的一部分中标记（带字母Z）分号。比较了这两种配置。如果它们是相同的，则机器移动到MARK_OPERATIONS，如果不是，它将标记在QQ之前的分号，MSQ，n为z，然后进入find_next_state。使用函数Compare_All可以轻松实现这意味着，无论比较结果如何，都将删除标记x和y。例如，假设TN = Tsimple并且由U计算的Tsimple的最后完整配置是：

：_

⏟

d_c_

⏟

d_a_a_

⏟

第2季度

⏟

然后你将移动到区域A并确定相应的Quintuple是：

d_a_a_

⏟

第2季度

⏟

d_c_

⏟

d_a_

⏟

第1季度

mark_operations：机器U标记它需要执行的操作，以计算TN的下一个完整配置。打印和移动（L，R，N）操作标有U和y的下一个状态。所有标记Z都被删除。继续我们的例子，你将标记（2）如下：

d_a_a_d_ducurudyay

mark_compconfig：由u计算的tn的最后一个完整配置标记为四个区域：配置QCC，ISCC，J本身未标记; 刚刚在它之前的符号标记为x和左侧的剩余符号或用v标记。最后，右边的所有符号（如果有的话）被打印到最右边符号的右侧，以指示下一个完整的开头通过U.持续到我们的示例的TN配置，（1）将被标记为U：

⏟

dvcv

⏟

d_a_a_

⏟

第2季度

⏟

：_

然后你打印

打印。

（本章完）