图灵机上的编程语言、解释器和应用

图灵约定了 Figure 区域（也就是纸带的偶数位置）一旦写下 0 或 1 就不能再被修改，因此只能不断往这个区域的空白格子追加 0 或 1 。他把那些会无限地往 Figure 区打印 0 或 1 的机器称为非循环机，这是理想的表示实数的机器，因为每个实数都有无限长的小数位。

循环机则是那些在 Figure 区的某些格子之间循环，或者只能在 Erase 区域里进行无限打印或擦除的机器，这实际是偏离了目标的机器，这种机器永远无法表示一个实数（因为在图灵的定义中，即便是 0.1 也应该表示成 0.10000… 无限循环）。

由于每个机器都是由一套转移规则确定，而转移规则里的符号是有限的，因此图灵机的个数是可数无穷的。如果图灵机所能计算的数就是人类按照一般方式能计算出的数，那么可计算数就是可数无穷多个。或者退后一步，即便图灵机所能计算的并非一般意义的人类可以计算的数，那么图灵机上可计算的数也是可数无穷，因此实数里实际有大量的数是无法在图灵机上计算得到的。

按理说这个论述实际已经有一定的说服力了，因为我们把机器规约到了有限符号组成的规则中，而这种规则集合是可数无穷，因此机器对应的潜在的计算方式的数量也是可数无穷。

但图灵并没有满足于此，他继续去模仿康托尔用对角线法则证明实数有不可数无穷个的方式，假设可计算数是可数无穷，用对角线法则可以构造出一个数 d，该数第 i 个数位是第 i 个图灵可计算数第 i 位取反的结果（1 取反为 0,0 取反为 1）。因此如果这个数是可计算的，那么就会导出矛盾，说明可计算数是不可数的，但这与上一段论述的“图灵机的描述本身是可数的”是矛盾的。于是我们只能承认数 d 是图灵不可计算的。

按理说这个论证实际也有说服力，即图灵已经找出了一个可以描述但是无法计算的实数。

然而图灵还没有停下来，因为他的最终目的不是找出不可计算的数，而是要论证有些“功能需求描述看似合理的”机器是不存在的。计算二进制数只是图灵机的一个小应用，但如果能证明某些机器不存在，得到的意义可能更大，因为也许可以说明判定任何数学公式的机器是不存在的（尽管判定任何数学公理这个需求看上去可能不是那么离谱，毕竟人类智能体在历史上已经证明了大量定理，也证明了许多否定性质的定理，比如不存在最大的素数，根号二 2 不是有理数）。因此作为判定机器不存在的预热，他还想继续去从找出一个可以描述执行过程，但却不可能存在的机器。

于是他设想了这样一个机器：给定任何其他图灵机的描述（就像通用机能够读取输入一样），它能判断该机器是否是非循环的（也就是判定这台机器是否是一台能够打印无限精度数的机器）。

接着他假设这个机器是存在的，记为 D, 那么用这个机器，结合枚举的手段就可以构造出一个数 d', 该数的第 i 位和 d 的第 i 位相反，也就是说 d' 和 d 的都是通过对角线方式构造的，只不过它的第 i 位等于第 i 个可计算数的第 i 位，不进行额外取反操作。

注意取 d' 这个数来证明实际是比较“大胆的”，因为它不是遵照原版的对角线法则构造的数， 如果用这个数去证明实数的不可数性，实际是会失败的。因为即便是有限集合情况下，比如以下三个数构成的集合:

123
223 
313 

如果按照常规对角线法则，取对角线上的数，并且每一位加 1 拼接得到数是 234, 那么我们知道，这个数一定不在该集合中。

然而如果取对角线的数位直接拼接，得到的是 123, 它实际是在该集合里的。

因此有可能对所有可计算数取对角线拼接成的数也是可计算数，也就是说这个问题如果沿用康托尔的对角线方法，从纯数学的角度是没法证明它的可计算性的。

然而，要用机器的机械性质去证明这样的数不是可计算的，这实际是一个很大的创新，因为它说明图灵机和可计算数的对应关系（或者说同构）能够获得一些不是那么显而易见的结论。

就好比有时候无法在时域里发现特别性质的信号，经过傅里叶变换到频域里，就很容易证明某些性质， 图灵实际用机械性质构建了一种新的数学对象，在数学层面可能不容易思考时，可以换到机械层面（历史上相似的同构还包括：笛卡尔用坐标系把代数和平面几何对应起来，哥德尔用编码把逻辑命题、证明和自然数对应起来）。

回到证明过程，假设有一个判定任何图灵机是否非循环的机器 D, 那么可以构造一个机器 H, 它用来打印数 d' 。H 要遍历所有可计算数，做法是，先从 1 开始枚举所有自然数，假设当前已经检查了 n-1 个自然数，并找到了 R(n-1) 个可计算数，即 R(n-1) 个非循环机器，那么继续检查自然数 n:

• 先将 n 解码成图灵机对应的标准描述。这种解码实际还是字符串匹配， 因为图灵定义的标准数与标准描述之间，每个字符是一一对应的（即便不是一一对应，比如用哥德尔配数方式， 由于图灵机也可以模拟乘法，因此同样可以正确解码，但这需要花费更多篇幅解释， 因此图灵没有用更复杂的编码方式）。

