为什么是图灵 —— 计算理论的缘起
发表于 ・ 资讯中心
单击上方“图灵人工智能”,选择“星标”公众号
您想知道的人工智能干货,第一时间送达

引言


丘奇−图灵论题的主要论点是图灵机捕捉到了直觉上的计算概念,尽管它不是定理。它有如下几种表述方式:
1)所有计算装置都与图灵机等价。
2)人按照算法执行的计算和图灵机等价。
3)人的智能和图灵机的能力等价。

图灵与图灵机
图灵在剑桥读书时的兴趣是数论和量子力学,但为什么会想到图灵机呢?按照图灵唯一的学生和恋人罗宾•甘地(Robin Gandy)1954年在《自然》杂志上为图灵写的讣告里的说法:图灵本科毕业后在剑桥国王学院做研究员(Fellow)的第一年曾对计算黎曼 zeta 函数的零点感兴趣,由此想到要造一台机器。事实上,图灵怀疑黎曼猜想不成立,于是他一直试图找一个反例。图灵机实际是图灵研究黎曼猜想的副产品。




图灵利用图灵机否定了可判定性。1936年丘奇在创办《符号逻辑杂志》(JSL)首刊上登了自己关于可判定性问题的两页短文。纽曼收到丘奇寄来的 JSL 首刊时,已经看过图灵的初稿,他马上把丘奇的结果告诉图灵,并给丘奇写信告知自己的学生图灵也在研究同一问题并取得进展,推荐图灵给丘奇做学生。图灵知道丘奇的结果,略有失望和焦急,他在给母亲的信中提到纽曼认为虽然他的结果和丘奇类似,但方法不同也可发表 。事实,图灵稍晚发表文章,从某种意义上帮助了他,让他有机会完善结果。图灵研究了丘奇的−演算,很快证明了图灵机和−演算是等价的,把证明过程增补到原文作为附录。恰是这个附录增加了所有人的信心。纽曼利用自己在伦敦数学会的影响力,帮助图灵把论文投给该会的会刊,这就是那篇无论怎样赞誉都不过分的经典 。



数理逻辑四大论:集合论、模型论、证明论和递归论。其中,递归论逐步演变成了相对独立的可计算性理论。如果从递归论角度考虑,大家更倾向说“丘奇论题”,而从可计算性角度考虑,更倾向说“图灵论题”。因为递归论和可计算性理论是同一个起因,前者源于哥德尔,后者起于图灵。现在计算理论和计算复杂性的教科书叙述方式都是以图灵机为中心,基本不提递归函数。主要原因首先是图灵机和计算密切相关,又好懂,学习递归函数需要更高的门槛。图灵只在早期几篇文章中提到递归函数与图灵机等价,然后就以图灵机为主讨论。图灵没有主动去宣传图灵机,也没有从严肃的数学角度把可计算性的概念推广。否则,也许计算理论作为一门独立深刻的学问可能会更早出现。霍奇斯很遗憾图灵在世时没有写一本关于计算理论与实践(The Theory and Practice of Computing)的书。
图灵关于丘奇−图灵论题的想法也是在不断变化的。一般认为到1950年他写“计算机与智能”时已经默认了人机等价的思路。彭罗斯认为图灵已经假设人脑的任何动作可以规约到(还原到,reducible to)图灵机的动作,而彭罗斯当然不认可这一点,他认为人脑是量子计算机。
为什么不是丘奇?
1930−1931年间,哥德尔在研究递归函数的同时,丘奇正在研究−可定义函数。说起来有意思,丘奇最早的论文中是想写,但他的打字员不会打上面的小帽子,便在前面打了个大写的希腊字母 lambda Λ,后来演变成小写的。丘奇的本意是定义一个无名函数,结果倒是无意中给这个定义起了个名字:−演算,所谓无名到有名。

丘奇的学生克里尼在1933年证明了一大类数论函数都是可定义的。丘奇认为这是很强的证据:−可定义函数就是“能行可计算性”(effectively calculable)。这就是丘奇论题的根源。丘奇1934年3月在普林斯顿告知哥德尔他的论题,但哥德尔不买账(thoroughly unsatisfactory)。



数学家和逻辑学家多采用递归函数,他们称那个分支为递归论;而后起的计算机科学家或者计算理论家更多采用图灵机,他们称可计算理论。而丘奇的−演算则无人问津。甚至他自己的学生克里尼在讲课和写书时也鲜有提及。倒是后来人工智能的先驱麦卡锡(John Mc Carthy)在设计 Lisp 语言时用到了 Lambda,导致现代编程语言中的几乎所有重要机制都源于−演算,例如 function/procedure, variable binding, parameter passing, scoping 等。麦卡锡尽管也出自丘奇所在的普林斯顿数学系,但他并非丘奇的门生。

