【图铃】王王讲历史：图灵受到过奖，哥德尔和秋才是计算机科学之父。

ACM关于图灵的声明并不完全错误，但和其他声明一样，非常具有误导性。ACM说图灵“明确了计算的数学基础和局限性”，但几十年来，很多人已经这样做了。科学盖棺的时候，重要的问题是谁先提出的？

图灵在奥地利数学家库尔特哥德尔(Kurt GER DEL)的开创性工作5年后，图灵的顾问美国人ALONZO CHURCH(ALONZO CHURCH)在1年后发表了论文。当然，他在1936年的论文中引用了这两篇文章。带着这一点，让我们更详细地看看现代计算机科学的诞生。

2哥德尔的作品(1906-1978年)

20世纪30年代初(1931年)，哥德尔成为现代计算机理论科学的创始人。他引进了基于整数的通用编码语言。它允许公共。

理的形式形式化任何数字计算机的操作。哥德尔用它来表示数据(如公理和定理)和程序 (如数据操作的证明生成序列)。他构建了一个著名的形式命题，讨论了其他形式命题的计算，特别是自指式命题，这意味着它们是不可判定的，给出了一个计算定理证明，系统地从一组可列举的公理中列举出所有可能的定理。因此，他确定了算法定理证明、计算和任何基于计算的人工智能的基本极限。

哥德尔

20世纪40 -70年代早期的人工智能实际上是关于定理证明和通过专家系统和逻辑编程的哥德尔风格的演绎。

哥德尔建立在Gottlob Frege（在1879年他引入了第一个形式语言)、Georg Cantor(1891年，对角化技巧)、Thoralf Skolem(1923年他引入了原始递归函数)和Jacques Herbrand(他发现了Skolem方法的局限性)的早期工作的基础上。这些作者是建立在莱布尼茨（Gottfried Wilhelm Leibniz）的形式代数思想(1686)的基础上，它与后来1847年的布尔代数是演绎等价的。

莱布尼茨（Gottfried Wilhelm Leibniz）是“计算机科学之父”的候选人之一，他被称为“世界上第一位计算机科学家”，甚至被称为“有史以来最聪明的人”。他不仅是第一个发表无限小微积分(1684)的人，也是第一个描述穿孔卡片控制的二进制计算机原理(1679)的人。(二进制编码本身要比这古老得多，可以追溯到古埃及。二进制运算的算法部分是相对较新的。比较Juan Caramuel y Lobkowitz发表的二进制编码(1670)和Thomas Harriott未发表的论文)

此外，莱布尼茨追求一个雄心勃勃且极具影响力的项目，通过一种通用语言和用于推理的一般演算来回答所有可能的问题:《普遍性特征与微积分推理者》 (灵感来自13世纪的学者Ramon Llull)。然而，在20世纪30年代早期，哥德尔的著名结果显示了莱布尼茨计划的局限性。

3 丘奇的工作 (1903–1995)

1935年，丘奇（Church）证明了希尔伯特和阿克曼（Hilbert & Ackermann）的决策问题没有通解，从而导出了哥德尔结果的一个推论。为了做到这一点，他使用了另一种通用编码语言，称为非类型Lambda微积分（Untyped Lambda Calculus），它构成了极具影响力的编程语言LISP的基础。

丘奇

1936年，图灵引入了另一个通用模型，这可能是其中最著名的一个(至少在计算机科学领域): 图灵机。他重新推导了上述结果。当然，他在1936年的论文中同时引用了哥德尔和丘奇。

同年，波斯特（Emil Post）发表了另一个独立的通用计算模型，也引用了哥德尔和丘奇。丘奇证明了他的模型与哥德尔的模型具有同样的表达能力。然而，据美籍华裔数学家、逻辑学家、哲学家王浩说，是图灵的工作(1936)使哥德尔相信了自己（1931）和丘奇(1935)方法的普适性。

就像哥德尔在1931- 1934年发明的最初的通用语言一样，图灵机和1936年发明的波斯特机器都是理论的、不切实际的结构，不能直接作为现实世界计算机的基础。值得注意的是，康拉德·祖斯为第一台实用的通用程序控制计算机申请的专利也可以追溯到1936年。

4 图灵究竟做了什么

图灵和波斯特在1936年究竟做了什么，是哥德尔(1931)和丘奇(1935)没有做过的?

有一个看似微小的差异，但其重要性后来才显现出来：哥德尔的许多指令序列都是数字编码的存储内容的整数乘法，但他并不关心这种乘法的计算复杂度会随着存储空间的增大而增加。同样，丘奇也忽略了他的算法中基本指令的上下文依赖性时空复杂性。

