图灵的秘密》读后感：一个图灵机实现
发表于2014 年 1 月 26 日由Ng1091 | 本文内容遵从CC版权协议转载请注明出自ng1091.com
这篇文章的内容可分为两部分，一是读《图灵的秘密》有感，二是一个图灵机实现。
Part1. 有感
《图灵的秘密》是在2012年，图灵诞辰100周年的时候出版的，非常好的一本书。
读完这本书最大的感受就是，计算机的诞生离不开图灵机，图灵创造图灵机的初衷是为了解决数学问题，而数学本质上是哲学问题，所以一切都离不开哲学。（说到这儿都有点小激动想去学哲学了…）
为什么说数学是哲学问题呢？举个最基本的例子，我们到底是发现了数学，还是发明了数学？前者的意思是，宇宙诞生的时候，一切数学原理就形成了，并不因为人的认识而发生改变；后者恰好相反，数学只是人类认知的一种错觉。[1]
就像我在这篇微博中说的，图灵的论文很晦涩，如果不是Petzold大神的解读真看不懂。那么图灵到底讲了什么呢？简单地说（具体思想什么的就不说了，不然又得抄书），命题逻辑中的一阶逻辑，从几个大家公认的公理出发，可以推出各种定理与命题公式（称为可证明的），现在给你一个公式，让你判断它是不是可证明的。问题是，有没有一种通用的方法，对于任何公式，都能判断出结果。图灵提出了图灵机模型，利用它证明了不存在这样的通用判定过程。（与哥德尔的不完备性证明类似：存在既不能被证明又不能被反驳的命题）
书中还提到，图灵机、 λ演算和递归函数的可计算性是等价的。[2]
Part2. 一个图灵机实现
一. 背景
大一的暑假，这本书还没出版（2012），当时通过彭罗斯的《皇帝新脑》对图灵机有所了解，很感兴趣，想写一个小程序，能够输入数据、模拟图灵机的基本动作、输出结果。2天之后，终于写了一个特别简易的程序，就叫它Ng图灵机语言吧。然后，我根据Ng图灵机的语法规则，写了两个小程序，能够对二进制进行加（减）一。如图1。
图1 大一的Ng图灵机语言。这段程序是对二进制数加一。
好玩是好玩，但是功能有限，编程难度很大，除了加一减一的程序，实在写不出什么更有意思的了。
直到看了这本书，又想起大一的Ng图灵机语言，觉得有必要完善一下，增加更多的功能，或许就能写出更复杂的程序了。
唉，本来打算一天完成，看了代码才发现低估工作量了。大一时的C语言“造诣”还挺高的嘛，没有注释、变量名极简、430行代码没一句废话，害得我足足看了2个小时才完全搞懂。又用一天半时间，才把它重新完善好（代码增加至630行，增加了12个新特性）。剩下的半天时间，为它写了几个令人满意的图灵机小程序。
二. 图灵机的基本原理
图灵机是个虾米东西呢？相信聪明的读者已经有所了解，不过我还是再描述一下，因为有些细节后面要用到。
首先图灵机是一个机器，它不能吃，因为它是虚构的。
1.一条无限长的纸带（tape）。纸带被划分为一个接一个的小格子，每个格子可以写一个字符。字符的种类是有限的。
2.一个读写头（head）可以在纸带上左右移动，它能读出当前所指的格子上的符号，并能改变当前格子上的符号。
3.一套控制规则（table），它根据当前机器所处的状态以及当前读写头所指的格子上的符号来确定读写头下一步的动作，并改变状态寄存器的值，令机器进入一个新的状态。
4、一个状态寄存器，用来保存图灵机当前所处的状态。图灵机的所有可能的状态的数目是有限的，并且有一个特殊的状态，称为“停机状态”。 [3]
好了，规则讲完了，游戏该怎么玩？
图灵机事先加载控制规则，相当于安装程序。然后用户在纸带上写上东西，相当于程序的输入数据。图灵机从初始状态开始，根据读写头的字符和控制规则，对纸带进行擦写、移动操作，并改变状态寄存器的状态。直到出现停机状态，图灵机停机，这时纸带上的内容就相当于程序的输出数据。
总结一下，图灵机的核心就是控制规则（table），一个控制规则应该包括5项信息：
1.当前状态（s1）
2.读写头上的字符（char1）
3.新状态（s2）
4.新字符（char2）
5.读写头移动方向（head）
也就是说，如果当前状态是s1，并且读写头上的字符是char1，那么就修改状态为s2，将读写头上的字符修改为char2，读写头朝head方向移动一格。（head可以是左、右、不移动和停机）
最后，以一个简单的示例结束本节：
一台图灵机的控制规则如下：
0 0 1 1 停机
0 1 2 1 停机
假设纸带上只有一个字符0，读写头正指向这个0. 图灵机的初始状态是0。
图灵机首先寻找能匹配的规则，发现第一条是可以匹配的，当前状态是0，字符是0，那么跳转至状态1，将字符修改为1，停机。最终纸带上只有一个字符1，并且图灵机最后的状态是1。
如果初始纸带上只有一个字符1，那么这个1不会发生变化，图灵机以状态2停机。
三.NTM的语法
Ng图灵机（Ng Turing Machine）下文简称为NTM。
NTM是一个图灵机语言，因此它有以下语法规则：
1.字符集：支持ASCII码从32到126的所有字符。（这些字符都是可打印字符）
以下8个为特殊字符：
读写头控制符：左移（<）、右移（>）、不移（|）、停机（^）
自动转义字符： 空格符（*）、任意符（?）
（为什么需要这两个字符呢？因为空格作为控制信息的分隔符，是不能被程序正常识别的，所以用“*”代替空格，程序读到“*”会自动变身为空格符；另外，在控制规则进行匹配的时候，想匹配纸带上的任意字符，就要用到任意符“?”了）
转义字符（\）：想输入以上字符（比如“*”）怎么办？，用一个反斜杠加字符就可以了。比如“\*” 代表 “*”， “\?” 代表“?”。转义字符用在普通字符前没有作用，如“\x” 和“x”是等价的。
注释符号（//）：这个就不多说了。
2.控制规则：为了简洁，将控制规则合并为两部分，第一部分是s1+char1，第二部分是s2+char2+head（书写时没有“+”，是紧密连接的），两部分之间用空格分隔。其中char和head的长度均为一个字符。
比如
00 101>，可以得出s1为0，char1为0，s2为10，char2为1，head为>
start0 movex<，可以得出s1为start，char1为0，s2为move，char2为x，head为<
每一部分的长度不能超过64位（第二部分长度不包括最后的head），因此NTM支持（126-32）^64个状态，大概是10的126次方。理论上是够用的，而且NTM也算是一个64位的图灵机了，挺跟得上时代的。
3.初始状态：初始状态默认为NTM代码中加载的第一个状态。
4.初始纸带：初始纸带会提示用户进行输入，以终结字符（$）结束；也可以跳过，会自动创建一个字符为空格的格子。输入完成后，读写头指向最后一个非终结字符($)，也就是$左边的那个字符。需要注意的是，在纸带上输入字符时，不需要转义。
四.一个简单的NTM程序
好了，下面一起来写第一个NTM程序吧！写什么呢？万变不离Hello World，就写它吧！
大致思路就是在纸带上从左向右依次打印Hello World，然后停机。挺简单吧？
我们用数字作为状态编号，第一个状态是0，当遇到空格时，打印H，进入状态1，读写头右移； 在状态1，遇到空格时，打印e，进入状态2，读写头右移……
完整代码是：
0* 1H>
1* 2e>
2* 3l>
3* 4l>
4* 5o>
5* 6*>
6* 7W>
7* 8o>
8* 9r>
9* 10l>
10* 11d^ // 打印完d，停机，因此11状态可省略
将代码保存为hello.txt，和NTM放在同一目录。
双击turing.exe，输入文件名，会看到代码已经成功加载，然后按回车跳过纸带（因为不需要任何输入）。最后，看到NTM停机，纸带上输出Hello World。如图2。
图2 NTM的Hello World程序
怎么样，简单吧。再分析一下代码，一共有0~10,11个状态，每个状态负责打印Hello World中的一个字符，然后跳转至下一个状态，因此每个状态只执行一次，整个状态是线性执行的，没有循环或条件分支。
五.两个计算二进制数的NTM程序
下面我将展示两个之前提到的，也就是大一写的二进制加（减）一的程序。
为什么要从二进制入手呢？因为二进制的运算规则很简单，比如加法只有3条，0+0=0,0+1=1,1+1=10，所以编程难度就很小。
先来看二进制加1，分析几个例子：
110 + 1 = 111 （6+1=7）
1011 + 1 = 1100 （11+1=12）
1111 + 1 = 10000 （15+1=16）
不难发现规律：若最低位（最右边）为0，将其变为1即可；若最低位为1，将左边遇到的第一个0变为1,将途中经过的所有字符变为0；如果左边没有0，就在最高位加一个1。
你应该还记得，NTM输入完纸带后，读写头指向最后一个字符，恰好指向二进制数的最低位。
假设以状态0开始，第一个规则是：
00 01^ // 它的含义是，在状态0遇到字符0，保持状态0不变，将字符修改为1，然后停机
// 如果状态0的遇到字符1， 我们就进入一个新状态，向左寻找0：
01 10< //进入1状态， 将1变为0，左移
10 11^ //在1状态找到0， 将0变为1，停机
11 10< //在1状态，将遇到的1都变为0，继续进入1状态，循环查找
1* 11^ //如果左边没有找到0，就会来到最高位的左边一格，遇到空白符，此时输出1停机
下面用图3、图4来演示一下之前的3个例子：
图3 例1和例2的演示
图4 例3的演示
最后用NTM验证一下：
图5 NTM验证3个例子
Bingo！
减法也不难，如果最低位是1，变为0停机即可；如果最低位是0，向左寻找1，进行借位，途中遇到的0都变为1；如果借不到1，直接停机。
最后一种情况全为0，停机后会变成全1，是二进制的循环减法。
程序代码与加法相似：
01 00^
00 11<
10 11<
11 10^
1* 1*^
具体就不演示了，感兴趣可以自己用NTM跑一下。
顺便一提，十进制加一的程序也不难，只要做到逢9变0，再进1位就行。代码如下
// Ng Turing Machine
// 给一个十进制正整数加1
// 例： 要计算123
// 输入：123$
00 01^
01 02^
02 03^
03 04^
04 05^
05 06^
06 07^
07 08^
08 09^
09 00<
0* 01^
六.真正的NTM程序
终于来到激动人心的地方了！其实之前讲的程序都是小儿科，下面我们要用NTM干”大事“了！
如何计算两个数的加法？
为简单起见，我们将数表示成连续的1。比如3就是111，5就是11111。
另外还要约定，输入时每个字符之间有一个空格，这个想法借鉴了图灵的论文，空格用来计算时打印辅助信息，可以方便计算，减少代码量。
先来分析一下，要计算2 + 1 =，将其表示成1 1 + 1 =，计算结果应该是1 1 1。
计算3 + 2 =，先表示成1 1 1 + 1 1 =，计算结果应该是1 1 1 1 1。
（上式中的“=”可以使最终输出更直观，在代码中要用到，因此不能省略）
思路大概是这样：先找到最左边的1，然后从左向右，把遇到的每一个1复制到等号右边。如何找到最左边的1呢？我们用一个字符“$”作为表达式的开始，这样找到“$”就表示到了公式最左边。每复制一个1，要对其进行标记，防止重复复制，用一个“#”放在1的右边，表示这个1已经复制过了。每次复制完成后，从右向左找到第一个“#”，表示这个“#”左边的1都已经复制过了，所以向右寻找1，如果在找到1之前先遇到了“=”，表示所有的1都已经复制完成了，这时就可以停机了，但是为了美观，我们再次向左移动，清理掉左边的所有“#”标记，遇到“$”时停机。刚才的描述中漏掉了一个bug，就是字符“+”，其实可以简单处理，遇到“+”忽略即可。
嗯，思路清楚了，程序该怎么写呢？请看图6。
图6 NTM两数加法的示例
最终代码：
0= begin=| // 开始
begin? begin?< // 移动到纸带开始处
begin$ plus$> // 遇到$即开始处，进入plus过程
plus1 plus-flag1> //若遇到1，用plus-flag进行标记
plus-flag* add-to#| // 标记完成，进入add-to开始做加法
add-to? add-to?> // 向右移动，寻找=
add-to= write-pass=> //找到=，跳过一个格子
write-pass? write?> // 跳过完成，进入write
write1 write-pass1> // 寻找空白
write* back1< // 找到空白，写入1，进入back
back? back?< // 退回到#标记，进入plus，做下一次加法
back# plus#>
plus= clear=< // 若遇到=，表示加法完成，进入clear清理标记
clear# clear*<
clear? clear?<
clear$^
plus+ pass+> // 若遇到+，表示已完成第一个数的加法，忽略+
pass* plus#>
用NTM验证一下，结果正确。如图7。
图7 两数加法的NTM截图
加法算完了，如何计算两个数的乘法呢？
2 * 3 = 表示成 1 1 * 1 1 1 =
把加2做3遍，就是乘法的含义。
思路又变得清晰起来：寻找“*”右边的1，用@标记，然后把“*”左边的1全部复制到“=”号右边，复制过程可以直接调用之前的加法代码。需要注意的是，每次复制前，需要清除上次留下的#标记。一次复制完成后，从“=”开始向左找到第一个@，表示左边的1已经乘过了，向右寻找1继续做加法。当找到1之前遇到=时，表示运算过程已经结束，清除@和#标记即可停机。
详细过程如图8所示。
图8 NTM的乘法示例
最终代码：
// Ng Turing Machine
// 两数相乘
// 数字用 1 的个数表示
// 以$开始，数字之间用空格分隔，以=结束
// 例： 要计算 2 * 3
// 输入：$1 1 * 1 1 1 =$
0= find-at=< // 开始
find-at? find-at?<
find-at@ find-one@>
find-at\* find-one\*>
find-one? find-one?>
find-one1 find-one-flag1>
find-one-flag? find-star@<
find-star? find-star?<
find-star\* clear-left\*<
clear-left? clear-left-pass*<
clear-left-pass? clear-left?<
clear-left$ plus$>
plus1 plus-flag1> //若遇到1，用plus-flag进行标记
plus-flag* add-to#| // 标记完成，进入add-to开始做加法
add-to? add-to?> // 向右移动，寻找=
add-to= write-pass=> //找到=，跳过一个格子
write-pass? write?> // 跳过完成，进入write
write1 write-pass1> // 寻找空白
write* back1< // 找到空白，写入1，进入back
back? back?< // 退回到#标记，进入plus，做下一次加法
back# plus#>
plus\* find-equal\*>
find-equal? find-equal?>
find-equal= find-at=<
find-one= clear-at=<
clear-at? clear-at?<
clear-at@ clear-at*<
clear-at\* clear-sharp\*<
clear-sharp? clear-sharp?<
clear-sharp# clear-sharp*<
clear-sharp$^
用NTM验证一下，如图9。
图9 乘法的NTM截图
结果正确，注意到截图中的steps了吗？计算2 * 3需要317步才能完成，而计算3 * 5竟然需要1178步。
不过NTM有一个优点，就是它的程序是工作在字符级的，不用担心数据溢出什么的，纸带是无限长的，所以纸带长度取决于你的内存大小。如果你愿意，可以计算两个非常大的数。
怎么样，加法、乘法都写好了，如果还不过瘾，可以参考乘法尝试写幂运算。
其实《图灵的秘密》这本书中，有关图灵机的例子，有的比刚才的示例还要复杂，比如计算二进制乘法、除法、计算π等等。有兴趣可以去膜拜一下。
七.NTM的更多特性
终于有时间更新日志啦，再不更新就不知道什么是图灵机了。这一节就来讲一下NTM的高级使用方法。
还记得之前说过新版NTM增加了12个特性吗？这里就讲几个比较重要的吧。（有些小特性实在拿不出手）
1.状态重载
这个特性之前已经和大家见过面了。为了简化代码量，增加对任意字符的匹配机制，又不损失精确匹配，所以就想到了“状态重载”的办法。也就是精确匹配优先机制。
当一个状态同时具有任意匹配和精确匹配的规则时，首先进行精确匹配，如果匹配失败，再选择任意匹配。
比如：
find-at? find-at?>
find-at@ another@|
这样两条规则结合，就可以实现向右寻找“@”，找到后进入another状态。
如果没有状态重载，代码可能是这个样子：
find-at! find-at!>
find-at# find-at#>
find-at$ find-at$>
find-at1 find-at1>
find-at0 find-at0>
//省略若干，这里必须把纸带上可能出现的字符都穷举一遍…orz
find-at@ another@|
利用状态重载，还能实现if语句
is-at@ goto1@|
is-at? goto2?|
if遇到@，then进入goto1状态，else进入goto2状态。（结构本质上跟上例是一样的）
如何实现if-elseif-else语句？
is-at@ goto1@|
is-at# goto2#|
is-at$ goto3$|
is-at? goto4?|
其实这样的多条语句就相当于is-elseif-else语句。
2.调试模式 (debug)
这是一个非常有用的功能，使用-d或-d2命令可以进入调试模式，在调试模式中能够单步运行程序。
-d和d2的区别是：-d是简洁模式，控制规则和纸带信息写在一行中；-d2则各占一行,并且显示读写头的位置。对于比较大的程序，使用-d2模式更直观，对于小程序使用-d显得简洁。
比如我们要调试之前的乘法程序，在命令行输入turing -d2 multiply.txt 以debug2模式运行程序。
输入初始纸带后就开始单步运行了。每一步显示当前匹配的控制规则、纸带信息和读写头位置，按回车进入下一步。如图10所示。
图10 debug模式
这样，可以看到NTM的详细运行过程，对调试程序有很大帮助。（事实上，我在写加法和乘法的时候，通过调试模式解决了好几个bug）
3.死循环检测
据我所知，任何编程语言都不能检测一个程序是否陷入死循环，同样NTM也不能。但是通过一个简单的想法，可以基本实现死循环检测。这个想法就是：一般的的NTM程序，执行步数都不会太大，否则说明它可能进入死循环了。NTM默认值是10000，只要执行步数达到10000步，就会暂停运行，询问用户是否继续。（当然，一些大规模的NTM程序可能会超过这个值，这时可以使用-n命令指定值）
我们写一个死循环程序，来试试看：
0? 1?<
1? 0?>
这个程序在0、1状态之间不停循环，读写头做往复运动。
运行程序，如图11所示
图11 死循环检测
当程序运行了10000步之后，出现提示，选项1和2的区别是2不打印纸带，对于一些非常bug的程序，可能会输出很长的无意义的纸带，打印会浪费时间。
我们选择1，NTM停机，打印纸带。
（这里有一个小bug，就是选择3.continue之后，运行步数会从0开始计数，导致最终的程序运行步数不正确。现在已经深夜了，懒得改…）
4.更多特性？
别忘了使用–help命令，可以看到NTM的所有命令。
如图12所示。
图12 NTM的帮助
八.NTM Relase
跟之前的beta版相比，增加了dead-loop.txt，修改了一处英语语法上的错误Orz…，还有一些小修改。
九.NTM的实现
解读代码的事情貌似非常浪费时间，尤其是在刚打完游戏的时候。所以代码就不解读了，日后再说！
在这一节里，我突然想到，NTM的实现确实有一些能够优化的地方。
控制规则的存储，我按照s1状态的长度作为索引，然后把长度相等的规则放在一个链表中，状态长度最长64位，所以最多就有64个链表。这个索引效率并不高，经常使用的状态名称长度也就那几个，大概是5~10位吧，所以冲突率高，在链表中线性查找会浪费很多时间。更好的办法是对状态名称算hash值，使用数组+链表索引，或者一种树结构的索引（如红黑树）。
呼~，这篇日志总算勉强YY完毕。最近几天突然有了下一篇日志的灵感，顺便来一个下集预告：关于认知，什么是理解，我们真的理解了吗，还是像John Searle的Chinese room那样什么都不理解；认知能力来源于大脑，那么随着大脑进化，认知到底有没有极限？
References:
[1] Charles Petzold 《图灵的秘密》（人民邮电出版社，2012），286
[2] 同上，311