图灵的秘密

作者简介

图灵机是英国数学家阿兰•图灵提出的一种抽象计算模型，本书深入剖析了图灵这篇描述图灵机和可计算性的原始论文《论可计算数及其在判定性问题上的应用》。书中在详解论文的同时，也附带了大量的历史背景资料、图灵的个人经历，以及图灵机对于人们理解计算机、人类意识和宇宙所产生的影响。 本书适合所有计算机科学专业的学生、程序员或其他技术人员，同时也适合欲了解图灵生平及其构建图灵机的思维的读者阅读。

书籍目录

目 　 　录

第一部分 　基 　 　础

第1章 　这个墓穴埋葬着丢番图　　2

第2章 　无理数和超越数　　10

第3章 　几个世纪以来的发展　　28

第二部分 　可计算数

第4章 　图灵的学业　　48

第5章 　运作的机器　　69

第6章 　加与乘　　86

第7章 　子程序　　97

第8章 　万物皆数字　　114

第9章 　通用机　　130

第10章 　计算机与可计算性　　150

第11章 　机器与人　　175

第三部分 　判定性问题

第12章 　逻辑与可计算性　　188

第13章 　可计算函数　　216

第14章 　主要证明　　244

第15章 　λ演算　　266

第16章 　对连续统的设想　　285

第四部分 　题外话

第17章 　万物皆是图灵机？　　310

第18章 　长眠的丢番图　　333

参考文献　　341

编辑推荐

佩措尔德编著的《图灵的秘密》涉及数学中几个大的研究领域，包括可计算性和数理逻辑。《图灵的秘密：他的生平、思想及论文解读》仅把与理解图灵论文最相关的那些主题和概念挑出来加以解释，省去了很多细节，因此《图灵的秘密：他的生平、思想及论文解读》从深度和严格性上都无法取代那些可计算性和逻辑方面的专业书籍。想深入研究这些领域的读者可以查阅参考文献。

前言

