图灵诞辰百年至今，伟大思想的光芒恒久闪耀。本书云集20位不同方向的顶尖科学家，共同探讨图灵计算思想的滥觞，特别是其对未来的重要影响。这些内容不仅涵盖我们熟知的计算机科学和人工智能领域，还涉及理论生物学等并非广为人知的图灵研究领域，最终形成各具学术锋芒的15章。如果你想追上甚至超越这位谜一般的天才，欢迎阅读本书，重温历史，开启未来。

无

这本书源于数理逻辑学家巴里·库珀的提议。在2007年时，他已经在筹划一个会议，纪念阿兰·图灵诞辰一百周年，不过，对于复兴图灵研究而言，这仅仅是他巨大的、充满激情的奉献的开端。2009年，在编辑图灵的一部新的极为重要的论文专辑时，他（和我一起）向剑桥大学出版社提出了一个想法，出版一本关于“图灵与计算之未来”的书。在与出版社的大卫·特纳拉赫和塞维亚·芭比娜接触以后，巴里和我感觉这是个机会，让当今顶尖的科学家们把图灵遗产中动人且有挑战性的部分带给广大读者。
2010年，我们确定了书名The Once and Future Turing，并且开始约稿。这项计划依靠的是巴里·库珀担任欧洲可计算性学会主席以及参与数不胜数的学术会议组织委员会所凝聚的网络力量。更为重要的是，计划中饱含他充满智慧的探索，呈现了逻辑与现代物理以及人类科学之间的相互影响。巴里对于“Computing the World”有着独到的见解，他将其作为副书名，并在书中五个部分的开篇对其做了进一步阐释，这些都是他对本书的贡献。我的贡献（包括全书开篇的引言）主要围绕图灵之曾经（Turing Once），巴里则书写了图灵之未来（Turing Future）。
非常不幸，在本书准备工作的最后阶段，巴里突然去世了。特别令人难过的是，他没能看到本书的出版。巴里诚挚地感谢剑桥大学出版社的每个参与者，我也是一样。同时，感谢撰写各章的杰出作者们，他们慷慨地工作并且永远充满耐心。这些章节从各个方面反射出时间与人类生命的奇迹，展现了一幅未来之景，如果图灵和巴里·库珀还活着，这一定是他们希望看到的。
安德鲁·霍奇斯
2016年1月

计算机\计算理论

【内封署名】堵丁柱 高晓沨 徐秋亮 李廉 徐雯 吕再新 孙晓明 蔡志鹏 译

图灵（1912—1954），19岁进入剑桥大学，26岁在普林斯顿大学获得博士学位。二战中，他帮助盟军成功破解了著名的密码系统Enigma，挽救了千万人的生命。1952年因同性恋而获罪，两年后食毒苹果自杀。2013年，英国女王伊丽莎白二世宣告特赦图灵。
今天，世人知晓图灵，因为他是“计算机科学之父”和“人工智能之父”，但我们理解那些遥遥领先于时代的天才思想到底意味着什么吗？拾起本书，你将跟随20位当代科学巨擘一起解开这些密码。

精彩导读
·罗宾·甘地是图灵唯一的学生，他们是站在数学金字塔尖的一对师徒。然而在功成名就前，甘地受图灵的影响之深几乎被人遗忘，特别是关于逻辑学和类型论。翻开第2章，重新发现一段科学与传承的历史。
·写就奇书《哥德尔、艾舍尔、巴赫——集异璧之大成》的侯世达，继续着高超的思维博弈。当迟钝呆板的人类遇见顶级机器翻译家，“模仿游戏”究竟是头脑的骗局还是真正的智能？翻开第8章，进入一场十四行诗的文字交锋。
·万物皆计算，生命的算法尤其令人着迷。在计算技术起步之初，图灵就富有预见性地展开了关于生物理论的研究，他提出的“逆向工程”仍然挑战着当代的研究者。翻开第10章，一窥图灵是如何计算生命的。
·量子力学、时间箭头、奇点主义、自由意志、不可克隆定理、奈特不确定性、玻尔兹曼大脑……这些统统融于最神秘的一章中，延续着图灵未竟的思考。翻开第12章，准备好捕捉量子图灵机中的幽灵。
·罗杰·彭罗斯，他的《皇帝新脑》，他的宇宙法则，他的神奇阶梯，他与霍金的时空大辩论，他屡屡拷问现代科学的语出惊人……翻开第15章，看他如何回应图灵，尝试为人类的数学思维建模。

