图灵机：在没有计算机的时候，我们如何谈论计算？( 三 ) 人类的灵魂

那篇论文中的思想与我所说的没有任何具有实际意义的区别。他能发表那篇论文已经很幸运了，我的意思是阿隆佐·邱奇（AlonzoChurch）用其他方法得到了同样的结果。

文章图片
文章地址：https://cacm.acm.org/magazines/2009/9/38898-an-interview-with-maurice-wilkes/fulltext
需要注意的是，在接受采访时， MauriceWilkes已经96岁高龄了，他本人是著名的计算机先驱， EDSAC（ElectronicDelayStorageAutomaticCalculator ，即电子延迟存储自动计算器）之父。在他这段奇怪的回答中，可以看出他对图灵崇高地位的嫉妒。这两个人显然合不来！我们也看到了MauriceWilkes对理论的不屑：尽管把机器编码为数字是对存储程序计算机的预期，但图灵的工作是纯粹的数学，没有任何工程意义。图灵对实际的计算机工程很感兴趣，但他多次试图参与到真正的工程里，却屡屡受挫。
而那些关于邱奇的言论又是如何评价的呢?
5图灵和邱奇在普林斯顿在图灵做研究的时候，许多研究人员关注的是“有效可计算性”的想法。此处我推荐读者看看邱奇的《初等数论的一个不可解问题》（见下图）。

文章图片
论文链接：https://www.jstor.org/stable/2371045?origin=crossref
老实说，这篇论文读起来很吃力，但它能带我们身临其境。本文给出了一个λ-演算的定义，一个递归函数的定义(在Kleene（克莱尼）/G?del（哥德尔）意义上) ，以及λ-演算中范式的存在性和等价性的一些不可判定结果。邱奇和克莱尼已经证明了λ可定义函数和递归函数的等价性；而当图灵在普林斯顿的时候， λ可定义函数和图灵可计算函数之间的等价性也得到了证明，于是我们便得到了邱奇-图灵论题，这个论题的指的是有效可计算的函数恰恰是那些数学上等价类中的函数。
6邱奇-图灵论题正确吗？正如人们常说的那样，我们无法证明这个论题正确与否，因为「有效可计算」不是一个精确的概念。我们可以把图灵可计算函数看作是一个颇为包容的类，因为其包括了许多在宇宙生命周期内无法计算的函数。借助Ackermann函数，我们可以很容易地得到范例。
Ackermann函数的现代形式如下：

文章图片
文章链接：https://lawrencecpaulson.github.io/2022/02/09/Ackermann-example.html
如果你定义f(n)=A(n,n) ，就不能指望计算出偶数f(4) 。 g(n)=A(4,n)尽管是原始递归，但几乎无法计算。
尽管在20世纪30年代之前都还没有数字计算机，但有效可计算性的概念已为数学家所熟知。有效性的概念在希腊几何的直线结构和圆规结构中就早已出现，有效性也是判定问题和希尔伯特第十问题的组成部分。与哥德尔的递归函数和邱奇的λ微积分相比，图灵的概念的天才之处在于其显然是正确的。哥德尔自己也不确定他的递归函数是否抓住了计算的思想，我们也不清楚邱奇的想法是否正确。唯有图灵的想法简单而自然。图灵的想法与其他模型在可证明性上是等价的，并为所有这些模型提供了合理解释。他在1937年发表的论文《可计算性和λ-可定义性》中指出了这一事实。
本文旨在证明作者提出的可计算函数与邱奇的λ-可定义函数以及由埃尔布朗和哥德尔所提出的并由克莱尼发展的一般递归函数是相同的。这几个相同的函数都证明了每个X-定义函数都是可计算的，并且每个可计算函数都是一般递归的。注意，图灵写的是「可计算的」，而我们要写「图灵可计算的」。