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

读《图灵的秘密》

2024-05-30 四 22:15 2024-07-16 二 15:05

本文可以看作是对 《图灵的秘密》一书阅读过程中思考的记录。

《图灵的秘密》详细解读了图灵在 1936 年发表的名为 “论可计算数及其在判定性问题中的应用”的论文。因此,这实际上是一部具有考古性质的学术著作,但由于作者在其中加入了许多历史人物故事和背景知识简介,使其带有科普或人物传记的色彩。

书本实际已经相当详细,不过光读文字,还是容易忽略一些细节从而导致理解偏差, 因此在阅读过程中用 python 实现了论文里描述的图灵机、通用机以及一些可实现的指令改写程序 demo , 算是复现了图灵论文里大部分可以被代码复现的内容,以减少自己用纸和笔去模拟图灵机的频率。

对于无法用代码实现的部分,则用自己的语言对书中已足够详细的内容做一些概括性总结或重新复述,并将自己以前学过的部分计算理论的知识放在历史背景中,做一些比较和延伸。

这次阅读带给了我一些观念上的变化:

  • 过去对图灵机的认识,就是一个简单的带读写头、可以在无限纸带上来回移动和读写的装置。 要在这台机器上编写出复杂程序是非常困难的,以至于我从来没有尝试认真思考过这个简单的机器为什么能等价于现代计算机, 而只是接受流传的观点。

    但实际上,图灵在描述完机器结构和底层转移规则(可以看作汇编或机器指令) 后就马上给该机器设计了编写指令的缩略表(其实是一套遵循上下文无关文法的高级编程语言,风格是偏函数式的,且混合了底层语言,有点类似内联汇编,只不过那时候还没有这些概念),然后用这个语言编写了通用机,也就是一个机器指令的解释器, 并以此说明机器能够模仿执行对角线方法的过程,模仿谓词逻辑推理、lambda 演算,从而可以模仿人的符号推理过程。 他的论证是非常“垂直”而且“彻底”的。

  • 图灵对计算机体系设计和工程上的影响是很小的,甚至可以认为几乎没有。

    他更多是证明指令和数据可以被同等看待, 因此能够计算加减乘除的机器实际也能解析指令本身(只要对指令进行适当编码),从而说明了通用计算的可能性。 冯·诺伊曼吸收了这种思想,设计出第一个数字计算机的结构(这是个集体性工作,不过报告是冯·诺伊曼写的), 而之后计算机的发展更是集体智慧的产物。

  • 图灵机和 lambda 演算差别并不太大,但图灵的内涵更为丰富。

    图灵设计的高级编程语言本身就有函数式编程的感觉,而且是真正的编程语言, 因为有想象中的机械装置作为最底层的解释器,将函数描述的状态翻译成转移规则这种机器指令。

    丘奇的 lambda 演算是纯数学的产物, 它对应的计算模型实际是字符串的替换,而这种替换在那个时候完全只能依靠人脑作为解释器。 如果非要套上现代概念,那么 lambda 演算即是编程语言又是计算模型, 不像图灵那样把计算和计算的描述分离开。在 lambda 演算模型上要能够把描述和计算模型分离,也许是 LISP 出现后的事了(再过 20 多年)。 实际那个年代,要描述复杂一点的形式对象,都需要借助函数的语言,而且是递归性质的函数,哥德尔就用这种方式,论述了那些能够处理数字的函数实际可以等价于处理逻辑字符串(逻辑推理就涉及字符串的替换、代入、生成等等)。所以,图灵和 church 都用了函数的方式来描述计算过程,并且都要说明他们各自模型可以用来模拟一阶逻辑的推导。

    但个人还是觉得图灵的内涵是更加丰富的,因为他指出函数变换或者逻辑推理这种高层的思维过程, 可以还原到字符串的查找替换上,而这些操作进一步分解,能继续还原到机械的动作和状态切换上, 这种还原为其获得了更大的灵活性,比如把 lambda 表达式写到纸带上之后, 就可以证明这台机器能够用字符串查找、替换算法来完成人脑能做的 lambda 演算,可以用机器去表示无限精度的数、可以实现解析纯字符串指令的通用机、还能用机器的有限状态去类比人的有限记忆等等。

    为什么可以在一篇论文里说明机器等价于这么多不同领域的对象?

    因为纸带、读写头以及状态转移机制的解耦,使得可以灵活地对纸带上的对象设计编码,lambda 演算要表达出整数都是比较费劲的,必须对整个表达式结构进行编码,而表达式结构中牵涉到了计算过程,因此设计编码时就要考虑演算规则对编码意义的影响,很需要技巧。而图灵机在还原过程中,编码的意义到机器规则层面已经完全被消解了,读写头要注意的只是看到的唯一符号的形式,根据形式去转移规则里匹配,而每条转移规则也无须关心其中符号的高层意义, 这种意义只体现在算法设计和最终纸带结果的解释上,而这些和机器结构是无关的。