• 将图灵机标准描述传给机器 D ，如果 D 判断该机器为非循环，那么可以在纸带某个约定位置打印 u, 否则打印 s.

  注意“传给”机器 D 可以有多种方式，一种是，D 的描述已经写在了纸带的某个区域上， H 本身有就有通用机的功能，H 写完数字并解码后就进入通用机功能部分的初始状态，然后开始模仿 D 去读取解码后的机器描述。这是最标准的做法，因为可以把 H 完全看作一个机器，便于后文描述。

  另一种是，H 可以停下来等待 D, 也就是 H 和 D 共享同一个纸带，由于图灵机是对人的行为建模，这种停下来等待 D 的做法对人来说也是一种很基础的行为，并且这种行为和根据状态进行转移没有本质差别，只不过要能把这种行为的指令写在纸带上，会需要更多解释，通用机的实现会更难。

• H 执行完 D 的功能之后，检查标志区，如果是 u 说明当前数字 n 对应的图灵机 M 是非循环的，也就是找到了一个可计算数。那么这时候 H 继续去模仿 <M> ，打印出 <M> 对应的数的第 R(n-1)+1 位，将这一位添加到当前已经计算的 d' 中。

  如果标志区是 s, 说明 M 是循环的，那么跳过这个数，继续写下并检查 n+1 ，如此循环

检查第 n 个数的纸带分区和变化如下：

问题在于，H 本身也对应一个整数 n(H), 当 H 循环遍历到 n(H) 时，如果 D 认为 H 是非循环的，那么会打印 u, 接着 H 就要去模仿自己的执行过程，那么又要从 1 开始遍历，因此它永远找不出 d' 的下一位，H 也就是循环机了。 如果 D 认为 H 是循环机，在标志位打印 s, 那么 H 会跳过对 H 自身的模仿，继续检查 n(H)+1 ，那么 H 看上去又是非循环的了。

这里实际有潜在的问题，比如 H 可能在 n(H)+1 上陷入了循环，那么 H 被 D 判断为循环就是正确的了。 不过图灵是从分析 H 的逻辑上来说服大家 H 就是非循环的，理论上，机器不可能在除了 n(H) 之外的数下出现循环，因为如果 D 判断 n(H)+1 或任何非 n(H) 数对应的机器是非循环的，说明 H 一定能模拟这个机器，不会在那个机器上陷入循环。

图灵在说明无法构造一个判断某个机器是否为非循环机的机器之后，又继续证明不存在一个判断某个机器是否打印过数字 0(或其他任何字符) 的机器，而这里图灵引入被后人称为 “规约”的技巧，即当已经知道算法 B 是不可能存在的情况下，想要证明 A 算法也不存在，那么先假设 A 存在，然后通过 A 构造出 B 算法。 由于 B 是不可能的，这就导致了逻辑上的矛盾，因此 A 也是不可能的。

注意尽管 A 和 B 都是不可能存在的，但通过 A 构造出 B 的算法是存在的，否则无法通过 B 的不存在而推导出 A 的不存在。

因此实际可以实现一些不存在的机器之间的规约算法，对于图灵机，要将规约技巧落到代码上， 实际核心包括两个部分：

• 编码的转换：由于图灵机就是用一组转移规则，很多时候只要编码合适，直接就可以把把问题转成另外一种。

  通用图灵机的存在性可以粗糙地看作是一种规约，正是因为给机器进行了编码，使得机器能够写在纸带上， 那么解析这些规则所需要的操作就和打印 0/1 序列需要的操作一样了（操作数据的指令能被规约成普通的数据）。

• 规则的转换：将某个图灵机转成另外一个图灵机，实际类似是一种源代码翻译软件。

图灵在论文里声称，可以构造一个机器，输入另一个机器的描述，将这台机器打印的第一个 0 改为 "-"（或其他字符），如果这个机器不打印 0, 那么机器功能不变，如果只打印一个 0 ，那么修改后的程序将不会打印出 0 ，即每次改写机器后按顺序减少一个打印 0 的次数。

本节实现这样的“源代码改写”程序，只不过用 python 实现，而非图灵机。

考虑以下打印 0 的图灵机，它只是无限向右不断打印 0(不考虑 Figure 和 Erase 区)

("b","0","0","R","b")
("b","1","0","R","b")

如何让它变成先打印一个 "-" 然后再无限打印 0 呢？一种做法是，找到那个打印第一个 0 的规则，记录为 rule0，然后在进入这条规则前插入一个新状态，先转移到该状态下打印一个 "-" 后再进入 rule0。 然而，仔细检查会发现，为了找到 rule0 ，需要先找到第一次触发 rule0 的那条规则, 而这会继续往前递归， 导致要动态追踪每一条指令，相当于用通用机反向去模拟这个机器，但如果该机器不打印 0, 就永远找不到这条规则。

实际上，寻找哪条规则打印第一个 0 本身是不可判定的，因为它就是一个判断机器是否会打印 0 的机器， 而当前我们就是在证明该机器不存在。

因此，为了实现“静态”的规则改写，我们不能依赖一个不存在的检测第一条打印 0 的规则的机器。

这里的做法是，对所有规则额外复制一份，但用新的状态来表示原来的状态，然后将原来的所有会打印 0 的规则里 0 的改为 "-"，并把这条规则中的下一个状态改成对应的新状态。

