永恒的图灵

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

S. 巴里·库珀
（S. Barry Cooper）
本书付梓前不幸逝世。生前为利兹大学数理逻辑教授，欧洲“可计算性学会”主席，“图灵百年委员会”主席。他主编的Alan Turing: His Work and Impact一书曾荣获2013年美国专业与学术杰出出版奖。
安德鲁·霍奇斯
（Andrew Hodges）
牛津大学数学研究所教授、高级研究员。他撰写了畅销全球的权威图灵传记Alan Turing: The Enigma，此书也是奥斯卡获奖影片《模仿游戏》的文学原本。

适读人群 ：IT领域相关专业学生，以及所有愿意了解图灵思想和理解计算机科学和智能技术的读者。
图灵是当代计算科学巨擘，开创了计算机科学和人工智能的基本理论，被称为“计算机科学之父”和“人工智能之父”。
本书是为纪念图灵百年诞辰，由20位不同领域的科学家联袂编写，从不同侧面探讨图灵计算思想的滥觞，展望这些科学思想的未来前景。
中文版由世界著名数学家堵丁柱领衔的8位资深学者翻译，译文准确传达了原著的意义,兼顾中文的表达，完美呈现了原著的精髓，堪称中文译作的精品。
本书适合所有愿意了解图灵思想和理解计算机科学和智能技术的读者。

前言

The Once and Future Turing: Computing the World

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

目录

The Once and Future Turing: Computing the World


译者序

前言

本书作者

本书译者
引言/

第一部分置身可计算的世界，探索普适性数学
第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物理含义/

参考文献/

后记/