图灵机模拟器 TM

希尔伯特判定性问题指的是:是否存在一个有限的确定性过程(即一个算法),给定任何数学命题,算法即能判定该命题是真还是假。

该问题提出的时候,其中提到的“有限的确定性过程”的执行者显然应该是人,因为那时候并没有能够进行推理的非人类机制。

因此这问题的换一种说法就是,是否存在一个极其聪明的人(或者把历史上所有人类看作一个对象,称为智能体),给定一个数学问题,智能体第一步先去检查这个问题能不能解,如果能解,那么再去考虑如何求解。如果不能解,那么可以放弃这个问题。

判定性问题就是判断问题能不能解这一步。

一般情况下,人都是拿着纸和笔开始去琢磨某个命题是对的还是错的,而在推理的时候,都是从给定的一组前提出发,根据推理规则向前推进(以欧几里得几何为模板的形式化方法)。

为了解决这个问题,需要把人类做推理的过程精确描述出来,图灵把这个推理过程分解到最简单的几个步骤,以此设计出了一台理论上的机器,论文里叫作自动机(a-machine),后人称其为图灵机。

python 模拟实现图灵机代码见:

numbers/turing_machine/op_extend.py at main · metaescape/numbers

以下做简单的说明:

机器包括一条单向的无限长的纸带,用以下 list 表示,尽管 list 是有限的,但如果机器需要更多纸带,随时可以扩充,因此它是潜在无穷的。

tape = ["$","$",0,"_",1, "_",0]
idx = 0

纸带的前两个元素一般都是 "$", 用做起始标志。之后的格子中:

  • 偶数位置内容是不可更改的(称为 Figure 格),用于打印最终要显示的 0 和 1 序列,它更接近现代计算机里划分给屏幕的内存区,因为最后确定图灵机输出时正是从 Figure 区里提取信息。
  • 奇数位置是可以更改的(称为 Erase 格),用来做辅助标记,接近现代计算机里的可读写的内存。

机器还有一个读写头,可以用额外的变量 idx 来表示,它所指的格子就是机器当前所能看到内容, 初始值默认为 0 。

读写头可以执行 L,R,N 三个动作,对应 idx 减 1, 加 1 和不变。如果 idx 已经在最左端,要继续左移的话,可以报错也可以维持不变。这些只是图灵所设定的极简规则。

此外,机器还有一个变量 state 来记录当前的状态。

机器的静态描述是一组 ("b","_","0","R","q") 形式的转移规则。

这条规则表示的是,如果当前状态为 "b",且读写头看到的字符 tape[idx] 为 "_" (表示内容为空),那么写下 0, 并且读写头右移,状态切换为 "q" 。

具体执行的时候,可以把以上规则写成 python 字典,便于快速查询:

rule = ("b","_","0","R","q")
d = {}
d[rule[:2]]=rule[2:]
print(d)
{('b', '_'): ('0', 'R', 'q')}

这个规则如此简单,以至于模拟器的核心实现就是根据 state 和 tape[idx] 作为 key, 去转移规则表里查询,然后根据规则去改变 tape ,idx 和 state, 这个模拟器核心逻辑就是:

tape = ["$","$",0,"_",1, "_",0]
idx = 3
state = "b"
def step():
    if (state, tape[idx]) in d:
        symbol, action, state = d[(state, tape[idx])]
        tape[idx] = symbol
        if action == "L":
            idx -= 1
        if action == "R":
            idx += 1
step()
print(tape,idx,state)
['$', '$', 0, '0', 1, '_', 0] 4 q

具体实现中,这些代码封装在一个类里,加入一些辅助打印功能,并且支持更丰富的指令的解释,比如动作部分可以支持多个连续动作:

("b","1",["L"],"p")
("b","*",["0","R","R","R"],"q")

以上图灵机执行后的行为是,如果在 "b" 状态下,看到字符 1, 则向左移动并转到状态 "p", 而如果看到其他任意字符(用 * 表示),则打印 0, 并且向右移动三次,并转到状态 q.

图灵用这种机器来打印无限长的 0 1 序列,它实际是一个 0 到 1 之间小数的二进制编码,比如 1111… 其实就等于 1 ,因为解码时会在最前面加上小数点,全 1 序列对应的是 0.11111…, 二进制中,它的极限就是 1 。正如十进制中 0.9999…=1 一样。