无论如何,图灵赢得了最多的荣誉(credit)。Google 把扫描过的书做了词频统计,做到 Ngram Viewer 中,我们在其中查 Church−Turing Thesis 和Turing Thesis,作为比对,可以看出越来越多的人使用Turing Thesis。
为什么不是哥德尔?
哥德尔1931年著名的不完全性定理文章中用到了“递归函数”的说法,这个提法后来被更精确地称为“原始递归函数”(primitive recursive function),以示与后来“广义递归函数”(general recursive function,也译为“一般递归函数”)的区别。厄布朗1931年4月7日给哥德尔写信,启发了哥德尔想到广义递归函数。7月25日哥德尔回复了厄布朗 ,两天后,厄布朗因登山事故去世,年仅23岁。哥德尔1934年3月在普林斯顿的演讲最早公开提出广义递归函数。此时又恰逢丘奇想到丘奇论题。



1965年戴维斯在编辑重要文集 Undecidable 时,曾给哥德尔去信请教他对丘奇−图灵论题的看法,哥德尔在1965年2月15日给戴维斯的回信中明确地表明哥德尔1934的脚注并不构成丘奇论题,只是说明“有限计算过程”等价于递归过程。哥德尔认为人在计算时的状态是有限的,而人的整个发展经历的状态可能是无限的。
为什么不是珀斯特?
珀斯特在几位计算理论的先驱里最年长,名气却最小。但他是个先知,一个悲剧性人物。他是马丁•戴维斯(Martin Davis)在被称为“穷人的哈佛”的纽约城市学院(CCNY)读本科时的老师,戴维斯最终到普林斯顿随丘奇读了博士。珀斯特1921年在哥伦比亚取得博士学位后在普林斯顿做过一年博士后,那时丘奇在普林斯顿读本科。戴维斯和珀斯特都是犹太人,他们都感到普林斯顿那个年代对犹太人的不友好。戴维斯对珀斯特极为尊重,倒反而较少提到他的博士导师丘奇。



值得指出,珀斯特反对把“论题”当作“定义”。如果把它当作定义,就会停止人们对这个问题的“不断探索”。正如 Davis 指出的,珀斯特不喜欢还原到“定义”或“公理”,更倾向还原到“自然定律”(natural law)。他认为丘奇等人的工作揭示了“智人数学化能力的局限”,而不只是机器的局限。
1921年,珀斯特错失了不完全性定理,而1936年他再次错失了“珀斯特论题”。珀斯特要么文章发表晚,要么文章没有提供足够的细节。图灵占尽天时地利人和。天时,图灵在发表文章前看到了丘奇的结果,他随后加了个附录,证明了图灵机和−演算的等价,而−演算和哥德尔递归函数的等价性已经被丘奇和克里尼证明,于是图灵机成为递归函数的替代品;地利,纽曼在剑桥给了图灵接触丘奇工作的机会;人和,哥德尔认可图灵机。