引　　言研究过计算机的历史、技术或理论的人，都会接触到“图灵机”这个概念。在1936年，为帮助解决数理逻辑中的一个问题，英国数学家阿兰·图灵（1912—1954）提出了图灵机。它是一种纯属虚构的计算机，连计算机假设也算不上。而由此得到的意外收获是，图灵创立了一个新的研究领域——计算理论（或可计算性），它主要研究数字计算机的功能和局限性。尽管图灵机是一种并不太合理的计算机，但由于其自身极其简单而大放异彩。最基本的图灵机只能进行一些简单的操作。如果连这些操作都不能做，那么这台机器干脆什么都别做了。然而，只要将这些简单的操作组合起来，图灵机就能够进行现代数字计算机可以执行的任何计算。拨开云雾见天日，通过考查计算机的原始基础，我们就能够更好地理解数字计算机的能力和局限性，这二者同样重要。尽管有人早就论证过计算机可以做什么，但在这种论证出现多年之前，图灵就证明了计算机永远都做不到的事。图灵机仍然是被阐述和探讨的热门话题，你可以试试用喜爱的网络搜索引擎搜索“图灵机”。然而，我猜很少有人会阅读阿兰·图灵描述他这项创造的原始论文。或许，这与论文的标题“On Computable Numbers， with an Application to the Entscheidungsproblem”（“论可计算数及其在判定性问题上的应用”）有关。即使你会读最后那个单词（试试看，将重音放在第二个音节上，把这个音节发成类似“shy”的音，这就差不多了），并且知道它的意思（即判定性问题），你可能也会担心，图灵一定指望他的读者对繁冗的德国数学问题有基本的了解。快速浏览这篇论文（其中还用到了德国哥特式字体来表示机器状态）也无法让人消除这种担心。今天的读者还能手捧70年前伦敦数学学会集刊中的文章，并坚持看到有所收获，甚至十分满意吗？这本书要讲的正是这篇论文。它包含了图灵原版36页的论文 “On Computable Numbers， with an Application to the Entscheidungsproblem”和增补的3页修订 ，并辅以背景材料和大量注解。阅读图灵的原版论文就是在探索他构建图灵机的思维过程，就像在他充满想象、内容丰富的思想中进行一次奇特的旅行。图灵机不仅对计算产生了深远的影响，还深深影响了我们对数学局限性、人类思维方式，甚至宇宙本质的理解。（当然，图灵的论文中并没有出现“图灵机”这个术语，他称之为“计算机器”。不过，早在1937年 人们就开始使用“图灵机”这种说法，并且至今仍是标准术语。）我在对图灵论文进行注释的过程中，发现用解释和阐述频繁打断他的叙述还是很有用的。我努力做到（但并没有完全做到）不打断他的某一整句话。大部分情况下，我会在讨论中保留图灵自己的术语和符号，不过有时，虽然图灵没有采用某个术语，如果我觉得这个术语在解释其工作时很有用，也会引入这些术语。图灵论文的内容会像下面这样表示。为了避免混淆，我们会更多地提及可计算序列，而非可计算数。我们（指出版商和我）努力保留图灵原始论文的字体和版式， 除非有一些奇怪的表示方法（比如冒号前加空格）在现代文字处理软件中总报错。原稿中所有的行间距也得以保留。图灵的论文中存在一些印刷错误、技术性错误和理论上的疏漏，尽管我没有在原文中加以修正，但会在评注中一一指出。图灵对他自己论文内容的引用，仍沿用原发表期刊中的页码，我没有修改这些引用，不过在评注中指出了被引用部分在本书中的页码。偶尔，你会在图灵的论文中发现一个括起来的数字，例如：如果用数字代替这些字母，如在§5中，那么我们可以得到这个完全格局的数字表示，也可以称作它的描述数。这是原论文的分页处以及标注的页码。我这本书的脚注采用的是圆圈编号，而图灵论文的脚注使用符号标注，并写在阴影部分。如果只保留本书阴影部分的英文内容，再组合起来，得到的就是完整的图灵论文，而我这个劳而无功的作者只能欲哭无泪了。更有趣的阅读方式是，先读本书，再读没有被我打断的图灵论文。图灵的论文分散在本书的第4~15章，其修订内容在第16章。他的论文分为11个部分和一个附录，对应到本书的页码是：1. 计算机器　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　582. 定义　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　633. 计算机器示例　　　　　　　　　　　　　　　　　　　　　　　　　　　 694. 缩略表　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　995. 可计算序列的枚举　　　　　　　　　　　　　　　　　　　　　　　1186. 通用计算机器　　　　　　　　　　　　　　　　　　　　　　　　　　　 1307. 通用机的详细描述　　　　　　　　　　　　　　　　　　　　　　　1368. 对角线法的应用　　　　　　　　　　　　　　　　　　　　　　　1589. 可计算数的范畴　　　　　　　　　　　　　　　　　　　　　　　　17510. 大量可计算数的示例　　　　　　　　　　　　　　　　　　　　21911. 在判定性问题中的应用　　　　　　　　　　　　　　　　　　　　　244附录　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　274图灵写这篇论文的最初动机是想解决德国数学家大卫·希尔伯特（1862—1943）构想的一个问题。希尔伯特想寻找一种通用的方法来判定数理逻辑中的任意命题是否可证。寻找这种“通用的方法”被称为判定性问题。尽管判定性问题确实是图灵写这篇论文的动机，但是这篇长篇大论本身讲的却是可计算数。在图灵的定义中，可计算数就是可以使用机器计算的数。论文前面60%的内容都是图灵对可计算数的探索，就算完全不了解希尔伯特在数理逻辑或判定性问题方面的研究，也能够阅读并理解这些内容。了解可计算数与“实数”的区别对于理解图灵的观点很重要。因此，本书利用前几章介绍了数字分类的背景知识，数字包括整数、有理数、无理数、代数数和超越数，它们都可归为实数。我尽可能不涉及比高中数学更复杂的知识。我知道，有些读者离开快乐的高中生活已经几十年了，我要努力唤醒这些记忆。如果由于我本着这种教育热情而做出一些冒犯读者的解释，我表示歉意。尽管我觉得本书的读者大多会是计算机科学专业的学生、程序员或其他技术人员，但是我还是尽量让非程序员的读者也愿意读，因此我定义了一些便于理解的术语。图灵的论文被誉为“20世纪的一座知识地标” ，我希望本书可以让更多的读者领略到这篇论文的风采。为了满足不同读者的需要，本书分成了四个部分。第一部分“基础”介绍阅读图灵论文所必须掌握的一些历史和数学背景知识。第二部分“可计算数”包含了图灵论文的大部分内容，也是关心图灵机和可计算性相关问题的读者最感兴趣的部分。第三部分“判定性问题”先简要介绍了数理逻辑的背景知识，然后讨论图灵论文的剩余部分。第四部分“题外话”讨论了图灵机为何成为人们理解计算机、人类意识和宇宙本身的必要工具。第三部分的数学内容肯定是比前几章的难，并且讲得比较快。对图灵论文在数理逻辑方面的影响不感兴趣的读者甚至可以跳过第三部分，直接阅读第四部分。本书涉及数学中几个大的研究领域，包括可计算性和数理逻辑。我仅仅把与理解图灵论文最相关的那些主题和概念挑出来加以解释，省去了很多细节，因此本书从深度和严格性上都无法取代那些可计算性和逻辑方面的专业书籍。想深入研究这些领域的读者可以查阅参考文献。阿兰·图灵一生发表过近30篇论文和文章 ，却从未写过书。其中的两篇论文造就了他流芳百世的声望。“On Computable Numbers”（“论可计算数”）当然是第一篇。第二篇名为“Computing Machinery and Intelligence”（“计算机器和智能”，发表于1950年），这一篇的技术性不是很强，图灵在文中首次提出了一种判断人工智能的标准，在今天被称为“图灵测试”。总的来说，一台机器如果可以骗得我们相信它是一个人，那么就可以说它是智能的。图灵机和图灵测试是阿兰·图灵声名不朽的两大基石。初看上去，它们像是两个完全不同的概念，但事实并非如此。图灵机是以一种非常机械的方式展现人类如何进行数学运算的，图灵测试则是对计算机能力的人为评估。在整个数学研究期间，图灵都在探索人类思维和计算机器之间的关系，他所采用的研究方法至今仍很吸引人。很多关于可计算性的教科书只讨论图灵的研究而不涉及图灵这个人，它们可没有劳神讲述有关个人传记的细节。不过，本书不会这么做。图灵在二战期间所做的密码分析方面的秘密工作，他参与的影响力巨大的计算机工程，他对于人工智能的思索，他的性取向，他由于“严重猥亵”罪而被逮捕和起诉的经历，以及他在41岁时自杀身亡，所有这些事情都需要关注。得益于英国数学家安德鲁·霍奇斯（1949—　）撰写的精彩传记Alan Turing： The Enigma（《艾伦·图灵传：如谜的解谜者》，Simon & Schuster，1983年出版），我没费多大力气就总结出了图灵一生中的重要事件。霍奇斯对图灵感兴趣的部分原因，在于他参与了20世纪70年代的同性恋解放运动。霍奇斯的传记还给休·怀特摩尔的剧本Breaking the Code（《破解密码》，1986）带来了灵感，在舞台上和在1996年改编的电视片中，阿兰·图灵的角色都是由德里克·雅克比扮演的。如同早期的英国数学家、计算机先驱查尔斯·巴贝奇（1791—1871）和艾达·拉夫拉斯（1815—1852），图灵也成为计算机时代的一个标志。美国计算机协会每年都会为在计算机行业做出杰出贡献的人颁发图灵奖，奖金为10万美元。现在还有一些用来组装图灵机的工具，比如“图灵编程语言”（从Pascal衍生而来）和“图灵的世界”软件。图灵的名字几乎成为计算机编程的通用代名词。杜特尼把他的“计算机科学探索”一书命名为The Turing Omnibus（《图灵选集》，计算机科学出版社，1989）。戴维德·波尔特把他编写的一本关于“计算机时代的西方文化”的书命名为Turing’s Man（《图灵时代的人类》，北卡罗来纳州大学出版社，1984）。布莱恩·罗特曼对传统数学极限概念的评论文章Ad Infinitum（斯坦福大学出版社，1993）被幽默地加上了副标题The Ghost in Turing’s Machine（《图灵机里的幽灵》）。数学和计算机科学领域以外的学者也对阿兰·图灵感兴趣。研究文集Novel Gazing： Queer Readings in Fiction（《凝神注视：论小说的另类解读》）中最有特色的一篇文章就是由泰勒·科坦撰写的The“Sinister Fruitiness”of Machines： Neuromancer， Internet Sexuality， and the Turing Test（《智能机器带来的“阴暗苦果”：神经漫游者、网络性爱和图灵测试》）。科坦博士所说的Neuromancer指的是威廉·吉布森著名的“赛博朋克”小说Neuromancer（《神经漫游者》）。在这部科幻小说里，有一个叫做图灵警察局的组织，他们负责确保人工智能体不会试图增强它们自身的智能。图灵还出现在很多小说的书名中。马文·明斯基（麻省理工学院人工智能方向著名的研究者）与科幻小说家哈里·哈里森合写了The Turing Option（《图灵选择》，华纳图书公司，1992）。伯克利计算机科学教授克里斯托斯·帕帕迪米特里欧参与创作了Turing（《图灵》，一部关于计算的小说，麻省理工学院出版社，2003）。玻利维亚小说家埃德蒙多·苏丹写了一本名为Turing’s Delirium（《图灵的狂热》，英文版由丽莎·卡特翻译，霍顿·米夫林出版公司，2006）的小说，在其中，一个外号叫图灵的密码专家发现了用他的技能为腐败政府服务带来的危险。在珍娜·列文的小说A Madman Dreams of Turing Machines（《图灵机狂人梦》，Knopf出版社，2006）中，阿兰·图灵和库尔特·哥德尔的生活被虚构在了一起，他们穿越时空，产生了奇特的交织。阿兰·图灵这个角色还出现在其他很多小说中，如尼尔·斯蒂芬森的Cryptonomicon（《编码宝典》，Avon，1999），罗伯特·哈里斯的Enigma（《密码迷情》，Hutchinson，1995），约翰·卡斯蒂的The Cambridge Quintet： A Work of Scientific Speculation（《剑桥五重奏：一部科学思考的著作》，Perseus图书公司，1998），以及道格拉斯·侯世达的G·del， Escher， Bach （Basic图书公司，1979）。阿兰·图灵甚至为The Turing Test（《图灵测试》，BBC，2000）的一部分做了解说，这本书是保罗·伦纳德写的Doctor Who系列小说中的一本。人们以各种方式来表达对阿兰·图灵的尊敬当然是好事，不过这样一来，图灵的实际研究可能会被遗忘。我希望，就算那些正式研究过计算理论，并认为自己完全了解图灵机的人，也能在面对这个真正由大师自己构建的图灵机时发现不少令人惊奇的事物。*　*　*我在1999年就开始构思这本书，当时只写了一点，然后在接下来的五年里时不时又写上一些。2004～2005年基本完成了前11章。后面7章是在2007～2008年完成的，在此期间的写作几乎未中断，唯一的中断就是与我一生中最好的朋友，也是我的至爱迪尔德丽·辛诺特结婚（终于结婚啦）！非常感谢伦敦数学协会许可完整地再版阿兰·图灵的论文“On Computable Numbers， with an Application to the Entscheidungsproblem”。沃尔特·威廉姆斯和拉里·史密斯审阅了本书的初稿，发现了一些错误，并且提出了一些很有益的改进建议。非常感谢Wiley出版公司的同仁，正是他们的工作将我所钟爱的想法真正出版成书。克里斯· 韦伯负责督促这本书的出版，策划编辑克里斯多夫· 里韦拉和制作编辑安吉拉·史密斯克服了很多版式和印刷方面的困难，技术编辑彼得·伯凡蒂帮助我认真完成了技术相关的内容。Wiley出版公司的很多幕后工作人员也都努力把这本书做得至臻至善。所有未被发现而遗留在书中的缺陷、瑕疵或隐藏的错误，都只能归咎于作者。每位作者都是站在前人肩上的。选出的参考书目只列出了我所参考的众多书籍中的一小部分。我还要感谢纽约公共图书馆，特别是科学、工业和商业图书馆的工作人员。为参考原始论文，我多次使用JSTOR，同时我发现维基百科、谷歌书籍搜索和Wolfram MathWorld也都很有用。*　*　*登录网站可以找到与本书相关的信息和资源。查里斯·佩措尔德纽约州纽约市和罗斯科2008年5月