而打印全 1 序列的图灵机只有一条规则:

("b","*", ["1","R","R"], "b")

对于各个数位之间有明显规律的序列,比如这个全 1 序列,或者 0101 交替的序列(对应的是有理数 1/3),用纯粹 ("b","1","0","R","q") 形式的指令来编写是相对简单的。

但对于那些 0 1 模式非常复杂,非常“随机”的序列,比如根号 2 的二进制表示, 用这种方式来编程是很复杂的(见代码文件中的 test_sqrt_root_machine 函数) 。

计算 sqrt(2) 并不是直接在这种底层的 0,1 序列上找规律并按规律延伸,而是 先要把 0 和 1 映射到“有理数”这个高层概念中,然后对有理数去做乘法,乘法相对 0 1 序列或者读写头左右移动同样是非常高层的操作(所谓高层就是说它应该包含了大量简单移动规则),而为了计算 sqrt(2), 需要在这种高层操作上反复迭代,以无限逼近这个无理数。

因此这要求能够在底层读写头移动和高层的运算(如乘法)之间建立联系,这就需要设计新的语言。

图灵机高级语言编译器 Compiler

numbers/turing_machine/abbreviated.py at main · metaescape/numbers

为了避免在这种类似汇编的层面进行编程,从而写出更复杂的指令集合(也就是计算某个数的图灵机),图灵对底层的“汇编语言”进行了抽象封装,用函数的方式来定义状态,比如:

find(0) ["R","R"] mark_to(1,z)

这表示,在纸带上找到第一个 0 之后,向右移动两格,然后对接下来的 0 用 z 进行标记,直到找到下一个 1 。

也就是说,如果当前纸带内容如下(每个数字后有一个空格,用于写或者擦除标记):

[1,"_",1,"_",0,"_",0,"_",0,"_",1,"_",1,"_"]

那么执行完以上指令之后,会变成:

[1,"_",1,"_",0,"z",0,"z",0,"z",1,"_",1,"_"]

这个过程实际由很多条底层指令共同完成。上节实现的图灵机模拟器 TM 能执行的“机器语言”只是以下形式的

("b","*", ["1","R","R"], "b")

它无法直接执行高层的指令,把高级语言翻译成机器可执行语言的工作实际是人脑完成的,图灵在论文中给出了一些高层原语翻译成底层指令的说明,读者心领神会。

abbreviated.py 中则用 python 实现了这种高级语言到机器语言的编译器,然而,严格来说,这不是一个完整的直接去翻译以下风格语句的编译器:

find(0) ["R","R"] mark_to(1,z)

而是用 python 内部的类来构建 find 和 mark_to 这种高层状态:

class Find(abbreviatedTable):
    def __init__(self):
        super().__init__()
        self.add_transition("*", ["L","R"], Mark_to("1", "z"))

然后执行:

SkelotonCompiler.reset()
e = Find()
table = SkelotonCompiler.compile()

得到的 table 就是底层的转移规则集合,具体见文件里的各个 test 函数。

有了编译器后,图灵先用它写了一套处理纸带数据的函数库,比如以上的 Find 就是他写的第一个函数。

由于图灵机能操作的对象就是一维纸带,因此这些操作函数的行为接近字符串操作,比如标记、拷贝、比较、拼接等。 可以用两种现代视角来类比他写的这些状态函数库:

  • 硬件视角: 类似构造了一个包含逻辑控制单元的 CPU 。因为最初的例子中,比如打印 0101 交替的序列的图灵机,相当于做了一个只能计算 1/3 的元器件(ALU 或比 ALU 更弱的专用计算设备,如加法器,乘法器),可以单独做出很多类似的机器,比如打印计算 1/4, 1 等等,这就类似最基础的计算器,只能算简单的一些值。 但有了这个函数库,就可以更方便地操作复杂的对象,比如操作内存地址。

    图灵将用这些器件构造一个通用的 cpu 。

  • 软件视角:写了一个 libc 库,将用这个库继续写一个解释器。

将图灵机编码到纸带上的汇编器 Assembler

图灵想要说明,存在一套转移规则,运行起来后可以解析其他机器的转移规则,并按规则行动。也就是存在一台可以模仿 其他机器的通用机。

那么这里的关键一步就是如何把其他机器写到纸带上,因为图灵机能够看到的世界只有纸带。

于是需要把机器的描述本身作为数据,也就是对 ("b","_","0","R","q")("b","_",["0","R"],"q") 形式的指令再编码,使得能够放在纸带上,图灵定义的标准描述类似于现代计算机里程序的可执行码。因此要实现一个类似汇编器的工具,记为 Assmbler。