然而，图灵和波斯特采用了传统的、简化主义的、极简主义的二进制的计算观点。他们的机器模型只允许非常简单、复杂度不变的基本二进制指令，比如莱布尼茨(1679)的早期二进制机器模型和祖斯1936年的专利申请。他们并没有利用这一点——图灵只是用他的(相当低效的)模型来重新表述哥德尔和丘奇关于可计算极限的结果。然而，后来，这些机器的简单性使它们成为复杂性理论研究的方便工具。(我也很高兴在无穷无尽的计算中使用并推广了它们）

祖斯

有世人称，图灵至少为人工智能奠定了基础。这有什么意义吗?

• 1948年，图灵写下了与人工进化和学习人工神经网络有关的想法，其架构至少少可以追溯到1943年(参见自20世纪20年代以来与之密切相关的物理学工作)。图灵没有发表，这也解释了为什么他的论文缺乏影响力。

• 1950年，他提出了一个简单而著名的主观测试，用来评估计算机是否智能。

1956年，在达特茅斯的一次会议上，约翰·麦卡锡（John McCarthy）创造了“人工智能”一词，作为相关研究的新标签。然而，第一次关于人工智能的会议早在1951年就在巴黎召开了，当时的人工智能仍被称为控制论，重点是与基于深度神经网络的现代人工智能非常一致。

但是早在1914年，西班牙人Leonardo Torres y Quevedo就已经成为20世纪第一个实用人工智能的先驱，他创造了第一个可以使用的象棋终局棋手(当时象棋被认为是一种仅限于智能生物领域的活动)。几十年后，当人工智能先驱Norbert Wiener在1951年的巴黎会议上与它交手时，这台机器仍大展拳脚。

然而，祖斯（Konrad Zuse）早在1945年就有了更通用的象棋套路。他也在1948年应用了他开创性的Plankalkül编程语言来证明定理，远早于Newell和Simon 1956年的工作。通过专家系统自动证明和推导定理，为人工智能奠定了形式化的基础(有些人错误地认为他也证明了人类优于人工智能)。总之，人工智能的基础性成就远远早于图灵的成就。

5 奇怪的颁奖

哥德尔理论计算机科学奖以哥德尔命名，但目前奖金更加丰厚的ACM 的图灵奖成立于1966年，以表彰“对计算机领域具有持久和重大技术重要性”的贡献。有趣而尴尬的是，哥德尔(1906-1978)从未得到过一个，尽管他不仅为该领域的“现代”版本奠定了基础，而且还在给约翰·冯·诺依曼(1956)的著名信中指出了该领域最著名的开放问题“P=NP?” 尽管这些先驱者在该奖项设立数年后就去世了，但中间还有12年的时间。

同样，祖斯(1910-1995)也从未获得过图灵奖，尽管他在1935-1941年间创造了世界上第一台可编程通用计算机。并且他在1936年的专利申请描述了可编程物理硬件所需的数字电路，这比香农在1937年关于数字电路设计的论文要早。

祖斯也在20世纪40年代早期创造了第一种高级程序设计语言，以及在1941年发明的Z3电脑。Z3不像哥德尔(1931)、丘奇(1935)、图灵(1936)和波斯特(1936)那样，只是一种理论上不切实际的纸笔结构，忽略任何物理计算机不可避免的存储限制。它的物理硬件在上述理论的现代意义上确实是通用的——简单的算术技巧可以弥补它缺乏一个显式条件跳转指令的类型 “IF…然后转到地址…

顺便说一下，图灵的编程或波斯特的机器更尴尬，它们也不允许“现代的”条件跳转——它们甚至没有指令指针可以跳转到的编号内存地址。

Z3 在计算硬件的历史中处于什么位置?

已知的第一个基于齿轮的计算装置是2000多年前古希腊的天球仪(一种天文钟)。1500年后，彼得·亨莱因仍在制造概念上类似的机器——尽管更小——也就是第一个小型化怀表(1505年)。但这些设备总是计算相同的东西，例如，用分钟除以60得到小时。

17世纪出现了更灵活的机器，可以根据输入数据计算答案。1623年，威廉·希卡德(Wilhelm Schickard)建造了第一台基于数据处理齿轮的简单算术专用计算器，他是“自动计算之父”的候选人之一，紧随其后的是Blaise Pascal（1642年）的高级Pascaline。

在1673年，上述不可避免的莱布尼茨设计了第一台能执行所有四种算术运算的机器(步数计算器)，而且第一台有内存的机器。他还在1679年描述了二进制计算机的原理，几乎是所有现代计算机的原理，包括Zuse的Z3。

Z3采用电磁继电器，开关明显移动。第一个电子专用计算器（其运动部件是太小而看不见的电子）是由John Atanasoff(“基于电子管的计算之父”)发明的二进制ABC(美国，1942年)。与17世纪以齿轮为基础的机器不同，ABC使用的是电子管——今天的机器使用的是晶体管原理，由Julius E. Lilienfeld在1925年获得专利。但是不像Z3, ABC不是自由编程的。汤米·弗劳尔斯(Tommy Flowers，英国，1943-45年)发明的用来破解纳粹密码的电子巨像机(NASC6)也不是。

另一方面，程序的概念当时已经众所周知。也许世界上第一台可编程机器是亚历山大的赫伦(显然他也有第一个已知的蒸汽机- Aeolipile) 在1世纪制造的自动剧院。他的可编程机器人的能量来源是一个下落的重物，拉着一根缠绕在旋转圆筒销上的绳子。控制门和木偶几分钟的复杂指令序列由复杂的包装编码。

巴格达的巴努·穆萨兄弟(Banu Musa brothers)于9世纪发明的自动音乐装置(music automaton)使用旋转圆筒上的大头针来存储控制蒸汽驱动笛子的程序（与Al-Jazari公司的可编程鼓机1206相比）。

大约1800年，约瑟夫-玛丽·雅卡尔等人在法国制造了第一台商用程序控制机器(穿孔卡片织机)，他们也许是世界上第一个工业软件的“现代”程序员。

在这种情况下，似乎有必要指出程序和上面提到的17世纪用户提供的有限输入数据之间的区别。程序是存储在某些介质(如穿孔卡片上)上的指令序列，可以在不需要人工干预的情况下反复运行。随着时间的推移，存储程序所需的物理对象变得越来越轻。古老的机器将它们储存在旋转的圆筒上; 提花机把它们放在纸板上; 祖斯将它们储存在35毫米胶片上，而今天我们通常使用电子和可磁化材料来储存它们。

雅卡尔的程序(1800年左右)还不是通用型的，但它们启发了Ada Lovelace和她的导师Charles Babbage (英国，大约1840年)。他计划制造一种可编程的通用计算机，但未能成功(只有他的非通用专用计算器制造出了一个20世纪的复制品)。

与Babbage不同，祖斯(1936-1941)使用了莱布尼茨的二进制计算原理(1679)替代传统的十进制计算。这大大简化了硬件。除了祖斯之外，其他人制造的第一台通用可编程机器是霍华德·艾肯(Howard Aiken)的，并仍然是十进制的MARK I(美国，1944年)。

Eckert和Mauchly(1945/1946)设计的更快的十进制ENIAC可以通过重新布线来编程。然而今天，大多数计算机都是像Z3那样的二进制。

“"Manchester baby”(Williams, Kilburn & Tootill, 英国, 1948)和1948年升级的ENIAC都将数据和程序存储在电子存储器中，ENIAC通过将数字指令代码输入只读存储器进行了重新编程。然而，早在1936-38年，祖斯就可能是第一个建议将程序指令和数据都放入内存的人。有人指出，除了图灵自己的ACE设计，20世纪40年代制造的计算机都没有受到图灵1936年理论论文的任何影响。

我们再次注意到，哥德尔1931 – 1934的形式模型将数据（例如公理）和程序（对数据的操作序列）以及结果（例如定理）编码/存储在相同的基于整数的存储（现在称为哥德尔编号）中，就像图灵和波斯特后来将它们存储在位字符串中一样任何图灵机、波斯特机或任何其他数字计算机都可以用哥德尔最初的通用模型形式化（这启发了我的自我参照哥德尔机）。

然而，应该注意的是，我们在这里使用了现代术语：哥德尔（1931年）、丘奇（1935年）和图灵（1936年）都没有在他们的论文中提到"程序"这个术语（尽管祖斯1936年的专利申请经常提到"Rechenplan"，意思是"程序"）。术语“存储程序”后来首次出现在电子存储的语境中。

图灵发表了生物信息学方面的开创性工作。然而，他最大的影响可能来自于他对破译德国军队在第二次世界大战期间使用的Enigma密码的贡献。他与 Gordon Welchman在英国Bletchley公园共事。然而，著名的密码破译巨像机是由 Tommy Flowers设计的。英国密码学家建立在波兰数学家Marian Rejewski、Jerzy Rozycki和Henryk Zygalski的基础之上，他们是第一个破解Enigma密码的人，他们在电影《模仿游戏》中甚至都没有被提及。有人说这是打败第三帝国的决定性因素。

6结语

总之，许多人对计算的理论和实践做出了贡献。他1936年的著名论文多次引用了哥德尔(1931)和丘奇(1935)的开创性工作，尽管图灵站在巨人的肩膀上，但他的贡献是巨大的。作为一名伟大的科学家，他似乎不太可能会赞同那些对他夸大其词的说法，错的不是他，那应该是谁呢。

资料来源：