文 | HW君
系列文章：
- 智能 | #0 人工智能的哲学原理
- 智能 | #1 在神经网络之前
- 智能 | #2 人工智能的三种流派
- 智能 | #3 可计算性，在图灵机之前
- 智能 | #4 通用计算机的起源
- 智能 | #5 一进制图灵机
- 智能 | #6 扩展二进制图灵机
- 智能 | #7 编码第N号图灵机
0. 模仿游戏
阿兰·图灵在1950年的论文《计算机与智能》中提出的一种测试人工智能的方法，叫「模仿游戏」。
当然它被后人熟知的叫法是「图灵测试」。
实际上图灵思考「模仿游戏」的起点是，一台机器是否可以模拟另一台机器？
这也是当今所有通用计算机的起源。
1. 遍历第N号图灵机
在上一期《智能 | #7 编码第N号图灵机》中，我们找到了一种将图灵机编码为一串 0 和 1 纸带的方式，并按该纸带的十进制数形式，将其命名为第N号图灵机。
例如：
「一进制+1图灵机」为第 177642 号图灵机；
「扩展二进制×2图灵机」为第 10389728107 号图灵机；
「一进制×2图灵机」为第 1492923420919872026917547669 号图灵机；
「扩展二进制+1图灵机」为第 450813704461563958982113775643437908 号图灵机。
而因为每一个图灵机必定对应一个十进制数，因此我们实际上已经可以遍历所有图灵机的可能性。
我们只需要从 0 开始数起：第 0 号图灵机、第 1 号图灵机、第 2 号图灵机……
一直数到第 177642 号图灵机，我们得到了「一进制+1图灵机」；
数到第 10389728107 号图灵机，得到「扩展二进制×2图灵机」；
数到第 1492923420919872026917547669 号图灵机，得到「一进制×2图灵机」；
数到第 450813704461563958982113775643437908 号图灵机，得到「扩展二进制+1图灵机」。
实际上大多数的自然数都不能产生可用的图灵机。
这里按照之前的编码方式列出第 0 – 12 号图灵机，观察其工作的情况：
T0：00→00R, 01→00R,
T1：00→00R, 01→00L,
T2：00→00R, 01→01R,
T3：00→00R, 01→00停,
T4：00→00R, 01→10R,
T5：00→00R, 01→01L,
T6：00→00R, 01→00R, 10→00R,
T7：00→00R, 01→???,
T8：00→00R, 01→100R,
T9：00→00R, 01→10L,
T10：00→00R, 01→11R,
T11：00→00R, 01→01停,
T12：00→00R, 01→00R, 10→00R,
上述的图灵机中，T0 就是简单地向右移动，并把纸带的格子全都改写成 0。
T1 也有同样的效果，但它在把遇到的 1 并改写成 0 之后，会往左回退一格，然后继续向右移动。
T2 则是简单地向右移动，且不改变纸带上原有的数据。
T0 、T1 、T2 这三台机器并不能停下来，因此不能被称为合格的图灵机。
T3 则可以称得上是一台合格的图灵机，它在将遇到的第一个 1 改写成 0 之后，就停机了。
T4 的状态控制器则是不完整的，它在遇到第一个 1 后就指向了一个空白的状态，不知道下一步要执行什么动作。
T8 、T9 、T10 这三台也和 T4 有着相同的问题。
T7 遇到的问题还更严重，它的二进制数为「111」，依照上一期的编码规则前后都加上省略的两个「110」后为「110111110」。
而我们的扩展二进制规则为：
二进制 0 → 0
二进制 1 → 10
R → 110
L → 1110
停 → 11110
这其中并没有涉及连续 5 个 1 的转换规则。
因此 T7 在纸带上遇到第一个 1 之后发生了未知的错误。
T5 、T6 、T12 则和T0 、T1 、T2 的问题类似，它们会永远不停止。
只有 T3 和 T11 能够正确工作的，虽然 T11 在遇到第一个 1 就停了下来，什么也没有改变。
同时也可以注意到，有 T6 和 T12 是相同的，并且在行为上等价于 T0 。
因此在列出的第 0 – 12 号图灵机之中，只有 T3 和 T11 能够算得上是合格的图灵机。
2. 再封装一层
我们已经实现用十进制自然数 0、1、2、3……来标记所有可能存在的图灵机。
现在再尝试将代表图灵机的十进制自然数编码成一条 0 和 1 组成的纸带。
可以直接将十进制转换为二进制，但会遇到一些问题。
例如考虑如下的一条纸带：
…00001101110010000…
因为纸带的左右两端都是无限长的 0，实际有用的部分为：
110111001
如果简单直接转换，那这个二进制数的十进制表示为 441。
但直接转换会导致这个形式的二进制数只能表示奇数，无法表示偶数，因为它的末尾一定不为 0。
因此我们可以采用将末尾的 1 移除的方式来读取，末尾的 1 即为前端二进制数的终结。
于是这段纸带的真正二进制数为：
11011100
它可以表示十进制的偶数 220。
而采用移除末尾 1 的方式的另一个好处是，除了奇数和偶数，我们还可以用这种方式表示 0 ：
…000010000…
它表示十进制的自然数 0。
这样我们就找到了一种将第N号图灵机的十进制 「N」编码成一段二进制纸带的方法。
3. 同时编码两个数
对于任意一个十进制自然数 ，我们可以将其用上述的方法编码成一段二进制纸带。
假设存在第 n 号图灵机 Tn ，对其输入纸带 m，它会输出另一段纸带 p。
将其表示为：
Tn (m) = p
那么要通过 m 产生 p，一定需要有这个特殊的图灵机 Tn 吗？
可以用以下这个视角来看待式子：
给定两个数 n 和 m，得到结果为数 p。
我们可以构建这么一个函数 U ：
U (n, m) = p
即函数 U 作用在数 n 和 m 上，产生了结果 p。
而以下两种情况的纸带输出结果是一致的：
（1）Tn (m) = p
（2）U (n , m) = p
其中（1）为第 n 号图灵机输入纸带 m，得到纸带 p。
而（2）为图灵机 U 输入纸带 (n , m)，得到纸带 p。
这两种结果是等价的：
U (n , m) = Tn (m)
因此我们可以假设存在一个图灵机 U，对其输入一条同时编码有 n 和 m 的纸带，那么它也可以输出一段纸带 p。
其中图灵机 Tn 和纸带 m 可以共同被编码为 (n , m) 。
为了实现图灵机 U 的功能，我们需要在一条纸带上同时编码进数 n 和 m。
这其实很容易，我们只需要在扩展二进制规则里再加入一个「111110」：
即我们的扩展二进制规则扩充为：
二进制 0 → 0
二进制 1 → 10
R → 110
L → 1110
停 → 11110
, → 111110
这样输入的纸带就是：
..n111110m…
它可以被图灵机 U 正确读取，从而产生 p。
而对于图灵机 U 来说，n 和 m 的值可以是任意的。
图灵机 U 所做的事情，便是把输入的「……n111110m……」纸带解读为 (n, m) 。
然后模仿成图灵机 Tn ，再对其输入 m ，然后输出纸带 p。
这样的一台可以模仿任意第N号图灵机的万能图灵机 U，就是「通用图灵机」。
4. 通用计算机的数学模型
构造一台「通用图灵机」无疑是非常复杂的。
对于输入的「…...n111110m……」纸带，它要先将自己模拟成第 n 号图灵机 Tn ，然后再去处理数据 m 。
这期间会读写头会在纸带上进进退退来来回回，过程缓慢且低效。
但尽管如此，我们一定可以找到这么一台通用图灵机 U ，完成这样的操作。
而通用图灵机 U 作为一台图灵机，那么它自身也一定有一个号码，即它是第 U 号图灵机：
U = Tu
这里的 u 会是多少呢？
可以给出它的准确十进制数字：
724485533533931757719839503961571123795236067255655963110814479660650505940424109031048361363235936564444345838222688327876762655614469281411771501784255170755408565768975334635694247848859704693472573998858228382779529468346052106116983594593879188554632644092552550582055598945189071653741489603309675302043155362503498452983232065158304766414213070881932971723415105698026273468642992183817215733348282307345371342147505974034518437235959309064002432107734217885149276079759763441512307958639635449226915947965461471134570014504816733756217257346452273105448298078496512698878896456976090663420447798902191443793283001949357096392170390483327088259620130177372720271862591991442827543742235135567513408422299889374410534305471044368695876405178128019437530813870639942772823156425289237514565443899052780793241144826142357286193118332610656122755531810207511085337633806031082361675045635852164214869542347187426437544428790062485827091240422076538754264454133451748566291574299909502623009733738137724162172747723610206786854002893566085696822620141982486216989026091309402985706001743006700868967590344734174127874255812015493663938996905817738591654055356704092821332221631410978710814599786695997045096818419062994436560151454904880922084480034822492077304030431884298993931352668823496621019471619107014619685231928474820344958977095535611070275817487333272966789987984732840981907648512726310017401667873634776058572450369644348979920344899974556624029374876688397514044516657077500605138839916688140725455446652220507242623923792115253181625125363050931728631422004064571305275802307665183351995689139748137504926429605010013651980186945639498
这是一个很大的数，量级为 7×101652。
我们说过，当今所有的通用计算机的数学模型，都可以等价于图灵机。
更准确来说，是等价于通用图灵机，即：
第724485533533931757719839503961571123795236067255655963110814479660650505940424109031048361363235936564444345838222688327876762655614469281411771501784255170755408565768975334635694247848859704693472573998858228382779529468346052106116983594593879188554632644092552550582055598945189071653741489603309675302043155362503498452983232065158304766414213070881932971723415105698026273468642992183817215733348282307345371342147505974034518437235959309064002432107734217885149276079759763441512307958639635449226915947965461471134570014504816733756217257346452273105448298078496512698878896456976090663420447798902191443793283001949357096392170390483327088259620130177372720271862591991442827543742235135567513408422299889374410534305471044368695876405178128019437530813870639942772823156425289237514565443899052780793241144826142357286193118332610656122755531810207511085337633806031082361675045635852164214869542347187426437544428790062485827091240422076538754264454133451748566291574299909502623009733738137724162172747723610206786854002893566085696822620141982486216989026091309402985706001743006700868967590344734174127874255812015493663938996905817738591654055356704092821332221631410978710814599786695997045096818419062994436560151454904880922084480034822492077304030431884298993931352668823496621019471619107014619685231928474820344958977095535611070275817487333272966789987984732840981907648512726310017401667873634776058572450369644348979920344899974556624029374876688397514044516657077500605138839916688140725455446652220507242623923792115253181625125363050931728631422004064571305275802307665183351995689139748137504926429605010013651980186945639498
号图灵机。
若将你的手机、电脑……转换成为一条纸带，那它就是上面的这串数字。
这就是图灵给世界留下的宝贵遗产，整个计算机产业蓬勃发展的理论起点。
5. 结语
即便图灵机理论影响了整个世界，但它其实只是图灵在思考希尔伯特判定问题过程中的副产物。
图灵创造出图灵机，只是为了尝试回答一个数学问题。
通用图灵机并非终点，我们认为有必要顺着图灵走过的路再往前一点，窥见一下他曾见过的风景。
这样后续在讨论人工智能时，才会有更深刻的理解。
（本章节完，敬请期待下一节）
By HW君 @ 2025-01-08