numbers/turing_machine/encoding.py at main · metaescape/numbers

模仿其他机器的通用图灵机 U

有了编译器、编码规则、汇编器,就可以用高级语言写出针对图灵机编码的解释器,即通用图灵机 U:

numbers/turing_machine/universal.py at main · metaescape/numbers

注意整个流程是怎么串联在一起的:

  • 首先 TM 是一个用 python 实现的图灵机模拟器,它实际也是一个通用机,给定任何功能的符合格式的指令集, 它都能模拟运行。但这是 python 在模拟其他机器,而不是某个图灵机本身在模仿其他机器。
  • 接着用针对图灵机的高级语言编写一个程序,这个程序经过编译器 Compiler 翻译成一系列 ("b","_",["0","R"],"q") 形式的指令,这些指令的集合就是通用图灵机 U,但真正要在 python 中运行起来,需要把 U 传给 TM, 得到类似 TM(U) 的对象,然后调用 TM(U).run() 运行起来。
  • 但 U 为了模仿其他机器,需要看到纸带上其他机器的编码。比如假设用高级编程语言编写一个 计算根号 2 的程序,该程序经过编译器 Compiler 翻译成一系列 ("b","_","0","R","q") 形式的指令,称为 sqrt2,这些指令可以直接被模拟器 TM 解析,执行 TM(sqrt).run() 后就会无限地计算 srqt2 , 而执行 TM(sqrt).run(1000) 则只计算前 1000 步,得到根号 2 的近似值。

    但以上只能被 python 实现的 TM 所执行,而不是被模拟的图灵机 TM(U) 所执行。

  • 为了使得 sqrt2 能被 TM(U) 执行,需要用 Assmbler 把以上 sqrt2 程序的 五元组指令集合翻译成一长串字符,装载到 TM(U) 的纸带上再执行。即 TM(U).load(Assmber(sqrt2)).run() 。

U 的实现基本是照着书本里代码重写的,而书本对原始论文做了少量的修正。这意味着在 1936 年计算机尚未存在时,图灵就在三页纸上,用自己发明的高级编程语言在自己想象的机器上,以不到 50 行代码写出的图灵机的通用解释器和详细的注释说明,而且几乎没有逻辑上 bug (书本里的修正基本是一些印刷错误或遗落的函数的补充),令人惊叹。

由于通用机是用计算历史去和指令集进行字符串匹配求差异的算法(因此只需要前面准备的那些通用的字符串处理函数),其计算效率是非常低的,比如如果直接在模拟器 TM 上执行计算 1/3 的程序(打印 010101 交替的序列),每执行一步就多获得了一个二进制精度,执行 5 步就可以得到 01010,但把这个程序编译成标准描述放到通用机 TM(U) 的纸带上后,执行 50000 步才能打印出 01010 。

因此实际上,这里实现的通用机除了能打印全 1 或者 0101 交替这类序列的前几位,现实中做不了任何事情, 但图灵在这之后要用它去模拟整个数理逻辑推理,计算 tan(1) ,证明不可判定、模拟 lambda 演算函数式编程 …

通用机的构造,是人类历史上第一次表明,理论上存在一种能够模拟人类计算过程的“智能”的机械装置,剩下的几乎都是工程技术问题了(当然每个具体的工程技术背后又有大量的理论去划定边界,比如算法复杂性理论等)。

本章能够用 python 代码模拟图灵机并进行检验也是因为 python 是一种通用机。

对角线法则和规约

判断是否为非循环机器

图灵约定了 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 个数的纸带分区和变化如下:

写入 n   <D> R(n-1) d' n
解码 n   <D> R(n-1) d' <M>
执行 D u <D> R(n-1) d' <M>
执行 M   <D> R(n-1) d' <M>
写入 n+1   <D> R(n-1)+1 d' 新增一位 n+1

问题在于,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 一定能模拟这个机器,不会在那个机器上陷入循环。

规约和图灵机改写器 Translator

图灵在说明无法构造一个判断某个机器是否为非循环机的机器之后,又继续证明不存在一个判断某个机器是否打印过数字 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 状态。

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

停机问题

论文里,图灵机的第一个应用是为可计算数贴标签:可计算数是一个实数,它理论上是无限数位的,是某种极限的结果,即便是 0.1 它也要被看作 0.1000… 的极限。而图灵机可以为这种无限的对象贴上一个有限的标签,因为图灵机的转移规则是有限的, 可以转成一段有限长的描述。

