CCCF专栏 | 黄铁军：电脑前传(2)：计算

从结绳记事开始，数和计算就成为人类认识世界、改造世界、创造新世界的有力工具。

不可数

从结绳记事开始，数和计算就成为人类认识世界、改造世界、创造新世界的有力工具。掰指头数数是最基本的智力活动之一，部分动物也会，这应该是自然数的起源。负数的概念最早出现在公元前三世纪我国的《九章算术》，西方国家直到1637年才由笛卡尔在《几何》中勉强承认负数的地位。0是在公元五世纪左右由印度人发明的（可能源于印度“绝对无”的观念），之后由阿拉伯人列为10个数字之一，广为传播，差不多和负数在同一时期被西方国家接受。小数也是《九章算术》发明的，今天使用的小数计数法则是文艺复兴之后的16~17世纪才确定下来。

“实数”这个词在18世纪才正式登上历史舞台。实数给人踏实的感觉，可以和直线上的点建立一一对应关系。实数集被称为“连续统”。十进制数位的整齐划一加强了实在感：两个整数之间等间隔地插入10个小数，再在两个小数之间更细密地等间隔插入10个小数……模式统一，秩序井然。我国自古以来很多哲学家都深信冥冥之中自有定数，18世纪岳麓书院山长旷敏本总结了这种信念：“是非审之于心，毁誉听之于人，得失安之于数”1。

但这种淡定，实为幻觉。

在实数概念出现之前的1683年，自然数就已经让伽利略隐隐不安了：对自然数做最简单的“数数”动作，只数偶数，每个偶数对应一个自然数（那个偶数的1/2），一一对应，因此偶数和自然数一样多。但明明偶数只是自然数的一半，另一半是迥异的奇数啊，这是怎么回事？

人类在懵懵懂懂中走过100多年，19世纪终于迎来了一位认真“数数”的人——德国数学家、集合论的创始人格奥尔格·康托(Georg Cantor, 1845—1918)。1873年，康托在一封信中提出，他怀疑在自然数和实数之间不能建立让伽利略困惑的那种一一对应关系，即实数不像自然数那样是“可数的”。一年后康托就证明了自己的怀疑。18年后的1891年，康托发表另一种证法——对角线证明法(diagonal proof)[1]。这一绝妙思路开辟了一条全新路径，库尔特·哥德尔(Kurt Gödel, 1906—1978)和阿兰·图灵(Alan Turing, 1912—1954)的伟大证明中都会用到它。

对角线法是一种反证法，只用到自然数常识和数学归纳法，不用公式，只借助文字，就能说清楚。

先假定实数像自然数那样是可数的，那么就可以排列成一个阵列：每个实数占一行，各行用小数点对齐，我们只需关心小数点后面的序列，遇到整数或有理数，只把后面的小数位都写成0。实数有无穷多个，因此这个阵列就有无穷行，先后次序无所谓，无论你怎么排，第一行记为第1个实数，第二行记为第2个实数，如此排列下去，直到你相信包含了所有实数。

康托的对角线操作是：第1个数，取小数点后的第一位；第2个数，取小数点后的第二位；第3个数，取小数点后的第三位……再把取出来的数位按上述自然次序排成一个无限长的数，把小数点放在这个数的最前面，然后让这个数的每位都加1，如果遇到9，就变成0，这样就得到一个新数。

把得到的新数与前面已经排好次序的实数序列逐项对比：第1个数的第一位和这个数的第一位不同，第2个数的第二位和这个数的第二位不同……，第N个数的第N位和这个数的第N位不同……，一直比对下去，如果这个新数和已经排好序列的实数集合中的任何一个数都不同，即这个新数不在实数集合中。这和集合中已经包含了所有实数的假设是矛盾的。 “实数不可数”得证！