当然这里还有一些细节，具体参见 numbers/turing_machine/reduction.py at main · metaescape/numbers 中的 translator0 函数和相关测试。

有了这种转换函数之后，结合之前假定存在的能够判断是否打印 0 的机器 check0，就可以构造一台机器 T, 给定机器 M 的描述 <M> 作为输入：

• 用 check0 去检查 M 是否打印 0, 如果不打印 0, 那么在纸带写下 0
• 如果打印 0 ，那么用 translator0 改写 M 后，将新的 M1 重新记为 M

也就是 T 是在循环判断和改写 M, 如果 M 从来没有打印 0 或只打印有限个 0, 那么 M 最终会被改写成一个不打印任何 0 的程序，这样 T 就会无限打印 0. 如果 M 不是无限打印 0, 那么 T 就是一个循环机器，不打印任何有效内容。

现在构造新机器 F0, 它调用 check0 再测试 T, 注意这里的调用关系是 check0(T(check0,M)), 实际上 check0 测试了 check0 自己的一部分。

• 如果 check0 说 T 打印过 0, 说明 M 只打印过有限个 0.
• 如果 check0 说 T 没有打印过 0, 说明 M 会打印无限个 0.

这意味着可以构造出一台检测任何图灵机是否打印无限个 0 的机器。 注意这里的转变是，原本 check0 只是检测 M 是否打印 0, 如果 M 是循环机它也能给出回答，但我们还无法说清如何把循环性质体现出来，而目前构造的机器 F0 可以检查 M 是否打印无限个 0, 这已经是非循环的体现了。

还有一个问题是，如果 F0 的回答是 M 只打印过有限个 0, 那么 M 可能是循环也可能是非循环地打印 1.

因此还需要引入一个机器 F1, 它能检测 M 是否打印无限个 1, 这个构造是对偶的，既然有能检查是否打印 0 的机器 check0，理论上可以构造一个新的改写器，把 check0 中规则里涉及到 0 的部分改成 1, 涉及 1 的部分改成 0, 就能得到检查是否打印 1 的机器 check1，从而构造 F1.

有了 F1, 那么就可以确定 M 是循环的还是非循环地不断打印 1, 结合 F0 就得到检测其他机器是否非循环的机器，而这是不可能的。

因此可以看到，整个过程涉及到三个改写函数：

• 把机器打印的第一个 0 改写成其他符号的函数： translator0（已实现）
• 把机器打印的第一个 1 改写成其他符号的函数： translator1
• 把 check0 改成 check 1 的函数

最后，判断图灵机是否打印无限个 0 或 1 意味着什么？如果机器打印了有限个 0, 那么一定存在某个 N, 对于任何下标大于 N 的纸带格子里都是 1, 那么这其实是一个有理数（0.1111… 极限是 1）。打印有限个 1 的机器对应的也是有理数。

这实际说明并不存在一个通用的判断可计算数是否是无理数的方法，自然也不存在通用的判断某个实数是否是无理数的 方法。

在图灵论文里，图灵机本身被证明是通用的，它处理的对象是纸带上的字符串。如果纸带上写的是其他机器的指令，它可以读取指令并模仿该机器，如果是数理逻辑公理和推理规则，它还可以用来模拟逻辑推理过程。

图灵选择了打印无限数位的实数这个案例，引入了不可计算数，这仅仅是图灵机的一个应用，由于只要求打印 0 和 1, 因此描述或展示起来更方便。

这个应用的最终结果是，可以用证明实数不可数的对角线法则作为引子，将问题翻译到图灵机的执行过程中，从而证明某些实数是无法被图灵机计算出来的。这不单开辟了计算机科学里可计算性理论，也开辟了数学里可计算数的分析理论（类似实分析），因为图灵用一种机制建立起了一个桥梁，桥梁一边是数，另一边是机械规则。

马丁戴维斯等人则把图灵机应用到更实际的场景中，这些场景里，人类希望图灵机能够停下来返回出具体结果，而不是永远等它打印一个不可能结束的实数，于是后人将停机定义为一种正常的机器行为，不停机表示异常。

注意这种转变不需要对图灵机本身结构或原理做任何修改，只需要约定，当机器进入到某些状态时，表示机器正常停止（比如就叫作 "stop" 状态）。

在这种设定下，每个机器可以看作是将字符串映射成另外一个字符串的函数：先把某些字符串写在纸带上，机器运行了一段时间后停下来，然后读取纸带上的结果，图灵设计的通用机是类似的，不过在实数表示的应用中，其输出还是无限长的字符串。

在更实用场景中，先将字符串写在纸上，机器读取分析，最后要么打印出 accept, 要么打印出 reject 然后进入 "stop" 状态, 要么就无限循环。而与之等价的是，机器读取完初始纸带数据进行分析，最后要么进入 "accept" 状态，要么进入 "reject" 状态，要么不停机。

但有些机器，它只进入 "accept" 或 "reject" 状态, 永远不会进入死循环。比如以下是一个图灵机，记为 ALL0，对于任意有限长度的全 0 的字符串，它最终会进入到 accept 状态下停机，如果遇到其他字符则会进入到 reject 下停机。

("b","0","0","R","b")
("b","_","_","R","accept")
("b","*","1","R","reject")

而以下机器，记为 ALL_MAY_0，如果遇到全 0 字符串，会进入 accept 状态，如果其中有 "1" 则会进入 reject 状态，但如果有其他类型的字符，则会在 "b" 状态下无限循环。