内容概要

　　Charles Petzold
　Windows编程大师、世界顶级技术作家、微软资深MVP，拥有25年的Windows编程经验。1994年5月，Petzold作为唯一的作家，获得由微软公司和Window
Magazine授予的Windows 先锋奖（仅7人获奖），直到今天，他依然是Windows GDI
程序设计首席技术作家。他出版过十几本著作，其中包括Win32 API编程经典《Windows程序设计》、《编码》等。
 　历届图灵奖得主名单
 　◎ 1966 A. J. Perlis
 　高级编程技术和编译器架构
 　◎ 1967 Maurice V. Wilkes
 　设计出第一台具有内置存储程序的计算机EDSAC
 　◎ 1968 Richard W. Hamming
 　数值方法、自动编码系统、错误检测及错误校验码
 　◎ 1969 Marvin Minsky
 　创造、推进和提升人工智能
 　◎ 1970 J. H. Wilkinson
 　利用数值分析方法来促进高速数字计算机的应用
 　◎ 1971 John McCarthy
 　人工智能
 　◎ 1972 Edsger W. Dijkstra
 　编程语言
 　◎ 1973 Charles W. Bachman
 　数据库
 　◎ 1974 Donald E. Knuth
 　算法分析和程序设计语言，“计算机程序设计艺术”丛书
 　◎ 1975 Allen Newell和Herbert A. Simon
 　人工智能、人类认知心理学和表处理
 　◎ 1976 Michael O. Rabin和Dana S. Scott
 　非确定性机器
 　◎ 1977 John Backus
 　可用的高级编程系统设计
 　◎ 1978 Robert W. Floyd
 　软件编程的算法，语法分析理论、编程语言的语义和算法分析等多项计算机子学科的创立
 　◎ 1979 Kenneth E. Iverson
 　程序设计语言理论、交互系统及APL
 　◎ 1980 C. Antony R. Hoare
 　编程语言的定义和设计
 　◎ 1981 Edgar F. Codd
 　数据库管理系统的理论和实践
 　◎ 1982 Stephen A. Cook
 　奠定了NP完全性理论的基础
 　◎ 1983 Dennis M. Ritchie和Kenneth L. Thompson
 　一般操作系统理论，对UNIX操作系统的推广
 　◎ 1984 Niklaus E.Wirth
 　开发了EULER、ALGOL-W、MODULA和PASCAL等一系列崭新的计算机语言
 　◎ 1985 Richard M. Karp
 　算法理论
 　◎ 1986 John E. Hopcroft和Robert E. Tarjan
 　在算法及数据结构的设计和分析中取得了决定性成果
 　◎ 1987 John Cocke
 　编译器的理论和设计，大系统体系结构，精简指令集计算机的开发
 　◎ 1988 Ivan E. Sutherland
 　计算机图形学
 　◎ 1989 William V. Kahan
 　数值分析
 　◎ 1990 Fernando J. Corbato
 　组织通用、大规模、分时和资源共享的兼容分时系统和Multics的开发
 　◎ 1991 Robin W.Milner
 　可计算函数逻辑（LCF）、ML和并行理论（CCS）
 　◎ 1992 Butler Lampson
 　分布式个人计算机系统
 　◎ 1993 Jurlis Hartmanis和Richard E. Stearns
 　奠定了计算复杂性理论的基础
 　◎ 1994 Raj Reddy和Edward Feigenbaum
 　对大型人工智能系统的开拓性研究
 　◎ 1995 Manuel Blum
 　奠定了计算复杂性理论的基础，密码术及程序校验
 　◎ 1996 Amir Pnueli
 　在计算中引入时序逻辑、程序及系统检验
 　◎ 1997 Douglas Engelbart
 　提出交互计算概念并创造出实现这一概念的重要技术
 　◎ 1998 James Gray
 　数据库和事务处理
 　◎ 1999 Frederick P. Brooks, Jr.
 　计算机体系结构、操作系统、软件工程
 　◎ 2000 姚期智（Andrew Chi-Chih Yao）
 　计算理论方面的基础性工作
 　◎ 2001 Ole-Johan Dahl和Kristen Nygaard
 　面向对象程序设计思想
 　◎ 2002 Ronald L. Rivest、Adi Shamir和Leonard M.