1895年，为了区分自然数的可数性和实数的不可数性，康托把自然数集合的基数（也称为势）记为ℵ0（阿列夫零），称为第一超限数，即可数的无穷大。根据幂集的定义，自然数的幂集的基为2ℵ0，康托证明了这正是实数（连续统）的基数。康托推测，第二超限数ℵ1就是2ℵ0，在ℵ0和ℵ1之间不存在其他超限数，即“连续统假设”。1900年，德国著名数学家大卫·希尔伯特(David Hilbert,1862—1943)把连续统假设列为20世纪有待解决的23个重要数学问题的1号问题。1963年，美国数学家保罗·科恩(Paul Joseph Cohen,1934—2007)证明连续统假设无法通过定理证明，这是一条独立于公理的陈述，无法通过公理证明或反驳。

对于第二超限数ℵ1，康托还有惊人发现：首先，实数和它的真子集（例如0到1之间的实数）是等势的，因此考察0到1之间的实数的性质，可以推广到所有实数。其次，连续统（直线）和平面乃至N维空间的点之间也能建立一一对应关系，只需要把表示各个维度的数字逐位合并成一个新数就行，因此也是等势的。康托被自己的这个发现震撼得说不出话来，他在一封信中写道：“我能看到它，但我不相信它。”

无穷对康托不仅是震撼，还有无尽的折磨。他对无穷的研究当时就饱受争议，遭到哲学家、神学家和数学家的抨击，他的老师利奥波德·克罗内克（Leopold Kronecker，1823—1891，德国数学家与逻辑学家）甚至斥之为无稽之谈。1884年，康托精神崩溃，他自己归因于对连续统的紧张工作和克罗内克的攻击。

不可计算数

从折磨康托的不可数转回具体数字，我们发现的不是秩序，而是更多的诡异。

人们最初认为整数之间的小数排列有序，都可以表示为两个整数之比（分母不为零），也就是后来所谓的“有理数”，这个词反映出人们期望数字能够具有良好的秩序。但这种美好的愿望在公元前六世纪就被打破了，毕达哥拉斯(Pythagoras)的学生希帕索斯(Hippasus)发现，根据毕达哥拉斯定理（勾股定理），直角边均为单位1的直角三角形的斜边无法表示成一个有理数。这一发现让相信数乃万物之本的毕达哥拉斯学派几乎疯掉，他们把希帕索斯扔进了地中海，把这个数称为“无理数”，并一直掩藏这个发现。后来人们逐渐意识到，无理数根本不是个案，相比之下，有理数才是汪洋大海中稀疏的小岛。

代数是数学的一个古老分支，代数方程是解决现实问题强有力的工具。求解整系数方程的整数根在公元前就被人们津津乐道，西方国家称之为丢番图方程2，这也是我国《九章算术》第八章的话题。

代数方程的解（根）称为代数数，好奇的人们不禁要问：“所有的实数都是代数数吗？是否存在不是任何代数方程根的实数？”1740年，瑞士数学家莱昂哈德·欧拉(Leonhard Euler, 1707—1783)猜想这样的数是存在的，并称之为“超越数”（因为它们超越了代数）。100年后的1841年，法国数学家约瑟夫·刘维尔(Joseph Liouville)用阶乘构造出了第一个超越数，1882年，德国数学家费迪南德·林德曼(Ferdinand von Lindemann,1852—1939)证明圆周率π也是超越数，之后自然常数e（代表欧拉）也被证明是超越数，后来找到的超越数越来越多，但是一直没有一种通用方法证明一个实数是否是超越数。

是否存在能够找到所有代数数的通用方法？这就是希尔伯特1900年提出的23个问题中的第10号问题“丢番图方程可解性的判定”。在1928年数学大会上，希尔伯特又提出三个问题，第三个就是比第10号问题更具一般性的判定问题(Entscheidungsproblem)：寻求一种确定的方法，从而能够在有穷步骤内确定某类问题中的任何一个是否具有某一特定的性质。“算法”这个古老词汇从此被赋予了明确的含义。

1936年，美国数学家阿隆佐·邱奇(Alonzo Church, 1903—1995)和图灵分别对判定问题给出了否定回答。两人不约而同地定义了一种“新数”——“可计算数”，只是用词稍有不同：邱奇用的是“Calculable Numbers”，图灵用的是“Computable Numbers”。

图灵在论文开头就给出了定义：“可计算数可以简单描述为其小数表达式可在有限步骤内计算出来的实数。”这里的“有限步骤”(finite means)并不是说确定数位的过程有限（事实上往往是无限的），而是指确定数位的方法是有限的，即算法有限。