当后人把图灵机应用在判断字符串上时,实际是把图灵机作为语言的标签。

语言是符合某种模式的字符串的集合,比如回文是一种语言,包含奇数个 1 的字符串也是一种语言。而上文刚提到的全 0 字符串也是语言,比如 "0", "000" 就是“全 0 语言”集合的成员。

如果某个机器,在任何字符串下运行都能停机,并且当输入的是属于特定语言 A 的字符串 w 时, 机器进入 accept 状态,否则进入 reject 状态,那么这台机器就可以用作语言 A 的标签,或者叫作判定 A 的机器,以上提到的 ALL0 就是判定全 0 语言的机器。图灵可判定的等价说法有:递归语言,可解语言,能行,可判定,可计算语言。

而如果某个机器,不一定在所有输入上停机。如果输入的是属于特定语言 A 的字符串 w, 机器进入 accept 状态,否则可能 reject 也可能无限循环。那么称该机器可以识别 A 。图灵可识别语言的等价说法有: 递归可枚举,计算可枚举,半可判定,半可计算。

判定某个语言的机器只是所有图灵机的一小部分,而所有图灵机数量是可数无穷,因此在该应用场景下的图灵机是可数无穷的。 然而语言的数量是不可数无穷的,因为假设所有语言都使用字典 \( \Sigma \) 里的字符,那么包含所有有限字符串的语言记为 \( \Sigma^{*} \) ,它是一个包含可数无穷个字符串的集合,假设字典只包括 0 和 1,那么可以用以下方式罗列出该集合里所有字符串:

- 长度为 0:
1: 空串字符串 ""
- 长度为 1 的串:
2: "0"
3: "1"
- 长度为 2 的串:
4: "00"
5: "01"
6: "10"
7: "11"
- 长度为 3 的串:
...

而所有语言的集合,实际是 \( \Sigma^{*} \) 的所有子集组成的集合, 也就是 \( \Sigma^{*} \) 的幂集,它的大小和自然数的幂集大小是一样的,也和实数集大小一样。 因为对于任何语言,可以用二进制的形式来表示 \( \Sigma^{*} \) 中的某个字符串是否在该语言中,比如 0110100… 表示 "0", "1","01" 在该语言中,而每个表示实际是无限长的二进制序列。

因此,正如可计算数应用下,一定存在一些实数是图灵机无法计算出来的,语言判定应用下,一定存在某些语言是图灵机无法判定的。

图灵并没有停在“机器的描述是可数无穷,从而有些实数不可计算”。他还希望描述出不可计算的数,并说明,如果想要构造这个数,就需要一台能够判定其他机器是否循环的机器 D ,在此基础上可以构造出一台行为逻辑上出现矛盾的机器, 而实践中是无法构造出逻辑错误的机器的。

同样的,我们不想停在“机器的描述是可数无穷,从而有些语言是图灵机无法判定的”上。我们还希望描述出这种语言,并说明,如果想要构造这个语言,就需要一台能够判定其他机器是否识别给定字符串的机器 D,在此基础上 可以构造出一台行为逻辑上出现矛盾的机器,而实践中是无法构造出逻辑错误的机器的。

如果要构造对角线,那么它应该是:

All TMs 1 2 3
M1 1 0 1  
M2 0 1 1  
M3 1 0 0  
       

这里 1,2,3 是上文提到的字符串在 \( \Sigma^{*} \) 中的按长度罗列之后的序号,如果 Mi 可以接受编号为 j 的字符串,那么表格里 i,j 下标的值就是 1, 如果不是接收状态,那么标号就是 0, 如果不停机,那么就用 None 表示。

假设以上表格只罗列出那些对任何输入都会停机的图灵机,表格内容里便不会出现 None ,为了能够罗列这样的图灵机,需要有一个可以判定某个图灵机 M 在任意输入下是否均会停机的机器 D ,注意这个机器 D 只需要输入 <M> ,而不要输入特定的 w, 因为它要判断的是 M 是否在所有输入上都停机。

基于 D 可以构造机器 H,它能够判定通过对角线所构造的语言,即如果 M3 在 3 上是 0,则 H 在 3 上是 accept, 否则是 reject 。构造方式为:

  • 给定任何输入 i, 从 1 开始遍历,解码并将结果传给 D, 以此找到第 i 个会停机的图灵机 Mi。
  • 模拟 Mi 在编号为 i 的字符串下的的行为,由于它一定会停机,那么最终会进入某个状态,如果这个状态是 accept, 那么 H 进入 reject(或 accept) 状态。否则进入 accept (或 reject) 状态。