Adelman
 　公共密钥算法（RSA）
 　◎ 2003 Alan Kay
 　发明第一个完全面向对象的动态计算机程序设计语言Smalltalk
 　◎ 2004 Vinton G. Cerf和Robert E. Kahn
 　在互联网方面的开创性工作
 　◎ 2005 Peter Naur
 　Algol 60语言
 　◎ 2006 Frances E. Allen
 　编译器优化理论和实践（她是图灵奖第一位女性得主）
 　◎ 2007 Edmund M. Clarke、Allen Emerson和Joseph
Sifakis
 　将模型校验推广成软硬件工业中广泛采用的高效校验技术
 　◎ 2008 Barbara Liskov
 　编程语言和系统设计的实践与理论基础
 　◎ 2009 Charles P. Thacker
 　第一台现代个人计算机Alto之父
 　◎ 2010 Leslie L.Valiant
 　人工智能、自然语言处理和手写识别等大量革新技术
 　◎ 2011 Judea Pearl
 　通过或然性积分和随机推理对人工智能做出贡献

章节摘录

版权页：   插图：   一种可行的方法是，依次计算每一项的第一位，直到某一项的第一位数字为0，然后，再依次计算每一项的第二位，直到某一项的前两位数字均为0，依此类推。这显然是一个很复杂的过程，特别是你不想机器在计算得到结果后再擦除结果的任意位时。 执行正弦函数只是一个问题，输入从哪里来呢？ 或许我们的直觉是让机器的使用者以某种方式“键入”机器需要计算的角。这显然是受现在的交互式计算机和屏幕计算器的启发，但是为了接受这种形式的输入，需要重新设计图灵机。这比目前我们所做的工作量更大。第二种观点是将函数的输入“硬编码”在机器内部。例如，我们可以设计一台专门计算37.85°的正弦值的机器。尽管这样会把机器限制为只能求解某一个角度的正弦值，但是我们还是希望设计出的这种机器易于修改，从而可以计算其他角度的正弦值。 第三种方法是把角度编码到纸带上。机器读取这个输入，计算正弦值，然后再把结果打印到纸带上。（我猜你喜欢这么做！我也是。） 第四种方法是让机器自己产生输入。例如，机器首先计算角度为0°的正弦值，然后计算角度为1°的正弦值，再计算角度为2°的正弦值，等等，并把每个结果都打印在纸带上，最后会得到一张包含很多角度正弦值的“表”。这种方法要求机器计算得到的每个结果都只包含有限个数位。 第五种方法需要两台不同的机器。第一台机器计算实数，第二台计算该数的正弦值。我说两台机器的时候，实际上是指可以实现两台机器逻辑的一台机器。我们已经遇到过以这种方式结合的机器。在第8节中（本书第166～167页），图灵把一台判定机器D和通用机u结合起来，构造成机器H来分析标准描述。这种做法的好处是，我们可以“插入”不同的第一台机器来计算不同角度的正弦值。 这些做法都是有问题的。一个大问题是正弦函数的输入和输出都是实数（至少理论上是这样的），而实数包含无限位。键入一个有无限位的数或将这样的数编码在纸带上都是不可能的。 事实上，即使你将角度限制在简单的、可以表示成有限的十进制数的范围内，正弦函数需要的也是弧度制的角度。180°对应π个弧度，因此看上去很简单的10°其实是π／18个弧度——个包含无限个十进制位数的超越数。

---

 图灵的秘密下载 精选章节试读 更多精彩书评

---