有理数显然是可计算的，图灵断言所有代数数都是可计算的，超越数有一部分是可计算的，这其中包括π和e。

图灵证明了所有可计算数是可数的，而实数是不可数的，因此，实数“绝大多数”是不可计算的。

图灵

1930年12月，18岁的图灵第二次参加剑桥大学三一学院的入学考试，仍未被录取。他的第二选择是国王学院。这一次，他决心专攻数学，全心钻研英国大数学家哈代(G. H. Hardy, 1877—1947)的经典著作《纯数学教程》备考。1931年秋，剑桥大学国王学院迎来了最著名的学生之一。

1932年，图灵研读的是一本新书——《量子力学的数学基础》，这是年轻的匈牙利数学家冯·诺伊曼(John von Neumann, 1903—1957)的著作。当时冯·诺伊曼在大卫·希尔伯特身边研究数学，其所在的哥廷根大学是量子力学的圣地，所以写出这样一部著作也在情理之中。

1933年图灵研读的是英国数学家伯特兰·罗素(Bertrand Russell, 1872—1970)的《数学哲学导论》。这部1919年的作品在末尾写到：“如果有学生因为这本书而迈入数理逻辑的大门，并进行认真的研究，那么这本书就达到写作的初衷了。”图灵显然足以慰藉罗素的衷心。

1934年6月，图灵顺利毕业，凭借优异的成绩，获得了国王学院奖金资助，得以留校从事研究工作，次年4月获聘研究员。

1935年春天，图灵修读“数学基础”课程，授课教师是麦克斯韦·纽曼(Maxwell Herman Alexander Newman, 1897—1984)。这门课涵盖了当时尚未解决的判定问题，纽曼把希尔伯特寻求的“确定的方法”称为“机械过程”：用于解决某个问题的一组明确（但无意识的、非智能的）指令集。

1935年5月，图灵考虑到数理逻辑圣地普林斯顿大学，申请宝洁奖学金未果，但没影响这位年轻研究员的心情。初夏时节，图灵躺在剑桥大学的格兰切斯特草坪上，想到了解决判定问题的思路。第二年春天，图灵把《论可计算数及其在判定问题上的应用》论文草稿交给了纽曼。

就在阅读草稿那几天，纽曼收到了邱奇寄来的短文“判定问题的笔记”（1936年3月发表）[3]，基于另一篇已刊出的论文（1936年4月出版）[4]，邱奇对判定问题给出了否定回答。