可以看到,这台机器是会停机的,因为无论什么情况它都会进入 reject 或 accept.

现在问题是,输入机器 H 所对应的整数编码 int(H) 时:

  • 机器 H 要从 1 开始遍历,当它去检查第 int(H) 号会停机的机器时,它就找到了 H 自己
  • 将 H 传给 D 做判断,根据以上分析,由于 H 是会停机的,H 要去模拟 H 在 <H> 字符串下的行为,于是它要重头去枚举 1 开始的所有数,那么 H 永远不会停机,这导致了矛盾。

所以我们描述了一种语言,没有图灵机能够识别,同时我们知道,不可能存在一个判定其他机器在任意输入下是否均停机的机器 D.

这个过程有一个更简单的版本,假设存在一个机器 D 它能判断那些没有任何输入的机器 M 是否停机,那么可以构造机器 H, 它接受其他机器的描述 <M>:

  • 先调用 D 来检查 <M>,如果 M 停机,则 H 进入以下 loop 状态:

    ("loop","*","","N","loop")
    

    否则 H 直接进入 accept 状态

  • 现在问题是,如果把 H 自己的描述 <H> 交给 H, 会有什么结果:
    • H 调用 D 去检查 <H> ,如果 H 停机,那么 H 下一步就陷入了死循环,也就是不会停机,但 D 刚检查完 <H> 说它会停机,这导致矛盾。
    • 如果 D 检测出 H 不停机,那么 H 马上就进入 accept 状态从而停机,同样导致矛盾

这个是大部分书本里介绍停机问题时介绍的版本,但是对角线和语言识别的性质更不明显了。

不可判定的语言

在形式语言理论里,一般会把对角线变成另外一个版本,它说明的是,由机器 M 的描述和它能接收的输入 w 构造的语言 <<M>,w> 是不可判定的(然后用规约的方式,再证明停机问题不可判定,同时还能说明 <<M>,w> 的补语言是不可识别,具体参考 8. Undecidability_哔哩哔哩_bilibili)。

即不存在一台图灵机 D, 给定任何图灵机 M 和任意输入 w, 如果 M 能够识别 w 则进入 accept 状态,如果 M 不能识别 w(可能不停机), 则进入 reject. D 所判定的语言就是 <<M>,w> 。

假定 D 存在, 那么构造出 H , 它接收另外一个图灵机的描述 <M>:

  • 将 <M> 交给 D 去判断 M 在 <M> 自己上是否会进入 accept 状态:
    • 如果是,则 H 进入 reject 状态
    • 如果不是,则 H 进入 accept 状态
  • 问题在于,当 H 的输入是 <H> 时, <H> 会交给 D 作判断:
    • 如果 D 说 H 会在 <H> 上进入 accept 状态, 那么 H 马上会进入 reject 状态
    • 如果 D 说 H 会在 <H> 上进入 reject 状态, 那么 H 马上会进入 accept 状态
    • 两者都导致了矛盾。
  • 于是不存在一台判定 <<M>,w> 语言的机器,或者说 <<M>,w> 语言是图灵不可判定的。

这个版本的对角线是修剪过的:

All TMs <M1> <M2> <M3> <H>
M1 acc rej acc    
M2 rej acc acc    
M3 rej rej rej    
         
H rej rej acc  

由于 D 的存在,可以挑选(实际还是一个一个遍历)出所有可判定的图灵机,从而找出图灵机描述作为输入情况下结束时的状态。

当遍历到 H 时,会发现它无法判定 H 自己。

这种做法只能在对角线上取反,而没法直接取对角线的值作为 H 的判断标准。

对图灵机进行限制的后果

