图灵的论文《可计算数及其在可判定性问题上的应用》(《On Computable Numbers, with an Application to the Entscheidungsproblem》）发表于1936年。图灵在论文中构造了一个图灵机来计算可计算数，证明希尔伯特提出的通用可判定性方法不存在。
图灵机的具体构造可以参考图灵的论文，但是阅读起来非常晦涩。如果理解他的构思或者灵感，那么阅读他的论文就会容易很多。图灵不是我们同时代的人，要推测图灵的构造灵感非常困难，但是读者可以和作者一样从阅读到的相关文字和听到的相关故事去隔空对话这位伟人，推敲他的灵感来源。电影《模仿游戏》很好的介绍了他的生平，根据历史学家估计，图灵因为破解德国的恩尼格玛密码机（Enigma Machine）拯救了英国一千四百万人。但是因为他的性取向，他遭受了英国政府不公正的待遇而辞世，年仅41岁。在破解恩尼格玛密码机的时候，图灵沉浸在密码学之中。密码学就是将一组数字按照一个规则让机器变成另外一组数字。然后接收到的一方可以根据一个反向规则让机器变成原文。举个简单的例子，10多年前孩子们没有隐私，信件会被家长偷看，作者就曾构造过一个简单的加密方法，把所有的英文字符换成英文字符表的下一个字符，接收者把每个英文字符换成字符表的前一个字符即可以重构原文。举一个更加复杂的例子，计算机科学一般用两位数字01，02，… 26来表英文字母A, B, … Z，用00表示空格。这样，一个关于聚会的时间和地点的文字消息就可以转化为一串数字。接收者收到这串数字后，把每两位数字转换成对应的字母，就可以构造出最初的文字消息了。把一个句子通过一个机器逻辑映射成一个数字非常有意思，例如ICU可以成090321。图灵在破解恩尼格玛密码机的时候可能深谙其中的乐趣，就好像两个年轻人糊弄彼此不懂密码学的父母一样。
《Cloud Foundry：从数字化战略到实现》的第一章曾回顾了香农信息论为代表的数字世界的崛起。我们谈到了冯·诺伊曼为何建议香农在他的信息论中采用物理学中熵的概念，但是我们并没有仔细讨论后面的哲学，这里可以再继续深入一下。物理学家也好，数学家也好，隐隐约约感觉到物质和能量背后存在的信息（数字）世界。我们能否用数字世界来描述物理世界？香农和奈奎斯特独创了信息论。在他们两位开天辟地的工作成果下，我们可以通过一个机器把图像、音频编码成一组数字。于是，我们今天可以用二进制编辑器打开任何一个计算机上的图片或者音频，其实它们只是一串0和1编码。这些0和1的字符串还是对应了一个数的二进制表示，所以它还是一个数。图灵在密码破译工作的时候，有机会去美国的贝尔实验室协调英美两国的合作。他在贝尔实验室遇到了两位大师。（可见人生结交高质量的朋友多么重要。）作者猜测图灵对于两位大师制作的编解码机器很受启发。他对世界万物都是数的信念往前推进了一步¹：如果说人的五官能够感受到的世界万物都可以用机器转换成数字来表示，那么人的思考过程是否也能用机器转换成数字来表示？为帮助读者理解图灵的这个构思，拿iPhone上的Siri语音助手举个例子。Siri是一个能思考和分析的程序，如果你用一个二进制编辑器打开，它也无非是一个0和1二进制表示的数。但是Siri对应成iPhone这个机器(本质上就是一个图灵机)上的一个数字后，在机器上的运作就能起到人工智能的效果。从这里读者也可以看到数字化是人类前进的一个新方向，相比人类在工程和物理几千年的研究，数字世界的探讨从图灵等人在20世纪40年代开辟这个话题到今天才几十年。
图灵的论文详细介绍了图灵机的构造和定义在图灵机上的可计算数。如果读者觉得论文太干，可以参考《图灵的秘密》一书，该书做了非常详细的注解。图灵用极其简单的抽象机器来模拟一个数学工作者。一个数学工作者脑子里面有个思考状态（上下文），他在纸上扫描到下一个字符的时候脑子里面会产生一个状态，然后可能在纸上移动位子写下一个符号，然后不断重复这个过程。图灵机的构造就是这么简单，图1-12就是图灵机的一个大致艺术描述。
图灵机在无限长的纸带上移动，每次移动读取一个符号(数字用二进制表示)，然后图灵机的内部状态进行改变，并决定图灵机下一个移动的位置。图灵在论文中给出的一个例子是打印一个分数⅓. 这个图灵机很简单：打印1个0往右移动一格，然后再往后移动一格，留出一空格做可能的符号标记，然后再打印一个1并往右移动一格，图灵机再往右移动一格留出一空格做可能的符号标记。以此类推。以上过程可以用如下的状态切换表来表示。
表1-1: 可计数⅓的图灵机表示
|
机器状态(Configuration) |
行为（Behavior) |
||
|
当前状态(m-config) |
输出符号(symbol) |
操作(Operation) |
结束状态(final m-config) |
|
b |
无 |
P0(打印0)， R(往右移动一格) |
c |
|
c |
无 |
R(往右移动一格) |
k |
|
k |
无 |
P1(打印1), R(往右移动一格) |
e |
|
e |
无 |
R |
b |
写过程序的读者已经发现，这有非常经典的汇编程序的味道。机器打印出来的纸带如下图所示。早期软件工程师还真的玩过穿孔的纸带。
|
… |
0 |
1 |
0 |
1 |
0 |
1 |
… |
表1-2: 可计算数1/3的图灵机纸带
把这个纸带标记为小数点后的二进制数字(0.010101…)，读者可以用级数求和，其结果等价于⅓。 读者可能要问两个问题：1）二进制表示对数字计算机的产生有极大帮助，那么图灵是如何突发奇想地想到用二进制来表示图灵机？ 2）图灵为何只讨论0到1之间的实数？这两个问题的确非常重要，因为这涉及我们对人和机器之间的互补和竞争关系的讨论: 机器到底是否会取代人？我们在下一节中再展开，我们暂时聚焦在图灵机上。
这个图灵机只做一件事情，就是表示一个可计算数⅓。为了达到举一反三的目的，我们可以把表1-1中的b和k的顺序更换一下，创造了另外一个计算2/3的图灵机。表格表示如下：
表2-1: 可计数2/3的图灵机表示
|
机器状态(Configuration) |
行为（Behavior) |
||
|
当前状态(m-config) |
输出符号(symbol) |
操作(Operation) |
结束状态(final m-config) |
|
b |
无 |
P1(打印1)， R(往右移动一格) |
c |
|
c |
无 |
R(往右移动一格) |
k |
|
k |
无 |
P0(打印0), R(往右移动一格) |
e |
|
e |
无 |
R |
b |
它的纸带如下，其中1和0的顺序与数1/3纸带中1和0的顺序正好相反，如图1-14。
|
… |
1 |
0 |
1 |
0 |
1 |
0 |
… |
表2-2: 可计算数2/3的图灵机纸带
我们现在看到了图灵机的定义和运行机制，能够用图灵机计算的数叫做可计算数。目前为止得到两个表格表示的不同图灵机，分别用来计算可计算数1/3和2/3。写过程序的人可以把这两个表当做两个程序，方便理解后面的人和AI的讨论。如果图灵只是用假想的机器来编码可计算数，那与香农和奈奎斯特的成果没有任何可比性，因为两位大师已经用机器把图像、声音等信号用机器编码成数字。但是图灵再往前走了一步，他不仅把数字编码成特定的图灵机，还把特定的图灵机编码成通用的图灵机²。读者可简单地理解为图灵创造了一个通用的机器，在这个机器里面，上面的两个图灵机(可以简单理解成上面的表1-1和表2-1）也可以编码成两个可计算数（程序），这意味着（理论）通用计算机的诞生。对于做数学的人而言，世界上已经存在计算机了。把上面计算表1-1表示的计算1/3的程序和表2-1表示的计算2/3的程序输入到这个通用计算机，就会输出对应的纸带：表1-2和表2-2。香农和奈奎斯特的编解码机器也可以在这台通用图灵机上运行。用今天的事物来类比，就是把微信程序、地图程序、Siri程序输入到iPhone这个通用计算机上执行。普遍被认为具有人工智能的Siri，从这个意义上说只是图灵机上的一个可计算数而已。图灵的这个通用计算机的构造需要更加坚持和专注的阅读，有兴趣的读者可以阅读他的论文或者有注解的《图灵的秘密》一书。
自通用计算机提出以后，图灵就开始为他假想出来的计算机编写程序。对学数学的人而言，脑子里有的而且逻辑通的就是存在的。图灵当然也关心如何在物理世界创造出一台物理计算机，但是这个需要涉及人情世故来获得大量物理世界的资源、聚集团队和持续执行。这种事情看上去更像是匈牙利贵族出身的翩翩公子冯·诺依曼的特长。作者不认为第一台可存储程序计算机是冯·诺依曼一个人创造的，而是他和他的团队一起创造出来的。图灵在普林斯顿研究院的时候曾经就在冯·诺依曼的办公室对面，冯·诺依曼也曾给了图灵一个助理工作的机会，但是图灵还是毅然回到了英国。
数字是数，信号是数，程序也是数，世界万物都是数。自从第一台假想计算机和第一台物理计算机诞生以后，再加上香农和奈奎斯特把物理世界的信号编码成数字，数字技术就开始蓬勃发展，进入了《Cloud Foundry：从数字化战略到实现》所谈到的大型机、PC机和云计算机时代。一堆本来只能吃榨菜喝小米粥的数学、物理工作者一夜之间成为能编写程序的高薪的软件人员。从计算机发明到现在短短六七十年，似乎能写的程序都被写了，这些程序不少带有“人工智能或机器学习”的数学模型。很多程序很强大：虚拟现实、无人驾驶、人脸识别、语音助理等。一下子人们开始惊呼：“人工智能程序会不会全面取代人类？”
- ¹：作者猜测这是图灵做的最大胆的一步外推，当然无从考证。
- ²：通用图灵机的展开可以参考图灵的论文《On Computable Number》
《AI和人》系列快速链接
作者介绍
冯雷(Ray Feng)是Pivotal中国公司MD兼研发中心总经理。Pivotal中国成立至今，冯雷主持了近十亿人民币投资的中国运营和研发体系。作为Pivotal全球产品关键领导人，冯雷为Pivotal公司的数字化理念建立及其对应的Cloud Foundry和Greenplum产品提供战略输入。冯雷于2010年从美国硅谷归国，在美国500强公司EMC旗下组建了Pivotal中国。在归国之前，冯雷居住在美国加州硅谷，在500强企业甲骨文(Oracle)总部从事云计算产品研发。作为云计算最早一批从业人员，冯雷帮助甲骨文云计算资源调度领域成为意见领袖。学术方面，冯雷以浙江省队物理奥林匹克银牌进入北京大学。冯雷在北大实验班（现在的元培项目）接受计算机科学和数学在内的基础学科熏陶，并获得物理学和经济学双学士。冯雷研究生就读于美国匹兹堡市的卡内基梅隆大学并获得硕士学位，在校期间在机器人学院(Robostics Institue)从事教育机器人项目助研。冯雷持有两项美国云计算专利，并著有云计算、大数据和AI的三部曲著作.
[如需转载请注明本文URL] https://digitx.cn/2019/04/19/ai和人_第3节_图灵机和可计算数
“《AI和人》第3节：图灵机和可计算数”的2个回复