超计算:超越丘奇−图灵论题
丘奇−图灵论题的一个自然结果就是不可能存在比图灵机更强的计算装置。那么假设存在一种装置超越图灵机,会出现什么结果呢?新西兰逻辑学家杰克•寇普兰(Jack Copeland)利用“超计算”(hypercomputation)来指称在可计算性上超越丘奇−图灵论题的装置。注意,这和“超级计算”(super-computing)不同,超级计算是量变,而超计算是质变。有的人会用不同的术语指称“超计算”,例如彭罗斯就用“非算法”(non−algorithmic) ,还有人用“超图灵”(Trans−Turing或者 Super-Turing)。其实图灵本人就曾提出过 oracle (译为“神谕”或“天启”)的思想:一个图灵机可以问 oracle 任何问题。当 oracle 的能力超过图灵机时,这个图灵机就有了超计算的能力。oracle 的存在有理论的方便性,但具备超计算能力的 oracle 还都不存在物理实现的可能性。
一个最常被提及的超计算模型是实数计算模型 BSS ,BSS 分别是三位数学家名字的首字母(Lenore Blum,Michael Shub 和 Steve Smale)。BSS 的主要用途是为数值计算中的算法分析提供理论基础。BSS 模型的一个很大假设是,任意精度的实数四则运算可在单位时间内完成,这在数值分析中是有用而又方便的假设,但目前尚不知道如何在物理上实现这个。其实即使在数值分析之外,我们经常做类似的假设,例如,在排序算法分析中,任意精度的数(可能是实数)之间的比较是单位时间的。
BSS 和图灵机的本质区别可溯源到二十世纪三十年代初期。那时哥德尔证明了整数的一阶逻辑是不可判定的。但几乎在同时,塔尔斯基证明了实数的一阶理论(几何和代数)则是可判定的。我们可以说图灵机和 BSS 分别是哥德尔定理和塔尔斯基定理的计算体现。有些复杂性的性质,BSS 也和图灵机不同。比如线性规划在图灵机上被证明是多项式时间的,但在 BSS 上,复杂度是啥,目前不知道。如果在 BSS 上可以找到线性规划的多项式时间的话,在图灵机上就可以找到强多项式时间算法。这个问题被斯梅尔称为最重要的计算机科学的理论问题。
二十世纪八十年代初就有人证明三层以上的神经网络可以逼近任意连续函数。八十年代末期,史蒂夫•贾德(Steve Judd)在他的博士论文里证明了三层以上的神经网络学习问题在图灵机上是 NP 完全的。作者本人则证明了在 BSS 模型上,类似的神经网络学习问题等价于线性规划问题 。目前各种神经网络学习算法都是工程,鲜有科学,神经网络算法多是些经验算法外加调参数,从业人员也多数没有计算理论的训练。在各种学习算法里,很少看到目前关于什么算法适合什么问题的理论指导。目前来看,BSS 模型没法物理实现,在某些情况下,可作为模拟计算看待。BSS 至少为简化带实数的算法分析提供了工具。
结语
物理学家费曼曾说人分两类,一类是懂了足够多的数学从而能够理解自然,还有一类则不是。这基本是所有物理科学家的共识,也就是说物理学为其他科学奠定基础,而自己的基础则是数学。逻辑学家曾经有过一个一厢情愿的想法,即逻辑为数学奠定了基础,但这个想法数学家们并不买账。王浩曾经对此失望并不解。那时,数学家普遍认为逻辑学家构造出来的问题太人为,和他们正在工作的问题关系不大。当珀斯特以及后来的苏联数学家们,如马尔可夫(Andrey Markov Jr.) 开始建立数学中具体问题和逻辑的关系时,大多数逻辑学家的注意力已经从数学转移,他们找到了新的服务对象:计算机科学。丘奇−图灵论题,作为逻辑学家的贡献,确实为计算机科学奠定了基础,并一直在直接或间接地推动计算机科学及其衍生学科(例如人工智能)的发展。这算是对逻辑学家们的安慰吧。
新古典经济学假设“完美理性”(perfect rationality),后来又有司马贺的“边界理性”(bounded rationality)。拉塞尔(Stuart Russell)和诺维格(Peter Norvig)的人工智能教科书 套用了经济学和心理学的说法来给智能体(agent)做定义,“计算理性”(calculative rationality)对应“完美理性”,“有界优化” (bounded optimality)对应“边界理性”。于是经济学里的“理性人”,就变成了人工智能里的智能体。从计算理论的角度考虑,一个智能体就是图灵机,“计算理性”的边界就是可计算性,而“有界优化”的边界就是计算复杂性。
计算理论是新时代的通识。理论计算机科学家阿伦森(Scott Aaronson)苦口婆心地劝哲学家应该学一些计算理论。其实,在中学和大学中像教数学和物理一样,教计算理论的入门课,也未尝不可。逻辑、数学、物理为所有其他学问奠定了扎实的基础,计算理论为我们思考几乎所有问题划定了边界,有些人在边界里面做工程,还有些人试探边界是否有弹性。例如,“机器=人”,同意的一派和反对的一派之间的争辩会激励学问的进步。
恰恰因为丘奇−图灵论题,使得计算机科学比电气工程更加接近数学和物理学,也正因为同样的原因,使得计算机科学既不同于数学,也不同于物理学。图灵机在数学与物理,唯心与唯物之间建立了某种比以往任何时候都更令人踏实的桥梁。这也是为什么大家为图灵的贡献和故事所感动,即使是最冷酷的数学家。





作者简介 :尼克(张晓东),乌镇智库理事长。早年曾任职于哈佛大学和惠普,后连环创业,曾获吴文俊人工智能科技进步奖。
版权声明
转自数学文化,版权属于原作者,仅用于学术分享
文章精选:
发表评论:
◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。