为什么是图灵——计算理论的缘起
数学与通识
2023-05-30 05:00
贵州
引言
丘奇−图灵论题(Church−Turing Thesis)断言：图灵机是最广义的计算装置。丘奇−图灵论题有时也称图灵论题，是计算机科学的基石，它之于计算机科学，宛如公理之于几何学，牛顿定律之于物理学。计算理论的缘起就是丘奇−图灵论题的形成过程。费曼说微积分是上帝的语言。如果我们把第一次工业革命，归因于机械和能量，贴上牛顿的标签，而把当下正在经历的第四次工业革命归因于信息和计算；那么，上帝的语言该改成图灵机了。至少，英国50英镑钞票的头像刚刚从瓦特换成了图灵。
丘奇−图灵论题的根据就是所知的最广义的计算机制都是等价的，这些机制包括：广义递归函数、λ−演算、珀斯特(Post)系统、图灵机等。这些机制中的任意两个之间都可以互相模仿。这个结论有时也称为图灵定理，因为这些等价性是数学上可证明的。图灵论题是把图灵定理推广到所有可能的、潜在的机制，这个跳跃使得“定理”变成了“论题”，因为没法在现在确定的已知框架中去证明未来的不确定的潜在未知。这需要一种信念(conviction)，信念就是论题。论题既非数学定理也非物理定律，而是一种实用主义的共识。当然，如果把这种共识公理化，也有可能证明丘奇−图灵论题，这本是哥德尔(Kurt Gödel)的期望。逻辑学家德肖维茨和古列维奇近来曾做过努力，他们按照哥德尔指明的方向，试图提出一套可以被广泛接受的公理，在此之上证明丘奇−图灵论题 。但是公理本身也需要某种直觉上的共识，况且，今天对公理的共识也无法消解明天潜在的非议，共识了两千多年的欧几里得公理体系也可以被掰弯。如果公理的根据还没有图灵机更加直觉上可靠的话，其上的证明也是徒劳。
有人说数学中只有定义和定理，没听说过“论题”。此言差矣。极限和连续的定义，其实就是某种“论题”，只不过我们习惯于用定义来指称它，而不说这是“柯西−维尔斯特拉斯论题”(Cauchy−Weierstrass Thesis)，我们的这种习惯恰是因为它符合我们对极限和连续的直觉。
对数学或者理论计算机科学的外行人，我们甚至可以采用一种人类学或社会学的标准：所有最聪明的人想到的机制都是等价的，那么这个论题肯定是靠谱的。为了避免过多地偏离主线，本文中，我们从此以共识作为“论题”的解释。这个共识的结论之一就是不存在比图灵机更强的计算装置。
丘奇−图灵论题是可计算性理论的基础。在计算复杂性理论里，还有“强丘奇−图灵论题”，它假设了更多：所有计算装置之间不仅可以互相模拟，而且模拟的成本是多项式的。姚期智认为丘奇−图灵论题和强丘奇−图灵论题可能更会受到物理定律的约束 。很明显，强丘奇−图灵论题受到的约束更大。肖尔(Peter Shor)提出素数分解的量子算法之后，量子计算就是对强丘奇−图灵论题的明确且现实的挑战，如果素数分解问题被证明不能在多项式时间内求解，那么量子计算对强丘奇−图灵论题的挑战就成功了。若果真如此，将来某一天我们不得不修正强丘奇−图灵论题。姚期智聪明地指出，否定强丘奇−图灵论题，甚至都不一定需要量子力学，经典力学中的−体问题，可能就没法找到多项式时间的解。但即使如此，大家仍然会认可丘奇−图灵论题。
丘奇−图灵论题的主要论点是图灵机捕捉到了直觉上的计算概念，尽管它不是定理。它有如下几种表述方式：
1)所有计算装置都与图灵机等价。
2)人按照算法执行的计算和图灵机等价。
3)人的智能和图灵机的能力等价。
这几种表述代表了不同的哲学观点，一个比一个强。1)虽不是定理，但目前我们知道的所有计算装置都和图灵机等价，例如哥德尔−厄布朗(Gödel−Herbrand)广义递归函数，珀斯特(Emil Post)的各种产生式系统，丘奇(Alonzo Church)的λ−演算，乔姆斯基(Noam Chomsky) 0 型文法等。第一种表述目前是几乎所有理论计算机科学家的共识。第二种和第一种表述有很强的关联，丘奇、珀斯特和图灵的初衷都是为了能够找到一个机械装置可以完整地刻画人施行计算的过程。如果认为算法就是机械过程的话，头两种表述是等价的。哥德尔认可前两种表述，但对第三种表述不买账。认可第三种表述就意味着认可“人是机器”，这是人工智能的终极哲学问题。对丘奇−图灵论题的态度决定了如何应答这个问题。
目前没有证据表明存在着某种自然过程可以展现比图灵机更强的能力，但即使某一天真的发现了这种自然存在(就像有些人期望的那样：可能会有某种生物过程超越图灵机)，也不影响图灵机是最强的机械可计算装置。哥德尔就认为可能存在不可机械计算的心理过程，但他也毫不含糊地认可图灵机是最强、最广义的机械计算装置。哥德尔在1946年为他1931年不完全定理文章写的后记中说：是否存在不等价于任何算法的非机械的过程，与“形式系统”或者“机械过程”的定义的充足性没啥关系。
图灵与图灵机
图灵在剑桥读书时的兴趣是数论和量子力学，但为什么会想到图灵机呢？按照图灵唯一的学生和恋人罗宾•甘地(Robin Gandy)1954年在《自然》杂志上为图灵写的讣告里的说法：图灵本科毕业后在剑桥国王学院做研究员(Fellow)的第一年曾对计算黎曼 zeta 函数的零点感兴趣，由此想到要造一台机器。事实上，图灵怀疑黎曼猜想不成立，于是他一直试图找一个反例。图灵机实际是图灵研究黎曼猜想的副产品。
图灵到美国留学回到英国不久就被军方征召做加密工作。他关于黎曼 zeta 函数零点的计算方法的文章拖到1943年才在《伦敦数学会会刊》上发表 。但图灵最早设计的计算黎曼 zeta 函数的机器是一个可以进行离散近似的模拟装置。这与甘地所说不知是否一回事。二战结束后，图灵在曼彻斯特大学时，又短暂恢复了他对数论的兴趣，他1949-1950年间写了两个程序在英国最早的计算机曼彻斯特 Mark−I 上运行，一个力图找出更大的梅森素数，图灵和合作者验证了当时已知的梅森素数，但没有找到新的；另一个计算黎曼 zeta 函数的零点。其实图灵是想找黎曼猜想的反例，自然无果。图灵的计算结果在他去世前一年才在《伦敦数学会会刊》上发表 ，现在所有计算黎曼 zeta 函数零点的算法都是由图灵的原始算法衍生出来的，于是有人称图灵是计算数论的开拓者 。图灵和哥德尔的初衷不一样，哥德尔的起点和终点都是逻辑，而图灵的起点是数论，终点是计算。
马克斯•纽曼(Max Newman)是英国当时的领袖级数学家，主攻拓扑，他1928年参加了在意大利博洛尼亚召开的国际数学家大会，现场听到身体欠佳的希尔伯特讲到判定问题。两年后判定问题就被哥德尔负面地解决了，颇令希尔伯特不爽。哥德尔的结果激发了纽曼对逻辑的兴趣。他1935年春季学期为剑桥高年级学生开讲“数学基础”，图灵也去听讲。图灵和纽曼深入讨论，理解了希尔伯特期望的是某种机械过程。
图灵利用图灵机否定了可判定性。1936年丘奇在创办《符号逻辑杂志》(JSL)首刊上登了自己关于可判定性问题的两页短文。纽曼收到丘奇寄来的 JSL 首刊时，已经看过图灵的初稿，他马上把丘奇的结果告诉图灵，并给丘奇写信告知自己的学生图灵也在研究同一问题并取得进展，推荐图灵给丘奇做学生。图灵知道丘奇的结果，略有失望和焦急，他在给母亲的信中提到纽曼认为虽然他的结果和丘奇类似，但方法不同也可发表 。事实，图灵稍晚发表文章，从某种意义上帮助了他，让他有机会完善结果。图灵研究了丘奇的λ−演算，很快证明了图灵机和λ−演算是等价的，把证明过程增补到原文作为附录。恰是这个附录增加了所有人的信心。纽曼利用自己在伦敦数学会的影响力，帮助图灵把论文投给该会的会刊，这就是那篇无论怎样赞誉都不过分的经典 。
有意思的是在图灵从普林斯顿得到博士学位回到英国后，他接替纽曼“数学基础”课，而同一学期，维特根斯坦开讲数学哲学，可课程名又恰“数学基础”，这才有了图灵和维特根斯坦1939年在剑桥的遭遇 。
按照数学家、图灵传记作家霍奇斯(Adrew Hodges)的说法，图灵想构造一个可计算的实数集合，这样可以建立整数到实数的一个映射，从而可以创建一套构造主义的实函数理论 。图灵1936年文章的打印稿后来被甘地收藏，打印稿肯定不是图灵亲操打字机，但上面的公式是图灵亲手写的。打印稿的背面，还有一篇图灵手写的笔记，探讨正规数(normal numbers)。所谓正规数就是所有数位都是均匀分布的数。图灵在国王学院的朋友钱珀瑙(David Champernowne)证明了0.12345678910111213…在十进制下是均匀分布的。图灵1933年就得知钱珀瑙的工作，一直和钱珀瑙较劲，想进一步给出计算正规数的算法。霍奇斯认真研读了这篇从未发表的手记，其中图灵提到了机械过程(mechanical process)和构造性枚举(constructive enumeration)，无疑图灵的目的是给出可计算性的机械定义。但笔记中存在错误，图灵后来没有再在正规数上花时间。图灵1932年还写过一篇手稿 Nature of Spirit，其中讨论自由意志和物理确定主义(physical determinism)。图灵 和这两篇手稿的关系密不可分。
最初，“计算”用的词是 calculation，可计算性就是 calculability。因为早期，computer 专指做计算工作的人，通常是指女性。随着1960年代计算机更加普及，大家才开始更多地说 computation，而 calculator 也专指“计算器”。早期关于递归论和计算理论的教科书的演变也可说明递归论逐步演变成可计算性理论的过程。最早的递归函数的专著大概是匈牙利女数学家罗莎培特的《递归函数论》，出版于1951年，1954年由逻辑学家莫绍揆翻译为中文，1958年由科学出版社出版(有意思的是“图灵”被莫先生译为“杜令”)。丘奇的早期学生克里尼(Stephen Kleene)的重要著作《元数学导论》也是由莫先生译为中文的，该书也是以递归函数作为核心。而丘奇后来的学生罗杰斯(Hartley Rogers)常年在麻省理工任教，他1967年的《递归函数论和能行可计算性》(Theory of Recursive Functions and Effective Computability)则以图灵机和图灵机的各种衍生作为讨论基础，更容易懂。同年，明斯基也出了本更加深入浅出的计算理论教科书 Computation: Finite and Infinite Machines，看书名就知道这是以机器为出发点的。罗杰斯和明斯基的几位早期学生毕业时，恰逢美国大学纷纷成立计算机系，他们去计算机系教计算理论的要比去数学系教逻辑的多。随着这些人后来都成为领军人物，这几本教科书的呈现风格也帮助塑造了学科的体系。罗杰斯这本书的影响尤其大。克里尼1967年出版的更初等的教科书《数理逻辑》(Mathematical Logic)也改用图灵机了。
数理逻辑四大论：集合论、模型论、证明论和递归论。其中，递归论逐步演变成了相对独立的可计算性理论。如果从递归论角度考虑，大家更倾向说“丘奇论题”，而从可计算性角度考虑，更倾向说“图灵论题”。因为递归论和可计算性理论是同一个起因，前者源于哥德尔，后者起于图灵。现在计算理论和计算复杂性的教科书叙述方式都是以图灵机为中心，基本不提递归函数。主要原因首先是图灵机和计算密切相关，又好懂，学习递归函数需要更高的门槛。图灵只在早期几篇文章中提到递归函数与图灵机等价，然后就以图灵机为主讨论。图灵没有主动去宣传图灵机，也没有从严肃的数学角度把可计算性的概念推广。否则，也许计算理论作为一门独立深刻的学问可能会更早出现。霍奇斯很遗憾图灵在世时没有写一本关于计算理论与实践(The Theory and Practice of Computing)的书。
图灵关于丘奇−图灵论题的想法也是在不断变化的。一般认为到1950年他写“计算机与智能”时已经默认了人机等价的思路。彭罗斯认为图灵已经假设人脑的任何动作可以规约到(还原到，reducible to)图灵机的动作，而彭罗斯当然不认可这一点，他认为人脑是量子计算机。
为什么不是丘奇？
1930−1931年间，哥德尔在研究递归函数的同时，丘奇正在研究λ−可定义函数。说起来有意思，丘奇最早的论文中是想写，但他的打字员不会打上面的小帽子，便在前面打了个大写的希腊字母 lambda Λ，后来演变成小写的λ。丘奇的本意是定义一个无名函数，结果倒是无意中给这个定义起了个名字：λ−演算，所谓无名到有名。
丘奇的学生克里尼在1933年证明了一大类数论函数都是λ可定义的。丘奇认为这是很强的证据：λ−可定义函数就是“能行可计算性”(effectively calculable)。这就是丘奇论题的根源。丘奇1934年3月在普林斯顿告知哥德尔他的论题，但哥德尔不买账(thoroughly unsatisfactory)。
哥德尔知道原始递归函数并不包括所有的“能行可计算函数”。希尔伯特的助手阿克曼1928年就提出了双递归的概念，即阿克曼函数，这不是原始递归的。哥德尔1934年在普林斯顿高等研究院做了几次关于不完全性定理的讲座，听众中有丘奇和他的两位学生克里尼和罗瑟。哥德尔的讲座由克里尼和罗瑟根据听课笔记整理成35页的小册子，名为 On Undecidable Propositions of Formal Mathematical Systems。受到厄布朗(Jacques Herbrand)的启发，哥德尔在讲座中使用了后来被他称为“广义递归函数”(general recursive function，也译为“一般递归函数”)的定义，哥德尔在文章中说：递归函数(最)重要的性质是给定变量的值的集合，就可以通过一个有限的过程计算出函数值来。这处哥德尔标注有个脚注“…This cannot be proved, since the notion of finite computation is not defined, but it serves as a heuristic principle.”哥德尔1964年又写了一个后记，强调了图灵1936/1937解答了他在脚注中提到的问题。
丘奇就数论中不可解问题在1935年4月19日在美国数学会有个十分钟的演讲，演讲内容的两页纸摘要登在1935年的美国数学会会刊上 ，这里丘奇没有用λ−演算，而是小心翼翼地说：其他“能行可计算性的定义”要么等价于“通用递归函数”，要么更弱。这是丘奇论题的最早的正式说法。此时丘奇还不敢肯定λ−演算事实上也等价于递归函数。
丘奇的学生克里尼1935年7月1日给美国数学会提交的摘要中提到他证明了λ−演算与递归函数的等价性。待丘奇的全文1936年发表于《美国数学杂志》 时，丘奇当然已经知道λ−演算等价于递归函数。于是他非常有信心地论辩：两种机制的等价性确认了它们广义地刻画了能行可计算性。丘奇最早意识到丘奇论题时，是作为定义提出来的，他1936的长文中明确写道“The purpose of the present paper is to propose a definition of effective calculability.”此时丘奇的唯一证据就是λ−演算。
尽管丘奇使用了哥德尔的广义递归函数，但哥德尔还是不认可丘奇论题。图灵的学生甘地以及逻辑学家希格(Wilfried Sieg)在回顾这段历史时讲到，丘奇并没有证明每个演算的原子步骤(atomicstep)是递归的，这是丘奇文章的一个缺陷。哥德尔的智慧当然一眼就看穿了。图灵在1936年的文章中也持有类似的说法，尽管他没有直接说“定义”，但他指出所谓可计算就是图灵机可计算(all computable numbers are ‘computable’)。苏联数学家柯尔莫哥洛夫也对逻辑有深刻研究，他为罗莎培特的《递归函数论》的俄译本写的序里也提到“可构造性的要求可以简单地理解为‘可计算性’ ”。
当更多的机制都被证明和λ−演算等价后，自然会认为这捕捉了一类概念而不是一个单一的想法。这个肯定是比定义更加具有关联性的概念，于是有了论题的说法。
作为丘奇的学生，克里尼也承认丘奇的λ−演算并不令人信服，哥德尔自己都不认可自己的递归函数，而丘奇用λ−演算和哥德尔的广义递归函数套近乎的做法，并不能打动哥德尔。只有“图灵的可计算性概念，令人心服口服”。
丘奇最早是把丘奇论题当作定义来用的。是克里尼在1943年的论文里首次使用“论题”(Thesis)。克里尼在1952年出版的《元数学引论》(Introduction to Metamathematics)中更加正式地提出丘奇论题和图灵论题，这本书影响很大。于是论题比定义更加广泛地使用。其实丘奇−图灵论题的一个哲学推论是智能可以还原为图灵机，如果把丘奇−图灵论题当作定义来用，肯定会引发无谓的哲学争论，而这些争论在图灵1950年的论文中，已经预见到了，所以那篇文章的很大一部分就是作为对这些已经预见到的争议的回答。
数学家和逻辑学家多采用递归函数，他们称那个分支为递归论；而后起的计算机科学家或者计算理论家更多采用图灵机，他们称可计算理论。而丘奇的λ−演算则无人问津。甚至他自己的学生克里尼在讲课和写书时也鲜有提及。倒是后来人工智能的先驱麦卡锡(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月在普林斯顿的演讲最早公开提出广义递归函数。此时又恰逢丘奇想到丘奇论题。
哥德尔不完全性定理和丘奇论题的关系有两个方面。首先，正如克里尼指出的，如果哥德尔不完全性定理不成立，丘奇1936年的论文也不成立。反之，哥德尔不完全性定理可由丘奇的结果推出来。其次，哥德尔用到的递归函数，启发了丘奇想到丘奇论题。
如果非要说也有哥德尔论题的话，那这个论题可以表达如下：所有机器可计算的函数可以用最广义的递归来定义 。哥德尔虽然没有想出令自己满意的计算装置，但他是那个一锤定音的人。随着他名声的提升，大家越发认可他的话。像丘奇、图灵甚至冯•诺依曼都认为他的看法不容置疑，更不要说晚辈的王浩、克雷塞尔(Georg Kreisel)、克里尼和罗瑟了。
哥德尔在1930年代就认识到图灵机可以作为机械可计算性的定义：“That this really is the correct definition of mechanical computability was established beyond any doubt by Turing.”哥德尔认可图灵机捕捉到了“人作为计算机”(human computer)的直觉，并且把这个功劳都归功于图灵。之后在他不多的公开发声(文章或演讲)中多次力挺图灵，并且措辞几乎相同。哥德尔1946年为“普林斯顿大学200年”写的文章中的一段话是最多被提到的：“one has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i. e., one not depending on the formalism chosen.” 哥德尔此处所说的“绝对”，是指图灵机不是相对的概念，它不需要依靠别的机制，它是最基本的装置。
关于图灵机和哥德尔自己的一阶逻辑的不完全性的结果，哥德尔1939年在圣母大学的演讲里，利用莱布尼茨的“计算机”(Calculemus)把它们巧妙地关联起来：“假设机器有一个曲柄，每当你转动曲柄一周，机器会写下谓词演算的一个重言式，如果你足够频繁地转动曲柄，它就会写下所有存在的重言式……。所以就谓词演算公式的推导而言，这台机器真的会完全取代思维。这将是一个字面意义上的思维机器。对于命题演算，你可以做得更多。你可以建造一台打字机形式的机器，这样如果你输入命题演算的公式，机器就会响铃[如果公式是重言式]，如果不是，就不会响铃。你可以对一元谓词演算做同样的事情……如果是谓词逻辑，你做不出来这样的机器。所以这里已经可以证明莱布尼茨“计算机”程序不能被实现，也就是说，对于判定一个公式是否是重言式这么简单的问题，人脑也绝不会被机器所取。”这里，由此可看出哥德尔一方面为图灵机所信服，另一方面他认为人脑能做图灵机不能做的事情，更具体地说是对谓词逻辑的判定问题 。这一点我宁愿相信哥德尔1939年并没有想得很清楚，因为谓词逻辑不可判定这事，恐怕人脑也没辙。人脑和机器的差别，我们能如此天真地搞明白？
哥德尔在1951年的 Gibbs 讲座中，再次突出了图灵的贡献。他1968年给克雷塞尔的信中，强调：“But I was completely convinced only by Turing's paper.”哥德尔为丘奇−图灵论题提供了信用担保。但他本人又和丘奇和图灵的思路不完全一致。虽然哥德尔认可图灵的“机械过程”，但他不认为心理活动可以归约为机械过程。哥德尔认为图灵犯了“哲学错误”。哥德尔在1943年的普林斯顿演讲中提及可定义性概念“会涉及研究数学的人的心理学有关的数学之外的因素”。图灵机恰恰在这方面向前走了一大步。
1965年戴维斯在编辑重要文集 Undecidable 时，曾给哥德尔去信请教他对丘奇−图灵论题的看法，哥德尔在1965年2月15日给戴维斯的回信中明确地表明哥德尔1934的脚注并不构成丘奇论题，只是说明“有限计算过程”等价于递归过程。哥德尔认为人在计算时的状态是有限的，而人的整个发展经历的状态可能是无限的。
为什么不是珀斯特？
珀斯特在几位计算理论的先驱里最年长，名气却最小。但他是个先知，一个悲剧性人物。他是马丁•戴维斯(Martin Davis)在被称为“穷人的哈佛”的纽约城市学院(CCNY)读本科时的老师，戴维斯最终到普林斯顿随丘奇读了博士。珀斯特1921年在哥伦比亚取得博士学位后在普林斯顿做过一年博士后，那时丘奇在普林斯顿读本科。戴维斯和珀斯特都是犹太人，他们都感到普林斯顿那个年代对犹太人的不友好。戴维斯对珀斯特极为尊重，倒反而较少提到他的博士导师丘奇。
珀斯特迟到的名声很大程度上是因为戴维斯的推动。戴维斯编辑的文集 Undecidable，是可计算理论和理论计算机科学的重要早期文献的汇编，其中最值得看的是戴维斯为这些重要论文写的评注。这本文集被戴维斯题献给珀斯特。珀斯特一生都受心理疾病的困扰。他1921年的博士论文证明了《数学原理》中的命题逻辑的完全性和一致性，同时还对维特根斯坦和皮尔士的真值表做了梳理。这部分工作发表于《美国数学杂志》。珀斯特把句法推导的概念推广，得出了“产生式系统”(production system)，tag 系统是“产生式系统”的进一步简化。
最早在逻辑学之外利用产生式系统的是语言学家乔姆斯基，他从与他同年的戴维斯处了解到珀斯特的工作 。乔姆斯基那篇现代语言学的开山之作“语言描述的三个模型” 中引用了数学家罗森布鲁姆(Paul C. Rosenbloom)的教科书《数理逻辑原理》(The Elements of Mathematical Logic)，其中正式地讲述了产生式系统。乔姆斯基这篇文章对计算机科学也有深刻影响。编程语言 Algol 中引入的 BNF (Backus Normal Form，巴克斯−诺尔范式)是计算机科学的重要工具，BNF 就受到了珀斯特产生式系统的启发。
王浩、寇克(John Cocke，因为 RISC 架构获图灵奖)和明斯基在1961-1963年间分别证明了2−tag 系统可以模拟图灵机 。他们的工作让更多的数学家和逻辑学家重新审视珀斯特早期的工作。
1921年对珀斯特极其重要，也是在这一年他证明了罗素−怀特海《数学原理》的不完全性，这部分更重要的工作却没有发表。差不多此时，他开始受到心理疾病的困扰。1938年10月28日珀斯特见到了哥德尔，心中五味杂陈，第二天心情平静后给哥德尔写了个明信片，自嘲且苦涩地说：“如果我要是哥德尔的话，我在1921年就已经证明了哥德尔定理。”哥德尔的回复很客气，但哥德尔没有为他呼吁。珀斯特不甘心，许多年后，他把1921年的成果写成长文，题为“Absolutely unsolvable problems and relatively undecidable propositions−an account of an anticipation”，1941年投给《美国数学杂志》，但被拒稿了。1942年3月2日，杂志主编赫尔曼•外尔(Hermann Weyl)给珀斯特写了封语气同情但态度坚决的信，说“……但是，我们不能把时钟倒拨，《美国数学杂志》不是发表历史回顾的地方……” 。该文后来被收录在马丁•戴维斯1994年为珀斯特编辑的文集中 。
他1936年和图灵同时且独立地提出了计算装置的数学描述：有限组合过程，他期盼有限组合过程可以被证明和哥德尔递归函数是等价的。他1936年的文章一共只有四页，第一页就明确给出了定义。珀斯特的盒子(box)就是图灵机纸带上的一个格子，worker 就是图灵机的有限自动机的head。其他操作几乎和图灵机一模一样，因为和图灵机太像了，后人也称之为珀斯特−图灵机器。注意，珀斯特的所谓 direction 不是方向，而是指令(instruction)。和图灵机略有不同的地方是，图灵机使用“内部状态”(internal configuration)，而珀斯特直接用了指令。这也使得珀斯特机器更像当代的计算机。这启发了明斯基对计算理论的兴趣。王浩机其实就是对珀斯特机的某种改造。尽管戴维斯一直在为珀斯特发声，力图提升珀斯特的历史地位。但珀斯特1936年的文章确实不如图灵同年的文章详实、严谨。珀斯特并没有给出严格的证明 ，而图灵证明了图灵机等价于λ−演算。
值得指出，珀斯特反对把“论题”当作“定义”。如果把它当作定义，就会停止人们对这个问题的“不断探索”。正如 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)苦口婆心地劝哲学家应该学一些计算理论。其实，在中学和大学中像教数学和物理一样，教计算理论的入门课，也未尝不可。逻辑、数学、物理为所有其他学问奠定了扎实的基础，计算理论为我们思考几乎所有问题划定了边界，有些人在边界里面做工程，还有些人试探边界是否有弹性。例如，“机器=人”，同意的一派和反对的一派之间的争辩会激励学问的进步。
恰恰因为丘奇−图灵论题，使得计算机科学比电气工程更加接近数学和物理学，也正因为同样的原因，使得计算机科学既不同于数学，也不同于物理学。图灵机在数学与物理，唯心与唯物之间建立了某种比以往任何时候都更令人踏实的桥梁。这也是为什么大家为图灵的贡献和故事所感动，即使是最冷酷的数学家。 |
雷达卡
发表于 2023-9-27 10:57
QQ好友和群
QQ空间
腾讯微博
腾讯朋友
分享
收藏
顶
踩
提升卡
变色卡
抢沙发
千斤顶
显身卡
发表于 2023-9-27 21:16