本书的译者大多数首次承担翻译工作。翻译与阅读不太一样。阅读只要意会，而翻译需要加上言谈。既然是首次，自然有一定的困难。可是，为什么大家愿意承担这项工作呢？最重要的原因在于，这是本吸引人的好书。它的吸引人之处并非图灵的传奇故事，而是涉及计算机技术未来的丰富思想。毫无疑问，这本书是为纪念伟大的计算机先驱图灵而编写的，它遍数了图灵曾经产生过的各种各样的天才想法。同时，书中也阐述了这些思想在近代的发展，并且更重要的是，展望了这些科学思想的未来前景。
图灵不愧是个天才，他的思想极其丰富，琳琅满目，令人目不暇接。不仅仅涉及计算机科学与技术，而且涉及物理、生物以及为人类思维建模的奇特想法。在工作之余，阅读此书，会让人耳目一新，思路开阔。
让更多的人受益，这是我们翻译此书的心意和衷心的期望。

堵丁柱
2018年1月

译者序
前言
本书作者
本书译者
引言/
第一部分置身可计算的世界，探索普适性数学
第1章算法、方程和逻辑/
◎马丁·戴维斯
11方法概览/
12例子：完全平方数集/
13一些关系/
14猜想变成定理的故事/
15通用方程/
16素数和一个丑陋的多项式/
17逻辑/
18关于数学/
19关于朱莉娅·罗宾逊的电影/
附录：不可解性定理的证明/
参考文献/
第2章被遗忘的图灵/
◎J M E 海兰
21引言/
22唯一的学生/
23回忆/
24早年时光/
25学生与导师/
26中文翻译/
27一个想法的产生/
28远见和反思/
29图灵和类型论/
210图灵的理论倾向/
211从未完稿的论文/
212图灵的遗产/
参考文献/
第3章图灵和素数/
◎安德鲁 R布克
31素数/
32大素数/
321梅森素数/
322电子时代的梅森素数/
33素数的分布/
331黎曼ζ函数/
332图灵与黎曼猜想/
333形式化证明/
34今天与未来/
参考文献/
第4章图灵之后的密码学和计算/
◎乌力·毛勒
41引言/
42密码学/
421引言/
422密钥的需求/
423安全性证明/
43计算/
44迪菲-赫尔曼密钥协商协议/
441预备知识/
442有效的乘幂运算/
443密钥协商协议/
45群上的离散对数及其他计算问题/
46离散对数算法/
461引言/
462大步小步算法/
463波利格-赫尔曼算法/
47抽象计算模型/
471动机/
472计算模型/
473三种问题类型/
48证明安全性：复杂度下界/
481引言/
482两个引理/
483群作用和大步小步算法的最优性/
484离散对数和波利格-赫尔曼算法的最优性/
485Zn中的乘积计算和CDH问题/
486DDH问题/
487DL问题到CDH问题的一般归约/
49结论/
致谢/
参考文献/
第5章图灵与恩尼格玛统计学/
◎坎蒂V马蒂亚， S巴里·库珀
51引言/
52事例的权重与经验贝叶斯/
53字母队列/
531恩尼格玛编码描述/
532字母队列的重要性/
54GCHQ解密的两个重要的图灵报告/
55图灵的全局统计观/
551统计学和抽象层次/
552扩展信息分层/
56形态发生、统计和图灵的人工智能/
参考文献/
第二部分过程计算而非计算大脑
第6章图灵的洞察/
◎斯蒂芬·沃尔弗拉姆
参考文献/
第7章外设计算和内生计算/
◎克里斯托夫·托伊舍
71自顶向下和自底向上的设计/
72内生计算和外设计算/
73图灵的自底向上计算模式/
74从内生计算到外设计算/
75展望/
参考文献/
第8章迟钝呆板的人类遇见顶级机器翻译家/
◎侯世达
第三部分通向计算生命的逆向工程之路
第9章图灵理论之发育模式形成/
◎菲利普K梅尼，托马斯E伍利，埃蒙A加夫尼，露丝E贝克
91引言/
92发育的应用场景/
93图灵理论的扩展/
94关于图灵模型的争议/
95图灵的影响/
致谢/
参考文献/
第10章走钢丝绳：图灵形态发生学中分层不稳定性的困境/
◎理查德·高登
致谢/
参考文献/
第四部分量子计算的生物学、思维和推广
第11章回答笛卡儿：超越图灵/
◎斯图亚特·考夫曼
111引言/
112机器思维/
113思维、意识和机器思维/
1131回答笛卡儿/
1132封闭式量子系统和双缝实验/
1133开放式量子系统/
1134稳定的域/
1135非算法的、非确定性的、非随机的反图灵系统/
1136负责任的自由意志/
1137回答笛卡儿：思维如何在大脑中活动/
1138潜能和广延实体通过量子测量相联系/
1139意识是什么/
11310感受性与量子测量的关系/
11311最前端的大脑/
11312量子纠缠、萨穆利的观点和捆绑问题/
11313反图灵系统的编程/
114结论/
附言/
致谢/
参考文献/
第12章量子图灵机中的幽灵/
◎斯科特·阿伦森
121引言/
1211“自由意志”与“自由”/
1212关于本章标题的注释/
1213阅读本章所需的知识水平/
122常见问题/
1221狭窄的科学主义/
1222偷梁换柱/
1223相容论/
1224量子梦话/
1225大脑上传：谁会在乎/
1226决定论与可预测性/
1227量子力学与隐藏变量/
1228结果论证/
1229预测悖论/
12210奇点主义/
12211利贝实验/
12212心灵和道德/
123奈特不确定性和物理/
1231奈特不确定性/
1232量子力学与不可克隆定理/
1233自由比特构想/
1234放大与大脑/
1235反对假想小人/
124从内而外的自由/
1241协调问题/
1242微观事实与宏观事实/
125进一步的反对意见/
1251广告商异议/
1252天气异议/
1253沙鼠异议/
1254初始状态异议/
1255维格纳的朋友异议/
126与彭罗斯观点的比较/
127应用到玻尔兹曼大脑上/
128指代和自由比特/
129自由比特构想能被证伪吗/
1210结论/
致谢/
附录A定义“自由”/
附录B预测和柯尔莫戈洛夫复杂度/
附录C奈特量子态/
参考文献/
第五部分神谕、无限计算和心智的物理学
第13章图灵的“神谕”：从绝对可计算性到相对再返回/
◎所罗门·费弗曼
131引言/
132“绝对”有效可计算性/
1321机器和递归函数/
1322部分递归函数/
1323有效不可解问题和归约方法/
133自然数的相对有效可计算性/
1331图灵的“神谕”和图灵可归约性/
1332递归可枚举集合、不可解度和波斯特问题/
1333波斯特问题的解和度理论的繁荣/
134自然数的一致相对可计算性/
1341相对计算过程和局部递归泛函数/
1342递归论/
1343自然数上有限类型的局部递归泛函数/
135广义递归论/
1351背景与概述/
1352集合和序数上的可计算性/
1353一般结构上的可计算性/
136在真实计算中相对可计算性概念的角色/
1361计算实践和计算理论/
1362内置函数和黑盒/
1363编程函数方面/
1364抽象数据类型/
1365复杂性的度/
1366结论/
附言/
参考文献/
第14章图灵超越：超越事件视界/
◎P D 韦尔奇
141起源/
142极限可判定/
143MH时空/
144无穷序数：超越算术/
145回到MH时空/
1460心智/
147无限时间图灵机/
148寄存器机和其他推广/
149结论/
参考文献/
第15章为数学思维建模的尝试/
◎罗杰·彭罗斯
151图灵的顺序逻辑/
152数学之信任/
153数学理解所基于的物理过程/
154П语句/
155谨慎神谕/
156谨慎神谕装置的运转/
157对于谨慎神谕装置的哥德尔型定理/
158物理含义/
参考文献/
后记/