图灵机尽管结构简单,但功能却异常强大,以至于会出现一些不可计算的问题。于是可以给图灵机增加各方面限制,看会出现哪些不同的机器以及这种机器能够识别的语言,这部分基本是自动机和形式语言里所讨论的内容。

  • 如果限制指令,只能向右移动,并且只能读取纸带上数据,那么称为有限自动机。

    有限自动机能识别的语言称为正则语言,正则语言也可以用正则表达式来描述,因此有限自动机可以识别正则表达式 所生成的语言。

    图灵机的“汇编语言”,即形式为 ("b","_","0","R","q") 的转移规则可以看作是正则的,每个位置都可以用 类似 [a-z]+ 形式的正则表达式来刻画。

    检查哪些语言不是正则语言的方法是泵引理,就像检查哪些语言不是图灵机可以计算的用的是对角线法则。

  • 如果限制图灵机只能从左向右读取纸带上的 Figure 区域,但可以在 Erase 区左右移动,且只能在最后一个非空 Erase 区上进行写入和擦除(即 Erase 是一个栈),那么得到的机器称为下推自动机 PDA。

    PDA 可识别的语言称为上下文无关语言(CFG),或 Chomsky 2 型文法所生成的语言(正如用正则表达式生成的正则语言一样),假设 M 是 PDA, 那么存在一台不会陷入死循环的图灵机,它能判断任意字符串 w 是否能被 M 识别。 这是编程语言中语法检查不会导致死循环的原因。或者说,CFG 文法检查是可判定的。

    图灵设计的高级语言是 CFG, 因为状态函数可以递归嵌套:

    find(0) ["R","R"] mark_to(1,z,read_to_erase0("success"))
    

    以上表示,找到 0 后右移两格,然后向右 mark 所有 0, 直到遇到 1 后进入到 read_to_erase0("success") 状态, 这个状态会擦除纸带上所有的 0 并且最终进入 success 状态

    检查哪些语言不是 CFG 的方法是 PDA 上的泵引理,就像检查哪些语言不是图灵机可计算时用的对角线法则。

  • 当规定读写头不能移出输入区或者输入区的某个常数倍,就得到线性界限自动机(LBA)。

    由于运动范围有限,所以它的完全格局是有限的,因此可以用计算历史的方式(会在下一节作更多说明)去验证一些性质。

    比如给定字符串 w, 用图灵机去模仿 LBA 在 w 上运行, 执行次数如果超过最大可能的完全格局数,说明就进入了循环,因此可以判断当前 LBA 不停机。

    于是 LBA 识别的语言都是可判定的,这些语言按 Chomsky 文法划分,对应的是上下文有关语言,或 Chomsky 1 型文法。图灵机可识别的是 Chomsky 0 型文法。

    注意对于语言的总结是 1950 年代 Chomsky 的成果了,部分内容可以参考另一篇文章 语法和语言解析

历史的重复:计算历史技巧的重复应用

通用机的实现技巧

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

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

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

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

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

一阶逻辑的不可判定证明技巧

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

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

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

Cook-Levin 定理证明技巧

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>.

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

其他语言上的自复制 API

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

重写一遍这个句子

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

以上句子中用到了自我引用的代词 "这个" 。然而原版的图灵机是没有 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

不考虑 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)

BA 形式的自打印程序

上节的思路和图灵机上自打印程序 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))),

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

从人到图灵机,再回到人

这部分在书本或者论文第 9 章里已经有许多描写。 总的来说,图灵认为人用一支笔在二维纸上进行运算的过程可以抽象成在一维的纸带上的简单行为。

人在计算过程中,只是根据注意力范围里的内容以及大脑里预设的一个计算规则从一个阶段进入到 下一个阶段,小时候学习乘除法时也是根据相应规则一步一步运算并熟练起来,以至于之后可能忘记自己正在做这种“机械”操作。 因此图灵机里的状态被称为 m-configuration, 这个 m 可以是 machine 也可以是 mental, 表示的是一种记忆里的模式。

图灵机的运行是一个 “状态和字符识别”->“写入或移动”->“状态转移”的循环,由于这台机器是理想中的, 我们可以说这个循环中每个步骤都是简单的,毕竟上一章用 10 行不到 python 代码就模拟了,代码如下:

def step():
    if (state, tape[idx]) in d:
        symbol, action, state = d[(state, tape[idx])]
        tape[idx] = symbol
        if action == "L":
            idx -= 1
        if action == "R":
            idx += 1

同样,许多车间上的流水线工人大体是按照某种状态转移规则工作的:识别产品,对其进行操作(贴标签或者因为它是次品而从流水线取下),然后回到等待检查的状态,这份工作抽象成图灵机指令就是:

("检查", "次品", ["下架"],  "检查")
("检查", "正品", ["贴标签"], "检查")

但本节要问的是,哪一步是简单的?它们真的简单吗?

识别简单吗?

  • 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 页来说服大家图灵机至少可以模拟人的数学推理的那部分思维),排除这些问题而抽象出符号计算中最核心的本质才是能够宣告通用计算存在的关键,而排除干扰的关键在于目标的明确性 – 解决可判定性问题。

从数理逻辑到图灵机和 lambda 演算

上一节是从人的角度来看待图灵机,这会引入大量的问题,获得启发,但更可能的是迷失。

除了依托于人思维过程的直接类比, 由于数学的推理过程已经被弗雷格、怀特海、罗素等人证明,可以用一阶逻辑描述几乎所有数学命题, 而定理的证明也可以“无意义化”,变成从初始字符串(公理)不断进行机械地形式变换搜索过程。

