推完上一篇那个晚上，我回家看见多崎作笨拙地在手机屏幕上滑动爪子（可能是在努力点赞）。它看见我回来，急不可耐地说话：喵，喵喵喵喵喵喵，喵喵喵，喵喵。
意思是说：我还以为你搞这玩意儿有多了不起，原来不过如此嘛，逻辑门，组合，冯诺依曼架构，我已经明白了！说完满不在乎得摇动尾巴。
我边沏茶边说：这还差得远着呢，上一篇文章介绍的只是现实世界诸多计算机中的一种，还有其他类型的计算机，例如DNA计算机，不同计算机有不同的原理，就像娘生九猫，猫猫不同，你看你是只三花，你大哥渡边升就是黄白相间，你小弟哈特菲尔德又是乌云盖雪，我只研究你三花多崎作，能说是懂猫了吗？你们三兄弟乃至所有猫存在共性，理解这种共性才算懂一点猫了。计算机也是一样的道理。
愿闻其详，多崎作说。
你知道计算机是可以编程的吧？我看多崎作点头就继续说下去，计算机是可以编程的，就意味着一种计算机可以通过编程来“模拟”另一种计算机，如果 计算机A 可以通过编程模拟 计算机B，那就意味着 计算机A的“能力” 大于等于计算机B。因为 计算机B可以做的，计算机A 都可以通过它模拟出来的那个 计算机B' 来实现嘛，到这里有没有问题？
多崎作点头。
我喝了口茶继续往下说：如果两个计算机，计算机A和 计算机B， 可以互相模拟，则他们做计算的能力是 等价 的，因为 A 可以做的， B都可以做，反之亦然。既然他们在能力上是等价的，那么我们只要研究A，其结果就可以适用于B。进一步，如果我们能找到一种计算机，它能模拟我们所能设想的所有计算机，那它就是所有计算机能力的上限，我们对计算性质的研究就可以只依据它了。
“太好了！” 多崎作激动地说，“太好了，让我们开始干吧！我们研究出来就可以成为青年科学家了吧？”
我苦笑：这件事已经有人在1936年做了，距今已有，额，八十多年了。这个人叫图灵，它提出的计算机模型叫图灵机。
多崎作：那好，请你介绍一下图灵机。
这就是图灵机。我指着上图给多崎作讲解：图灵机由一个无限长纸带、一个读写头组成，纸带如上图一样分成一个一个的小格，小格可以是空白的，也可以填上0或者1， 读写头可以做这样几件事：
像左或向右移动（N格）
读当前格子里面的内容
往当前格子里面写（0、1或空白）
读写头的行为由一个『状态转移表』定义，一个典型的状态转移表是这样的(我把表格打印在纸上给多崎作看)：
读到的符号
写入指令
移动指令
空
-
-
0
写入1
向右移动纸带
1
写入0
向右移动纸带
“等等！”多崎作举起爪爪，“等等，我有一个问题啊，不一定对，就是，这个这个，图灵机这个读写头，它怎么知道下一步要干嘛呢？它是怎么干的呢？”
是这样的，我递给多崎作一杯茶，这个事是这样的，图灵机 是一种 抽象模型，所谓抽象模型呢，就是说我们这里不考虑它的具体构造，而是考虑它的性质，它的性质就是有一条纸带，有一个读写头，读写头可以做的事情是有限的；而读写头具体要做什么，是由上面那样的表格决定的，我们只要给了图灵机这样一个表格，图灵机就会按它工作，这就是图灵机的假设，我们就要这样接受它，它就是可以做到，换言之，能做到这个的我们管它叫图灵机，比方你就可以是一个图灵机，你的爪子可以在纸带上移动，可以读纸带上的内容也可以往上写字，你也可以读表格来决定你下一步要怎么做，在这个意义上，你就是一台图灵机，明白？
“我在纸上列竖式做乘法的时候就是一个图灵机？”多崎作说。
孺子可教，正是这样。那么这个表格是怎么来的呢？我知道你要问这个我就自问自答了哈。这个表格代表了不同的计算任务，制定这个表格实际上就是对图灵机编程，我们做出来这个表格，提交给图灵机，它就会按照表格行动，限制就在于，我们只能以读写头读到的符号为依据，我们设置的行为只能是写入0/1或者移动读写头。
事实上，上面那个表格就是一个简单的，对二进制数按位取反的程序。
多崎作的胡子因为喝茶沾满水滴，它抖了一下脑袋才转过来看我：乏味。你就不能搞点真正有意思的编程吗？上次是一位数加法，这次是按位取反， 这是连狗狗训练一下都可以做的事情好不好。
只是为了解释一下嘛，我说，没必要搞那么复杂，我也可以解释多位数加法或者乘法，或者算鸡兔同笼之类的，但是那样构造这个例子就要涉及过多细节，例如输入如何安排和映射，这是一篇科普推送里面合适写得吗？明白意思就可以了嘛。
多崎作：可以。明白了，有点意思。但是这有什么用呢？这个有什么意义？这看起来不过是一个还不如上一篇实际的一个计算机，感觉没有提供什么知识。
我：完整地说明图灵机的意义，超出了我们这篇文章的篇幅。不过我们今天可以说这几点，有一些其实你已经意识到了，例如，你意识到自己在某种意义上就是一个图灵机，这正是图灵机提出的重要背景。图灵机要解决的问题首先是人类的逻辑能力的问题，图灵断言，人类的任何逻辑推理过程，都可以由图灵机表达，因此，可以通过研究图灵机的性质来研究人类的逻辑推理，或者说，认识能力。
多崎作：好的。那研究出来什么了呢？
我：主要是两点，第一点是关于人类能做什么，第二点是关于人类不能做什么。关于人类能做什么的是 丘奇-图灵论题， 关于人类做不了什么的是 停机问题。
丘奇图灵论题是说，任何在算法上可计算的问题可由图灵机计算。你可能会问，那什么叫“算法上可计算”呢？很遗憾，这个概念没有很好的定义，本质上，定义这个概念，就等于发明一个计算模型，而迄今我们发明的计算模型都还是和图灵机能力上等价的。所以这个论题实际上是用图灵机定义了可计算性。但是到底什么是可计算的呢？我觉得它一定程度上是一个心智的问题，因此，丘奇图灵论题只是一个“论题”，连“假设”都不能算，因为它不太可能建立一个可以证明或证否的表述，这是它从根本上和心智有关的性质决定的。但他仍然提供了一个重要的知识，那就是它是对人类思维能力里面很大一部分的形式化的建模，我们从而能去理解我们能做的和不能做的。
而我们（图灵机）不能做的，就是停机问题。《神雕侠侣》里面神雕大侠杨过给了郭襄三根金针，说每根针代表一个实现愿望的机会，只要郭襄说出来，杨过大侠就一定会帮助她实现。本青（年）小的时候老是想：那我每次用到最后一根针的时候，都说还要三根不就完了。这个故事的本意是讽刺人的贪心，但是用在这里是表达一个“元叙事”的意思。图灵机承诺我们，可计算的算法都可以计算，那么，存不存在一个算法，可以判定任何一个算法能不能算得出来（停机）？图灵断言，这样的算法在图灵机上不存在。并且这个断言是严格的，也就是说理论上不可能。证明的构造，是在被判断的算法和做判断的算法里面建立一个同构的关系，即他们通过不同的方式表述同一件事，而停机问题会导致这两个算法之间自相矛盾。
多崎作：说得这么玄乎，你会证明吗？
我：我会，但今天就算了，因为到现在篇幅已经够长了。我只是想补充一点，停机问题的证明构造和哥德尔不完备定理的构造非常像，但是他们之间到底是什么关系，我目前还没搞明白。它和罗素发现的“理发师悖论”有一定的关系，“理发师悖论”后来通过公理化集合论解决掉了，我们认为这个悖论似乎是一个数学语言不完备的问题，但是停机问题和哥德尔不完备定律提示我们，在人类逻辑能力里面，似乎从根本上存在这种自我指涉的结构……
“砰！”我正讲得高兴，听见一声巨响：多崎作一爪子把我的茶壶打翻出溜跑掉了。茶水留在桌上弄湿了在多抓鱼上买来的参考书，他们分别是：
Functional Programming：Practice and Thoery
图灵的秘密
可计算性与自动机理论