("b","0","0","R","b")
("b","_","_","R","accept")
("b","1","1","R","reject")
("b","*","1","N","b")

第一台机器比第二台要好，它更不会浪费我们的时间，因为对于第一台机器，当它运行很久的时候，我们知道它可能是在识别一个很长的字符串（不考虑机器故障的话），但对于已经运行很长时间的第二台机器，不知道是因为字符串太长还是遇到了非法字符。

于是我们会期望有一台机器 D，它能识别其他机器 M 在某个字符串 w 作为输入时是否停机。给定 M 的描述 <M> 和字符串 w, 拼接成 <<M> w> 后写在这台机器初始纸带上, D 分析其内容后一定能最终停下来，如果 M 会在 w 上停机则 D 停在 accept 状态，否则停在 reject 状态。

这个问题可以有两个版本，一般流传最多的“停机问题”版本和计算理论里的”图灵可判定语言“版本。不过这里额外引出一个版本，先完全模仿图灵在论文中采用的对角线方法来构造停机问题，再引出书本里介绍较多的停机问题，最后介绍形式语言里的图灵不可判定语言。

图灵用 3 页纸写出了通用机的所有代码和注释，没有机器调试的情况下， 只能在大脑或纸上模拟，最终整个解释器只有少量的错误，这是如何做到的？

首先图灵构造的机器规则非常少，机器每一次运行一步，在纸带上最多出现一个字符的变化， 而状态最多变化一次，这种局部性质使得可以用一般的搜索算法来解析指令并构造纸带下一刻的状态。

具体来说，如果把每一步纸带的快照连同状态（被称为完全格局）都写到纸带上， 让纸带记录整个机器计算的历史，那么可以从最后一个完全格局上找出机器 应该所在的状态，以及读写头所在位置的字符，那么根据状态和字符就又可以去规则中查出下一个状态、 位置和需要打印的内容，也就是只需要对最后一个完全格局做非常小的修改就可以得到下一个完全格局。

为了能够更便捷地写出通用机描述，图灵还临时发明了一个对状态和规则进行抽象的类似函数式的高级语言， 最终能够用少量代码实现出几乎正确的程序。

根据计算历史的差异设计出来的原理“简单”的算法（可将其称为 diff 算法），几乎是没有实用性的， 这类似暴力算法一般都是概念上简单，但执行上低效一样。不过图灵只需要考虑逻辑正确性。

图灵把某个是否打印 0 的机器描述编码成数理逻辑的语言，为了描述转移规则以及机器是永远不停机这个事实， 必须用到全称量词来说明所有计算历史中完全格局的性质，因此这里必须要用到带量词的谓词逻辑，而不能只是命题逻辑。

而由于计算历史无非就是多个差异很小的完全格局的组合，因此它们之间转换的性质是可以通过有限逻辑规则描述的。

由于图灵用机器模拟对角线法已经证明不存在判定机器是否非循环的图灵机，而这台机器可以被逻辑命题描述出来，因此存在无法判定的逻辑命题。

Cook-Levin 定理说的是，任何 NP 问题都可以在多项式时间内规约到 3-SAT 问题。 3-SAT 是判断形如 (x|y|z)&(x|z|w) 的命题逻辑公式是否可满足，即是否存在一组变量赋值，使得这个命题逻辑公式为真。

首先这个问题实际和图灵证明不可判定非常类似，都是要建立机器和逻辑之间的等价关系，只不过 Cook-Levin 面对 的是一个计算复杂度上受限的机器，即那些能解决 NP 问题的图灵机，这些机器都是会停机的，因此不会涉及到无穷。这种限制使得描述机器的逻辑语言可以是命题逻辑， 而不需要带量词的谓词逻辑。

具体来说，NP 问题指的是在非确定性图灵机 NTM 上解决的问题，即给定一个字符串 w 一个 NTM 可以在 O(n^k) 步骤内判定这个字符串属于某个类。非确定性图灵机是为了便于描述更复杂计算而设计的机器，但它实际等价于一般的图灵机，只不过计算复杂度会指数爆炸。

既然所以 NP 问题都可以在多项式步骤内解决，因此不需要全称量词就可以把整个计算历史用命题逻辑形式来描述， 如果该命题存在一组为真的赋值，说明存在一个被 NTM 接受的计算分支。

这使得所有 NP 问题的计算历史形式可以被命题逻辑表达式描述，所有 NP 问题都可以转为 SAT 问题，而 SAT 可以在多项式时间转为 3-SAT, 因为 3-SAT 是第一个 NP 完全问题。

参考： 16. Cook-Levin Theorem_哔哩哔哩_bilibili

在对角线法则相关的证明中，不同版本的图灵机都出现了自引用的情况，它们基本是用来否定某类机器的存在性。

那些算法中机器 H 是如何获得自己的描述 <H> 并运行的？

实际需要三类能力：

• 能写下自然数并不断加 1
• 能将数字解码成图灵机描述
• 能执行这个描述（通用机功能）

而这三类能力可以继续还原到那些字符串操作的功能上，最终规约到（潜在）无限长的纸带、读写头移动和读写、根据条件进行转移状态的能力上。

比如所有对角线方式都可以用以下 python 伪代码程序来表示：