因此图灵还有别的方式来说明自己的机器是可以做数学证明的,对于任何一个数理逻辑里能够被证明的公式,都可能在图灵机上被自动证明出来。

图灵在论文里几乎没有任何解释就声称这个程序 K 是存在的,并且继续用它做了很多事情。本节对这个程序 K 的存在性做一点补充说明。

  • 这个程序和通用机的实现是相似的,首先要将所有数学定理和推理规则都编码成能够写在纸带上, 而只要数理逻辑里所有符号个数是有限的,这与转移规则的编码是相似的。
  • 数理逻辑中,进行推理证明的核心规则称为演绎推理(modus ponens),它是一种“自明的”公理性质的规则。即如果已知命题 A 以及 A->B, 那么可以得到命题 B.
  • 实际上,图灵机的运作本身就是遵从这种形式的规则,我们可以把 ("b","_",["0","R"],"q") 写成:

    (b "_") -> (['0', 'R'] q) 
    

    那么任何一个时刻,给定状态和当前字符作为前提 A, 去查找转移规则 A->B 获得的 B 就是读写头要做 的动作和下一个状态。

    因此既然可以实现一个通用机,它能够解读转移规则,从而模拟其他的图灵机。 那么也就存在一个数理逻辑命题生成机 K, 在初始纸带上写下所有公理的字符串(就像写下其他图灵机的转移规则一样,其中有许多 A->B, D->X 之类的命题,同时还包括 A,B,C,D 这样的命题),然后 K 可以用类似宽度搜索的方式,对所有公理的子集 分别应用一次 Modus Pones 规则(应用方式和通用图灵机的是一样的,都是字符串匹配), 其中大部分组合是不会得到任何命题的,但有一小部分会得到结果,比如 [A,A->B] 会得到 B, [D,D->X] 会得到 X. 将 B 和 X 写入纸带,然后再把当前纸带上所有公理和定理构造出幂集,以组合出所有可能的前提条件,如此迭代。 那么对于那些逻辑上可以被证明的公式,总会在某一步被遍历出来。

  • 然而,这里可能会有疑问,难道数理逻辑的推理只有这个规则吗?

    确实,逻辑证明中,除了 modus ponens 之外,还有替换规则,这类似变量替换,比如假设有命题 (4/2)=2, 而当前有一个公理是 x=y->y=x (等式的对称性公理), 这时候 (4/2)=2 和 x=y 在字符上并不匹配,图灵机如何得到 2=(4/2) 这个命题?

    做法是,把 x=y->y=x 替换成当前纸带上出现过的所有变量或常量的组合,那么由于 (4/2) 和 2 都存在, 那么一定会得到 (4/2)=2->2=(4/2), 这显然在以上指数爆炸构造幂集的复杂度上继续加上了一层指数,但它在 逻辑上是可行的。

而说到替换规则,就需要引入 lambda 演算,这是图灵博士期间的导师 Church 提出的一套形式化变换规则,他先是定义了函数这种特殊的字符串形式,然后定义关于这类字符串的两条变换规则(就像图灵定义了状态转移规则一样),称为 alpha 变换和 beta 规约。

  • alpha 变换:对于任何函数,如 \( \lambda x.x+1 \) 等价于 \( \lambda y. y+1 \)
  • beta 规约:如果有另一个字符串拼接到某个函数字符串的末尾,比如 \( \lambda x.x | 3\) 。(这里用 | 表示拼接操作)那么可以将函数里 x 替换成 3, 并且把首位都消除掉,也就得到 \( 3 \).

可以看到,lambda 演算的过程实际可以看作一种 “组合-消除” 循环,只是带着“函数”这种数学对象的语义光环, 而形式化本身就是一个去意义的过程,所以不需要过分关注其“函数”的语义。

这种“消消乐”的核心就是替换(也包括生成,因为替换之后就生成了新的对象)。

也就是说,图灵和丘奇二人,分别摘取了数理逻辑推理中“演绎推理”和“替换”两大规则,以之为核心,各自发展出一套计算法则。可以想象,图灵机既然能够模拟整个逻辑证明过程,显然也可以模拟 lambda 演算,这仍然是字符串匹配替换而已,最终他们证明二者能力是等价的,如果将其上升到一切符号计算模型都等价于这两种模型,就称为 Church-Turing 论题。

替换生成与图灵完备

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

发明的举例:

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

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

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

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

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

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

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

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

radioLinkPopups

如对本文有任何疑问,欢迎通过 github issue 邮件 metaescape at foxmail dot com 进行反馈