按照惯例，邱奇已经解决了问题，图灵的论文不能再发表了。但纽曼意识到，图灵的方法与邱奇有很大差异，而且更简洁明了，因此他建议伦敦数学学会发表图灵的论文。伦敦数学学会记录的收文时间是5月28日，正式出版于1936年的11月和12月两期，1937年12月又发表了三页的修订。在论文序言部分，图灵引用了邱奇的两篇论文，声明邱奇“有效可计算性(effective calculability）”概念和自己的“可计算性(computability)”是等价的。

把论文发给伦敦数学学会后，纽曼很快（5月31日）给邱奇写了一封信，比较了两人证明方法的不同，并直言“我觉得如果可能，明年他应该和你一起研究。”结果是，1936年9月，图灵来到普林斯顿大学就读邱奇的博士。

1936年12月，博士新生图灵在普林斯顿数学俱乐部报告了自己的论文，听者寥寥，不足十人，这让他很郁闷，在家书中写道“只有名人才能吸引听众”。

1938年6月，图灵获得博士学位[6]。他的博士论文的要点是：既然存在不可判定的命题，那就以它为真，加入原有系统，从而得到一个新系统，在新系统中，不可判定命题（已经为真）就可判定了。当然新系统又会出现新的不可判定命题，解决方法就是再构造新系统，如此迭代，形成分层结构。这篇论文引入的另一个概念是改进的图灵机，它可以中断计算来寻求外部信息。当然，这些内容与图灵的伟大证明相比都算不了什么，但可以换来一个博士学位。

毕业之际，冯·诺伊曼想以1500美元的年薪招图灵为研究助理。图灵婉拒了，回到剑桥大学继续担任研究员，薪水为每学期10英镑。

图灵机

为了解决判定问题，图灵想象了一种通用计算机器，也就是我们今天所谓的“图灵机”。图灵机后来的影响超过了判定问题本身，图灵可能也意识到了这一点，所以把论文题目定为《论可计算数及其在判定问题上的应用》。

论文第1节“计算机器(Computing Machine)”开门见山地给出了定义：“我们可以将一位正在进行实数计算的人比作一台只能处理有限种情况q1, q2, q3,⋯, qR的机器，这些情况称为‘m-格局’。”1937年5月，邱奇对图灵的论文发表评论文章：“一位持有铅笔、纸和一串明确指令的人类计算者，可以被看作是一种图灵机”，这是“图灵机”一词最早见诸文字的地方。

时至今日，已经出现的所有计算机都是图灵机，但不要因此就认为图灵机就是机器。事实上，在计算机出现之前，Computer本来就是指以计算为工作的人（通常是女性）。人在计算时可能会犯错，这也没超出图灵机的定义：一台根本不会正确工作或不会做任何有意义工作的图灵机还是图灵机，图灵称之为“不符合要求的”图灵机。绝大多数数学教育，甚至可以说所有教育，目的就是把你从一个“不符合要求的”图灵机培养成“符合要求的”图灵机。

就像人做演算需要草稿纸，图灵的机器也是如此：一条无限长的可以左右移动的纸带穿过机器，纸带上是排列整齐的一串方格。任何时候都只有一个方格在机器里，机器可以读、写或擦除方格里的字符，就像一个笨拙的，或者说特别认真的，做四则运算的孩子。

实际上这台装置连四则运算都做不了，它的基本动作就是把纸带左移或右移一格以及在当前方格上进行读、写、擦操作，其他什么动作都不会。不过这正是图灵想要的，在论文第2节，他一口气给出了四个定义（原文没编号）：

1.如果每一阶段的动作完全由格局所决定，我们称这样的机器为自动机。

2.如果一台自动机打印两种符号，第一类符号完全由0和1组成（其他符号称为第二类符号），那么这样的机器就称为计算机器。

3.如果给机器装上空白纸带，并且从正确的初始m-格局开始运转，那么机器打印出来的第一类符号组成的子序列，就叫做机器计算出的序列。

4.在这个序列的最前面加上一个十进制小数点，并把它当作一个二进制小数，所得的实数就称为机器计算出的数。

就这么一台简单的机器，就能打印出所有可计算数？图灵的魔法在于“m-格局”，m指的是机器(machine)，格局(configuration)是机器所处的状态，也就是机器所能处理的情况。机器运行就是在不同状态之间切换，机器的功能取决于格局的定义，也就是会遇到哪些格局？遇到每种格局应该怎么办？

机器如此简单，遇到的情况也简单：目前的方格是空格还是某种字符？能办的事情更简单：左移、右移、写和擦除。简单！这就是图灵机。

在论文第3节“计算机器示例”中，图灵展示了如何定义一组格局，让他的机器打印出一个有理数和一个无理数。

论文第4节“缩略表”定义了一组常用功能，图灵开始称为“骨架表”，后来称为函数，也就是后来程序员都明白的子程序或函数，差别就是程序员是在计算机上写代码，而图灵是在没有计算机的情况下凭空想象。另外他的机器首先关注的不是加减乘除等功能函数，而是在纸带上进行字符串搜寻、拷贝等常用的基本功能。

论文第5节“可计算序列的枚举”。完全格局是指完成一个操作后的纸带快照、读写头的位置和下一个格局。从头开始顺次把完整格局串成行，就是机器完整的历史操作记录，“我们把机器表中这样形式的表达式写下来，并且用分号分隔开来。如此一来，我们就得了机器的完整描述。”

把完整描述进行标准化，再把所有符号替换成阿拉伯数字，就得到一个整数，称为描述数。“一个可计算序列是由计算它的机器所描述。事实上，任何可计算序列都可以通过这样的表描述。”因此，“每个可计算序列至少对应一个描述数，但不存在一个描述数对应多个可计算序列。因此，可计算序列和可计算数是可数的。”简言之，一台机器可以用唯一的一个整数进行编码，它对应一个可计算数，机器是可数的，可计算数也一定是可数的。

论文第6节“通用计算机器”和第7节“通用机的详细描述”是这篇文章的中心，篇幅不长，也相对容易理解。“发明一台计算任何可计算序列的机器是可能的”，这就是图灵的通用机(Universal Machine)。通用机的输入是“开头写有某台机器M的标准描述”的纸带，“可以计算出与M相同的计算序列”。

图灵在论文第7节定义了一组骨架表来完成这个任务，图灵第一次用“指令”这个词代替表或函数，这是区分通用机和之前只能打印一个可计算序列的专用机的关键。用现在的话说，专用机只能完成一个任务，而通用机是可编程的，指令就是纸带上的标准描述。

显然，图灵想象中的机器已经具备了存储（纸带）、软件（描述）和硬件（通用机）等概念，只是他没用我们今天熟悉的词语。15年后的1951年，图灵在曼彻斯特大学做程序员，他是这样定义“编程”的：“一种让数字计算机按照人的意愿工作，并将其正确表达在穿孔纸带上的活动”。

可计算数不可计算

简单总结一下：每台专用机能够产生一个可计算序列，对应一个可计算数，专用机的计算过程可以编码成一个描述数，通用机执行这个描述就可以产生专用机同样的可计算序列。我们是否就此可以得出结论：通用机是否可以算出所有的可计算数？

似乎可以回答“是”。前提是能够设计出所有专用机，用今天的话说就是编写出所有可能的软件，并在计算机上执行这些软件。软件数可数但无穷多，因此完成这个任务的前提是编制无穷多个软件，再无穷无尽地执行下去，这实际上是做不到的。

正确答案应该是“否”。尽管每个可计算数都可以算出来，而且所有可计算数是可数的，但是不存在枚举出所有可计算数的算法，只能一个一个地算，不存在找到所有可计算数的通用算法，这就是“可计算数不可计算”的含义。

证明方法是反用康托的对角线法，这就是图灵在论文第8节提到的“对角线法的应用”。既然可计算数是可数的，那就可以把所有可计算数排成队列，用对角线法构造出一个新数。根据对角线法，这个新数与队列中的任何可计算数都不同，因此是不可计算数。然而，构造这个新数的过程是一个典型的可计算过程，因此这个新数是可计算数。这就导致了矛盾。

矛盾的根源在于不可能对可计算数实行对角线法，上述可计算数队列根本没办法构造出来。

自然数可以逐个枚举，因此找出所有可计算数最直接的思路是逐个检查所有自然数，看它是否描述了一台能够产生一个可计算数的专用图灵机。假定机器D能够检查一个整数是否符合要求的描述数，通用机U能够按符合要求的描述数执行并产生对应的可计算数，机器H按照对角线法调度U和D来逐位产生新数。

下面这个系统开始运行。

H从i=1开始逐个检查所有自然数，用r(i)来记录已找到的可计算数的个数，r(1)=0，之后的规则是：如果整数i不是符合要求的描述数，则r(i)=r(i-1)；反之，r(i) = r(i-1)+1，同时H调用U计算出i对应的可计算数的前r(i)位，并把第r(i)位添加到新数的第r(i)位。

三台机器似乎可以联合起来按部就班地运行了。

但机器H终究会碰到自己所对应的那个整数，设为k。因为H的一切行为正常，因此k是一个符合要求的描述数，D也应该做出这样的判断，按规则H就会把k转换成标准描述，交给U去执行计算任务，也就是产生k对应的可计算数的r(k)位。执行描述数k的机器U就等于H，它会依次产生r(1),r(2),…, r(k-1)，但要产生r(k)时却回到了任务本身，陷入无休止的死循环，永远产生不出r(k)。

出现上述困境，说明假设错误，因此，不存在能够生成所有可计算数的通用算法，也不存在能够判别任何指定数是否是可计算数的万能机器。这意味着：软件要一个一个地去编，软件中的漏洞也要一个一个地去查，没有万能机器能帮我们完成这个任务。

判定问题

从论文第9节“可计算数的范畴”开始剩下的十多页，是可计算数在判定问题中的应用，被《图灵传记》[7]的作者安德鲁·霍奇斯(Andrew Hodges)誉为“有史以来数学类论文中最不寻常的部分”。其实上一节已经体现了证明的精髓。

“判定问题(Entcheidunsproblem)”这个德文词是希尔伯特的助手海因里希·贝曼(Heinrich Behmann, 1891—1970)创造的。在贝曼的想象中，判定过程是这样的：

这个问题的一个特性至关重要，就是证明过程只允许根据指令进行纯机械式的计算，不允许掺杂任何严格意义上的思考活动。如果愿意，我们可以说机械的或像机器一样地思考（说不定以后我们可以用机器来运行这种过程）。

贝曼这番话是1921年5月10日在哥廷根数学协会关于判定问题的座谈会中讲到的（这个材料近年才公开[8]）。

1928年，已届暮年的希尔伯特在国际数学家大会上将判定问题列为三大问题之一，他梦想得到一个肯定回答。英国数学家哈代对此嗤之以鼻，他指出[7]：“当然不存在这样的公理，我们应该感到庆幸，因为如果我们找到了一套机械的规则，为所有数学问题提供解决方案，那么数学家的活动就将结束。”

哈代和希尔伯特各执一词时，图灵还在备考剑桥大学，攻读的正是哈代的《纯数学教程》。四年大学毕业后，他才第一次听到判定问题，躺在剑桥草坪初夏温暖的阳光下，破解了两大顶级数学家争执的世纪难题。

那是1936年，图灵24岁，一个刚刚大学毕业的翩翩少年，为机械意义上的计算画出了明确边界。

这正是： 数可数，非常数

                实数不可数，实在在何处？

                计算又可数，其他为何物？

                其他可想不可及

                机可及，图灵机 

作者介绍

黄铁军

•CCF杰出会员。

•北京大学教授，计算机科学技术系主任、数字媒体研究所所长。

•主要研究方向为视觉信息处理和类脑计算。

脚注

1 岳麓书院讲堂中一副对联的前三句，由旷敏本撰书。旷敏本（1699—1782年），乾隆十九年（1754年）被聘为岳麓书院山长，即现代意义上的“院长”。

2 丢番图方程(Diophantine equation)：有一个或者几个变量的整系数方程，它们的求解仅仅在整数范围内进行。丢番图是古代希腊人，被誉为代数学的鼻祖，他早在公元3世纪就开始研究不定方程，因此常称不定方程为丢番图方程。

参考文献

[1] Cantor G. Ueber eine elementare Frage der Mannigfaltigkeitslehre[M]// Jahresbericht der Deutsche Mathematiker-Vereinigung 1890-1891. 1891,1:75-78.

[2] Petzold C. The Annotated Turing: A Guided Tour Through Alan Turing’s Historic Paper on Computability and the Turing Machine[M]. John Wiley & Sons, 2011. （中文版： 杨卫东,朱皓 等译. 图灵的秘密. 人民邮电出版社, 2012）

[3] Church A. A Note on the Entcheidunsproblem[J]. Journal of Symbolic Logic. 1936,1(1):40-41.

[4] Church A. An unsolvable problem of elementary number theory[J]. American Journal of Mathematics. 1936,58 (2): 345-363.

[5] Turing A. On Computable Numbers, with an Application to the Entscheidungsproblem[C]// Proceedings of the London Mathematical Society. 1936:230-65.

[6] Turing A. Systems of Logic Based on Ordinals (PhD thesis). Princeton University. doi:10.1112/plms/s2-45.1.161.

[7] Hodges A. Alan Turing: The Enigma[M]. Simon & Schuster, 1983: 104.

[8] Ewald W. From Kant to Hilbert: A Source Book in the Foundation of Mathematics[M]. Oxford University Press. 1996, Vol. II, 1113.

中国计算机学会

微信号：ccfvoice           

长按识别二维码关注我们

【精品文章】

点击“阅读原文”，加入CCF。