cnt = 1
while True:
    program = decode(cnt)
    if static_check(program):
        runtime_check_then_run(program)
    cnt += 1

• decode 是把整数转成机器可以运行的指令的函数（即指令要能够表示成和机器本身处理的数据对象一样的形式）
• static_check 是检查解码后字符串是否真的是合法程序，大部分数字解码后得到的都是“乱码”，有些很像程序， 但也可能有语法错误，比如 f(x, 。因此只有那些真正是程序的才能进入下一个阶段， 这部分检查是可计算的（从图灵机的语法来看，我们很容易检查某个字符串是否是合理的图灵机指令。 如果是现代编程语言，由于 CFG 的检查问题是可判定的，因此这类函数都可以正常停机）
• runtime_check_then_run 则要检查程序运行起来时候的特点，但这里存在不可计算的问题：
  • 比如想要筛选出那些最终能停机的程序，这样理论上才可以运行到该程序自己， 否则会被中途某个无限循环程序卡住，但即便如此，当遇到程序自己的编码时，还是会陷入悖论。
  • 一种保证该程序一定会执行到自己的做法是，runtime_check_then_run 对程序都执行固定步数， 比如 10 步，那么以上程序一定能执行到自身，但无法区分哪个程序是它自己。

因此我们需要一些更方便描述能够精确灵活地引用程序自己的机制，这里关注打印自身的程序（也称为 quine 程序）

根据 计算理论导引（原书第3版） 6.1 节介绍。

如果要在（可停机的）图灵机上构造一个打印自身指令的机器（注意指令有多种编码，因此在不同编码下会有不同打印程序），一种方法是，把机器执行过程拆成 A 和 B 两部分：

• A 是打印 B 的程序，记录为 P<B>; 执行完 A 后 <B> 就出现在了纸带上。但我们不知道 B 是什么，因此实际写程序的时候要先构思 B 。
• B 不需要依赖 A, 否则会陷入互递归，它只是看到纸带上的数据 data，于是明白，原来 A 是一个打印 data 的程序，所以如果 B 能够根据纸带数据返回打印数据的图灵机描述，就可以在纸带开头插入 A 的描述 <A>, 这样机器运行结束之后，纸带上就留下了 <A>data
• 而此时由于已经有了 <B> 的程序，那么 A 就因该一个打印 <B> 的程序，将 data 替换成 <B>. 最后纸带就剩下 <A><B>

在写出程序 <A><B> 的过程中，人和机器分别需要要说明能力（或者说智能）？

• 程序要能够读取纸带数据，并且反推出机器是如何打印这些数据的

  暂且不考虑细节的话这是简单的。比如给定字符串 "010", 打印 "010" 的一个图灵机就是：

  ("start","_",["0","R","1","R","0"], "end")
  

  注意这是一个把数据变成指令的程序，实际又在做类似指令翻译或改写的工作，如果纸带上写是指令，那么就需要 B 能写出一段打印指令的指令。这里的核心在于指令能被看作普通的能够被读取和打印的数据。

• 人要能写出这种带有反推机制的程序 <B>，并且写出打印 <B> 的程序 <A>

  也就是说，机器和人在这里要达到一个共识，机器 B 部分能够反推出 <A>, 人也能在写出 <B> 之后 反推出 <A> 。对于图灵机，打印特定数据的机器（转移规则集）有无数个， 比如在以上规则后添加一些额外的永远不会执行的转移规则，或者将以上命令拆分成多步骤， 但保持功能不变。我们只需要选定一个就可以了，并且机器和人要约定用相同的反推原则。

  如果看到纸带上有 a, 机器反推出的指令是 pa, 而人反推出的是 p(a), 那么最终写出来的程序就 不会等于原程序了

此外还要额外考虑：

• 编码问题：我们一般都是用以上四元组方式来描述图灵机指令的，但这种形式不方便打印在纸带上， 在通用机一节里，图灵设计了标准编码。对于自打印机器，也应该设置一套编码，它不需要和通用机 的标准编码一致（比如不需要把指令都约定成 5 元组形式，并且用 ; 分开，这种方式是为了更好的指令解析，但子打印程序中不需要解析指令，只需要根据数据反推出唯一的一个指令）

  因此最终“自复制”出的结果是不同抽象层上的“自己”。

  额外地，如果图灵机是实体，那么它需要有组装机器的能力，那些字符得对应成具体的零件， 移动方式对应机器人的动作，这不单模糊数据和指令，还模糊了物理世界和信息世界。

• 打印出 SELF 的指令之间顺序可以不考虑。因为图灵机的指令是一个集合，它内部是有顺序性的，但指令之间不需要顺序性。

  以下形式的指令是等于 <A><B> 的

  <B><A>
  

  A,B 内部指令之间顺序也是无关，原程序是 a1,a2,a3,b1,b2, 但打在纸带上可能是 b2,b1,a2,a1,a3

numbers/turing_machine/self.py at main · metaescape/numbers 中实现了一个“取巧”的自打印图灵机，其中 A,B 两部分采用的编码是不同的，比如 B 部分用的是接近标准编码的形式，q1 会被解析成 DA, 字符 R,A 等会解析成 DCC,DCCC 形式。 因此 <B> 部分是形如 DADCDCCDAA… 的字符串，这个时候 B 要去把它修改成打印 DADCDCCDAA… 的程序，为了能够更简单实现，我们直接把其中的 D 改成 P, 即 B 程序执行完后纸带内容变成：

DADCDCCDAA...PAPCPCCPAA...

PAPCPCCPAA 表示打印 DA, DC,DCC,DAA, 这样的话，我们需要对 PAPCPCC 形式额外写一个解码器， 转成真正能在图灵机上执行的程序 <A>.

因此严格来说，把图灵机加上编码器和解码器得到的才是真正的自打印程序。

对于自然语言，我们可以写出

重写一遍这个句子

按照指令的话会得到相同的句子。

以上句子中用到了自我引用的代词 "这个" 。然而原版的图灵机是没有 self 原语的，因此我们无法在图灵机上模仿这种方式来打印自身。

但对于现代计算机，由于我们用的是寄存器加内存随机寻址机制，cpu 本身可以解码内存地址，而代码本身就是放在内存中的，因此只要知道程序加载在哪（操作系统提供），就 可以轻松引用到自己。

比如以下是用 python 提供的引用函数体自身的机制，它实际要去保存指令的内存区获取数据：

def print_my_self():
    import inspect
    # add any thing here
    source_code = inspect.getsource(print_my_self)
    function_name = print_my_self.__name__
    print(source_code)
    print("print_my_self()")

print_my_self()

def print_my_self():
    import inspect
    # add any thing here
    source_code = inspect.getsource(print_my_self)
    function_name = print_my_self.__name__
    print(source_code)
    print("print_my_self()")

print_my_self()

如果程序写在单独文件里，那么用引用文件的 self api 即可：

with open(__file__, "r") as f:
     content = f.read()
     print(content)

而如果是在 jupyter 里还可以引用 block 本身：

from IPython.core.magics.execution import _format_time
ip = get_ipython()
# 获取当前单元格的内容, 可添加任何内容
current_cell = ip.user_ns['In'][-1]
print(current_cell)

from IPython.core.magics.execution import _format_time
ip = get_ipython()
# 获取当前单元格的内容, 添加任何内容
current_cell = ip.user_ns['In'][-1]
print(current_cell)

甚至数字和 string 对象本身就有打印自身的能力（这是编码上的不动点）

123

123

自打印程序和内置库的设计也很相关，比如假设 python 里有一个打印函数叫作 self_print

def self_print(s):
    if type(s) == str:
        return f"self_print('{s}')"

那么把以上函数藏到内置库里的话，只要是单引号输入的字符串都是 quine 程序了，只不过当前 python 提供的 print 不直接支持这种机制。

self_print('你好 quine')

self_print('你好 quine')

然而图灵机上自复制的存在是说明，即便没有直接提供访问自己的 api, 也是可以实现自己打印自己的功能。

不考虑 python 本身提供的引用自己的方式，我们如何把前文在图灵机上描述的自打印程序，按相同的拆分成 <A><B> 两部分的思路迁移到 python 呢？

先对比底层各个组件之间的区别：

• 图灵机里的纸带既是“屏幕”又是内存。

  图灵机可以从“屏幕”（figures）区中读取数据然后反推出打印数据的程序，并继续打印到屏幕上。但 python 打印完内容是没法从标准输出“读取”回来的。因此 python 里能读能写的不是屏幕，而只能是内存。

  然而，图灵机默认是一条纸带，所有的操作都是针对这段区域的，但 python 中，只能用具体变量 来表示内存，比如 tape="123", 然后可以通过 tape 具体去操作内存里的值。

• 图灵机打印命令是 "P0" 而在标准格式中，只需要用 "0" 就可以打印 "0"

  在交互式 python 里， 0 或者 print(0) 都可以被正常打印。

• 如果要写出类似 <B> 程序的 python 程序，我们先从 tape 变量（内存而非标准输出或屏幕）中读取数据，然后反推出一个打印 tape 里数据的程序。

  但这额外引出了 tape 的构造，也就是 tape="…" 中 tape= 部分，这部分也必须被打印出来， 所以大致有了以下框架：

  tape="..."; print(f"tape={tape};")
  

  tape=...;
  

  这里我们有定义 tape, 同时有打印 tape=, 也读取了 tape 中内容。按图灵机的思路， 接下来考虑根据数据取到的 tape 里的内容 …, 反推出打印这些数据的程序，然后把这个程序打印到纸带内容之前。

  那么反推出的程序是什么？实际上带 print 的部分代码本身就是根据数据反推的结果，我们要 把 tape="…" 打印出来，一定要用 print, 这本身就是 <B>, 而 tape 里的内容就应该是 <B>

  我们先把内容都复制过去，会发现引号的问题：

  tape="print(f"tape={tape};")"; print(f"tape={tape};")
  

    File "<ipython-input-80-0dcef513ccaf>", line 1
      tape="print(f"tape={tape};")"; print(f"tape={tape};")
                    ^
  SyntaxError: invalid syntax
  

  于是变成了修这些引号细节，比如直接把第一个改成单引号

  tape="print(f'tape={tape};')"; print(f"tape={tape};")
  

  tape=print(f'tape={tape};');
  

  发现少了一部分，因此添加两份：

  tape="print(f'tape={tape}{tape};')"; print(f"tape={tape}{tape};")
  

  tape=print(f'tape={tape}{tape};')print(f'tape={tape}{tape};');
  

  这比较接近，但引号和分号还是出了问题， fstring 引入和多重引号，因此不用这种方式：

  tape=";print('tape=' + tape + tape)"; print('tape=' + tape + tape)
  

  tape=;print('tape=' + tape + tape);print('tape=' + tape + tape)
  

  第一个语句还是少了引号，这里需要引入 repr 函数，它会给字符串添加引号，比如

  print("str")
  

  str
  

  这没有引号，但以下有引号

  repr("str")
  

  'str'
  

  注意 repr 打印出的是单引号，因此只要用单引号才行：

  repr('str')
  

  'str'
  

按照这种思路，参考 kirjavascript/quine-howto: how to write lots of quines, 得到的完全打印自身程序如下：

tape=";print('tape=' + repr(tape) + tape)";print('tape=' + repr(tape) + tape)

tape=";print('tape=' + repr(tape) + tape)";print('tape=' + repr(tape) + tape)

上节的思路和图灵机上自打印程序 AB 在高层的理念上有点类似，但具体实现上不太不一样，核心在于：

• B 部分要对 tape 的内容复制两遍，这在图灵机中是不需要的，因为图灵机中 A 部分的代码是会 往纸带（屏幕）上主动写内容的，因此 B 只需要反推出那些内容然后继续往纸带添加它自己的一份即可。
• 但在 python 中，A 部分不会朝着屏幕写内容，它只会向 tape 这个内存区添加数据，所有的打印 工作都集中在 B 部分，于是 B 必须把原本图灵机上 A 主动执行的打印也接手过来，因此要打印两份。

此外，上一节中 B 部分用到了 tape 作为代词，引用 A 部分的内容，从而保持了 A 部分作为模板还是能放在 B 前面。它接近自然语言中以下句子：

"将以上句子打印两遍，第一遍用引号括起来"
将以上句子打印两遍，第一遍用引号括起来

B 部分的功能是把带引号的数据里引号去除掉（类似 python 里 print）并复制两份，然后借助 "用引号括起来" 这句话把引号加上去（类似 python 里 repr）

如果把代词替换成“以下”则变成：

将以下句子打印两遍，第二遍用引号括起来
"将以下句子打印两遍，第二遍用引号括起来"

B 部分别放在了前面，所以这对于自然语言，写起来很简单，但 python 不支持先引用后定义，以下会报错。

print('tape=' + repr(tape) + tape);tape=";print('tape=' + repr(tape) + tape)"

不考虑精确性，程序大概是：

print(2*"print(2*")

print(2*print(2*

但这里还会遇到括号，引号缺失问题。尝试中发现我们还是要分离出 A, B 两部分，因此不能直接用 print 去作为最外层的函数， 经过多次调整，最终发现以下程序是可行的（随机性还是很大，下一次不一定能写出来）：

(lambda x,y: print(x+str((x,y))))('(lambda x,y: print(x+str((x,y))))', '1')

(lambda x,y: print(x+str((x,y))))('(lambda x,y: print(x+str((x,y))))', '1')

不考虑精度，可以写出很多接近自打印的程序，如下，但之后更多是在和目标语言设计的引号和括号机制做斗争，这是写出精确自打印程序最麻烦的点。

(lambda x: print(x+repr(x)))('(lambda x: print(x+repr(x)))')

(lambda x: print(x+repr(x)))'(lambda x: print(x+repr(x)))'

总的来说，自复制在理论上看上去简单，但要真正实现，会遇到非常多的细节问题：

• 在哪个编码层级打印出“自己”，如果打印底层编码，会稍微更简单一些。

• 如果要在源码层打印出自身，要知道哪些字符或者方法可以让数据和和打印结果变得一样， 类似寻找编码中的不动点，比如：

  repr('print')
  

  'print'
  

  否则会陷入编码上的无限递归（要打印出 print, 需要 print(print), 继而又要 print(print(print))），

幸好实践中几乎不需要写这类程序，前文说到过，现代计算机自带有寻址以及能够控制指令加载区域（操作系统提供）的功能，天然就能访问自己的程序。

• python 里是如何判断两个字符串相等的？

if (state, tape[idx]) in d:

以上语句根据 d 的不同会有不同实现，如果 d 是 hash 表，那么 (state, tape[idx]) 会被编码成 一个数字，然后去 hashmap 里检查这个位置是否有元素。

然而，规约到最底层，最终实际是二进制串的对比，比如 a==b 规约为 101010 和 000101 是否一样的比较，它在 cpu 里执行的是一个 CMP 指令，它实际是逻辑异或 XOR 操作：

def binary_xor_compare(bin_str1, bin_str2):
    int1 = int(bin_str1, 2)
    int2 = int(bin_str2, 2)
    xor_result = int1 ^ int2
    return xor_result == 0

bin_str1 = "101010"
bin_str2 = "101010"
bin_str3 = "000101"

print(binary_xor_compare(bin_str1, bin_str2)) 
print(binary_xor_compare(bin_str1, bin_str3))

True
False

比较的结果会体现在 CPU 的零标志（ZF）位。之所以能够这么比较，是因为我们在程序里写下的每一个字符都被精确编码了，这是一种对表征精心设计的结果，从而可以把比较的规则转换到门电路的设计上，这种思路的理论源头可能来自于克劳德・香农（Claude Shannon）于1937年发表《对继电器和开关电路中的符号分析》，这比图灵构思出机器还要晚， 距离 1946 年第一台电子计算机真正造出来，还有近 10 年的时间。而且根据书本介绍，1945 年，图灵自己也参与了计算机的设计和制造，他参考了冯·诺伊曼对 EDVAC 的设计报告撰写了 ACE 机器的方案，但工程上还是没有造出有实用价值的计算机，因此计算机发明本身虽然受到了图灵论文的启发（包括通用机的可能性、指令本身可以被编码而当作数据来处理），但在工程技术的发展上实际和图灵关系不大。

因此可以说，即便是字符的识别，也并不简单。这种简单仅仅是因为人类进化了几十万年（不考虑更早的其他形态的进化）后，突然意识到自己似乎天生就能做这种事情时出现的情绪上的简单感觉。

• 人是如何识别状态和次品的？

前文的 python 模拟器把机器内部的状态和机器外部的纸带都作为相同的 python 内部对象来处理，最终规约到一样的二进制编码。但对于人，这两个对象是不一样的，一个是内部的心理状态，另一个是外部视觉识别（或其他感官）的对象。

如果流水线上，人的每一步操作是实时按照操作手册进行的，或者完全熟练了整个流程，不需要做完一个动作就努力思考下一个状态是什么，那么人可以完全处于无意识的识别和操作情形下，这时候只需要考虑外部的模式识别问题。

那么识别一个产品是否为次品是简单的吗？或者说，如果图灵机的纸带上是一只猫的图片，甚至是一个时刻的汽车前置摄像头里的视频，读写头如何解析这些画面和采取下一个动作？

由于长期的进化，这些能力对人来说仍然可以说简单的，但一个完全无人的流水线和全自动自动驾驶在字符识别被认为是简单之后的 80 年还没有完全实现（可能 Sora 会使得识别次品变得更简单）。

• 写入或移动简单吗？

  对于数字计算机，写入和擦除移动都是简单的，但对于实体中复杂的运动，仍然不简单。

• 状态转移简单吗？

  如果规则是确定的，那么是简单的，问题在于规则是如何制定的。

• 规则定制简单吗？

  制定规则实际就是编程，它并不是简单的活动，况且还有更多是无法用确定性语句编写出的规则，比如自动驾驶的规则，也就是说，一些现实场景下，不单单读写头得是一个复杂的模式识别机器（比如神经网络），整个转移规则的确定、运动方式（比如概率性转移），很可能都需要用其他结构来完整实现，且这个系统要有学习的能力。这可能也是 1948 年图灵写了一篇名为 “Intelligent Machinery” 论文的原因， 其中提到另外一种通用机器的实现构想，通过神经网络来模拟人脑，并且像儿童一样能够被教育。

然而，图灵显然不被这些问题所干扰，也不能被这些问题困扰（尽管他花了近 3 页来说服大家图灵机至少可以模拟人的数学推理的那部分思维），排除这些问题而抽象出符号计算中最核心的本质才是能够宣告通用计算存在的关键，而排除干扰的关键在于目标的明确性 – 解决可判定性问题。

这种“替换-生成”的模式不断在其他地方被发明或发现。

发明的举例：

• Chomsky 0 型文法：它的规则就是一套 a->b 的规则，根据这个规则可以把字符串里的 a 替换成 b. 这里 a,b 不是单独的字符串，而是可以任意复杂，比如 1abc1->1ac1 规则表明，如果 abc 夹在两个 1 之间，其中 b 就可以被消除。
• 元胞自动机：根据某个当前网格里周围网格状态，当前网格变黑或者变白。（替换颜色并生成新格局）
• 神经网络：麦卡洛克和匹茨 1943 年发表的 "神经活动内在概念的逻辑演算" 论文，论证某些神经网络可以构造出门电路，最终神经活动可以等价于图灵机。

发现的举例： 物理世界里很多现象都是这种生成替换模式，因此广义上看，通用计算无处不在。

• 对于宏观或中观事物，由于运行速度太慢，我们看到的相当于只是有限几个转移规则执行的过程。 而根本看不出自然正在计算什么。但从整个地球或宇宙历史的尺度上看，那么或许可以看出这个机器在运行什么 样子的程序（比如任何一个生物从孕育到死亡的过程，或者更大尺度的进化过程）。
• 对于微观的运动，由于速度是很快的，因此在许多场景下微观物体可能也在进行通用计算， 最终展现出了我们所看到的世界（可以搜索 Stephen Wolfram 关于通用计算无处不在的观点）。

这种过于宽泛的扩展引出了潜在的问题：

• 元胞自动机如何读取其他元胞自动机？
• 神经网络如何把其他网络的整个描述（或权重）作为输入？
• 0 型文法如何能构造一种生成其他文法的文法？

由于图灵是对人用铅笔做题进行建模，因此图灵机天然带有人机交互性质，它可以读取外部输入，而外部输入的形式就是编码在纸带上，和它打印的结果的形式是相同的，这使得机器可以处理其他机器的描述，也可以在一台机器上编写不同功能的程序。

因此，图灵机之所以强大，不仅在于其计算能力，还有它输入输出形式的统一，中间计算过程的统一（所以可以相对容易地用计算历史的思路实现通用机），以及人交互干预灵活性。

而元胞自动机、神经网络和 0 型文法虽然理论上和图灵机计算能力等价，但在其他方面似乎都有些局限。