《群体性愚昧：为什么精英在一起也会干蠢事.html.pdf》由会员分享，可在线阅读，更多相关《群体性愚昧：为什么精英在一起也会干蠢事.html.pdf（274页珍藏版）》请在三一文库上搜索。
1、译者序 本书的译者大多数首次承担翻译工作。翻译与阅读不太一样。阅读只要意会，而翻译需要加上言谈。既然是首次，自然有一 定的困难。可是，为什么大家愿意承担这项工作呢？最重要的原因在于，这是本吸引人的好书。它的吸引人之处并非图灵的传奇 故事，而是涉及计算机技术未来的丰富思想。毫无疑问，这本书是为纪念伟大的计算机先驱图灵而编写的，它遍数了图灵曾经产 生过的各种各样的天才想法。同时，书中也阐述了这些思想在近代的发展，并且更重要的是，展望了这些科学思想的未来前景。 图灵不愧是个天才，他的思想极其丰富，琳琅满目，令人目不暇接。不仅仅涉及计算机科学与技术，而且涉及物理、生物以 及为人类思维建模的奇特想法。在
2、工作之余，阅读此书，会让人耳目一新，思路开阔。 让更多的人受益，这是我们翻译此书的心意和衷心的期望。 堵丁柱 2018年1月 前言 这本书源于数理逻辑学家巴里库珀的提议。在2007年时，他已经在筹划一个会议，纪念阿兰图灵诞辰一百周年，不过，对 于复兴图灵研究而言，这仅仅是他巨大的、充满激情的奉献的开端。2009年，在编辑图灵的一部新的极为重要的论文专辑时， 他（和我一起）向剑桥大学出版社提出了一个想法，出版一本关于“图灵与计算之未来”的书。在与出版社的大卫特纳拉赫和 塞维亚芭比娜接触以后，巴里和我感觉这是个机会，让当今顶尖的科学家们把图灵遗产中动人且有挑战性的部分带给广大读 者。 2010年，
3、我们确定了书名The Once and Future Turing，并且开始约稿。这项计划依靠的是巴里库珀担任欧洲可计算性学 会主席以及参与数不胜数的学术会议组织委员会所凝聚的网络力量。更为重要的是，计划中饱含他充满智慧的探索，呈现了逻辑 与现代物理以及人类科学之间的相互影响。巴里对于“Computing the World”有着独到的见解，他将其作为副书名，并在书 中五个部分的开篇对其做了进一步阐释，这些都是他对本书的贡献。我的贡献（包括全书开篇的引言）主要围绕图灵之曾经 （Turing Once），巴里则书写了图灵之未来（Turing Future）。 非常不幸，在本书准备工作的最后阶段，
4、巴里突然去世了。特别令人难过的是，他没能看到本书的出版。巴里诚挚地感谢剑 桥大学出版社的每个参与者，我也是一样。同时，感谢撰写各章的杰出作者们，他们慷慨地工作并且永远充满耐心。这些章节从 各个方面反射出时间与人类生命的奇迹，展现了一幅未来之景，如果图灵和巴里库珀还活着，这一定是他们希望看到的。 安德鲁霍奇斯 2016年1月 本书作者 本书译者 堵丁柱，负责引言、第15章和后记 得克萨斯大学达拉斯分校，计算机科学系，www.utdallas.edu/dxd056000/ 高晓沨，负责第13章和第13章 上海交通大学，计算机科学与工程系， 徐秋亮，负责第4章 山东大学，计算机科学与技术学院， 李廉
5、，负责第58章 合肥工业大学，现已退休 徐雯，负责第9、10章 得克萨斯女子大学，数学与计算机科学系，twu.edu/math-computer-science/faculty-and-staff/wen-xu-phd/ 吕再新，负责第11章 华盛顿州立大学，计算机科学系，directory.vancouver.wsu.edu/people/zaixin-lu 孙晓明，负责第12章 中国科学院计算技术研究所， 蔡志鹏，负责第14章 佐治亚州立大学，计算机科学系，grid.cs.gsu.edu/zcai/ 引言 阿兰图灵短暂的一生始于1912年，止于1954年。这本书的灵感来自他的百年诞辰纪念。
6、但是作为本书的发起人，巴里库珀 和我期望在讨论图灵过往的同时，在主题中加入“未来”。我们选择了一个令人兴奋的书名The Once and Future Turing，它取材于亚瑟王墓碑上的铭文。我们邀请了一些著名的科学家来简述基于图灵之发现的科学工作，分享他思想的精 髓，而且还要求给出未来的闪光点。结果即为本书中的15章，这些作者以完全不同的方式回应了我们的挑战。 图灵自己对于未来有毫不含糊的超级想象力。他在1950年的经典论文计算机器与智能中所做的预言就是一个著名的例 子。他并不总是对的，也没几个人相信他小心阐述的关于机器智能的50年预测，可是这实现了。另一方面，他低估了快速、便 宜、大规模
7、计算的潜力。他在1948年对未来计算机硬件的想象正确地指出了光速是计算速度的关键约束。但是他关于厘米规模 电子元件的假定忽视了小型化的巨大潜力。对图灵的先见之明，较为令人侧目的证明是他对于通用机器能力，以及对于今天称为 软件工业的未来的评论：“每个已知的过程都不得不编译成指令表的形式” 在1946年，图灵可以自信地说，他是英美密码战的“幕后操纵者”，并为国际关系的未来留下了自己的遗产，不过，这份 遗产还没有得到仔细评估。1939年他和高登威奇曼建功立业，说服英国当局给予从未试验过的“图灵炸弹”密码破译机技术大 量投资，结果证明，这部机器的逻辑光芒改变了战争中英国的命运。这种视野并非图灵独有。为
8、了战胜希特勒，布莱切利园好似 一跃跨入未来，他们的工作科学、有组织且社会化，仿佛60年代先于40年代到来了。但图灵对于自身的洞察力总是有着特殊的 自信。1936年他提出通用计算机器时，选择了一个非数学而有启发性的词汇“发明”：“通用计算机器。我们可以发明一种机 器，用来计算任何可计算的序列”同一年他清楚地预见了即将到来的与德国的战争，以及密码学对于这场战争的重要性。战 后，虽然他不能对实用计算机的发展保持控制，然而他的自信并未动摇。在没有任何外部支持的情况下，他依然亲自动手做计算 机实验，研究生物生长的数学理论。这样的孤独并没有影响他的热情，即使他的模型不得不等到20世纪70年代才得到认真对
9、待，而到90年代人们才需要具备那种能力的计算机。 对于图灵，剑桥应该是他最接近的理想归宿，可是他的行为从来不符合剑桥的期望。图灵完全不在意区分“纯”数学和“应 用”数学，然而这种区分支配着剑桥的全体教职员工。取而代之的是，他表现出数学预言的能力，先于而非跟随科学观察所得。 我们可称之为超级神奇（metamagical），把meta和magical连到一起造出这个新词的是本书的作者之一侯世达 （Douglas Hofstadter）。 在回到贯穿本书的话题之前，我们讲一个关于阿兰图灵生活的新故事。对于已经熟悉他的非凡故事的人，这可以算作一个 有价值的插曲。对于不熟悉的人，这段插曲会让你体会到，为
10、何在数学、科学和技术之外，他的个人生活已经成为大众痴迷的源 泉。2013年，在我们选定书名很长时间以后，牛津大学图书馆举办了一场主题为“神奇的书，从中世纪到中土”的展览。在入 口处是亚瑟王的铭文：Rex quondam，Rexque futurus（曾经与未来）。展览中作为特色的有阿兰加纳的近期工作，包括他 最著名的书猫头鹰恩仇录。这场展览与图灵的联系是如此神奇：阿兰加纳曾经是阿兰图灵的跑友，他们于19511952年在 柴郡的乡间小道上跑了上千英里。 他们相遇于1951年，在跑步时发现了彼此。那时阿兰加纳刚17岁，是曼彻斯特文法学校具有文学天赋的六年级学生。但是 一开始加纳就觉得他们相处得很平
11、等，这令他极为欣赏，因为他的学校的特殊氛围就是这样（由另外一个名叫阿兰的人通过喜剧 历史系男生所诱发的一种文化）。平等也来自相称的实力，图灵已经是位有名的业余长跑运动员，而加纳刚刚成为有竞争力 的年轻短跑运动员。平等也可以在玩笑中发现，这种玩笑现在叫作“没有废话”，充满文字游戏和粗俗的幽默。当图灵问他智能 机器是否具有可能性时，加纳并未感到新奇。在静静地跑了十几分钟后，他回答说不。图灵没有争辩。“为什么学习传统的语 言？”图灵又问。加纳回答：“你不得不学会以不同的方式使用大脑。”这种回答也许会让图灵满意。 在六到七英里的持续慢跑中，他们的谈话通常远离个人。但是有次例外，可能是在1951年年末，
12、图灵提起白雪公主的故 事。“你也是！”加纳吃惊地说。原来，这让加纳立刻回想起童年的奇异经历。那是他五岁的时候，白雪公主和七个小矮人 的故事中毒苹果的样子吓坏了他。图灵立刻产生了同感，他们共同的创伤如同加纳看到的成为维系其中的纽带。“他 习惯于重温情景中的细节，老是想着那个模糊的苹果，一边红一边绿，其中一边引向死亡。” 他们的来往发生在图灵作为同性恋受到庭审和惩罚的时期。图灵从来没说过他的遭遇，不晓得为什么，加纳直到1952年后 期才听到这些新闻，这时警察警告他，不能和图灵在一起。加纳对此以及他听说的事非常气愤，其实，他从来没有受到一丝一毫 的侵害。但是不可避免地，他和图灵的关系遗憾地结束了。阿
13、兰加纳痛苦地回忆起他在1953年最后一次见到图灵的情景，他们 刚好坐同一辆巴士从威姆斯洛去曼彻斯特，当时加纳和女朋友在一起，这使得他很难谈起任何恰当的话题，因此他装作没有注意 到图灵的存在。这件事像极了小说和电影中青春散场的一幕，不久，加纳就启程去服兵役了，在那里，他听到了图灵的死讯。阿 兰加纳始终没有披露这些经历，直到六十多年以后，它们才出现在观察家报的一个栏目上。对于图灵奇幻的一生，其中一 定有很多内容人们永远都无法知道。但是可能没有一个含有这样的情节，图灵发现了自己的苹果，那个直接预示着他1954年的 死亡的符号。 2012年我听阿兰加纳讲起这个故事，仍然仿佛发生在昨天一样，它直击我们现
14、在正在创造的蜿蜒六十多年的历史。巍峨矗 立的乔德雷尔班克射电望远镜加重了时间流逝的痕迹，它邻接一座古建筑，那是一处考古遗址，也是阿兰和格丽西达加纳安家 的地方。望远镜自身也是充满活力的曼彻斯特大学的科学前哨，并且它与计算机一样，是1945年以后由第二次世界大战之技术 转变为科学的成果之一。现在，它已经成为天文学和宇宙学的基础设施，但是在1954年，它们还是全新的。宇宙的规模和年龄 还是未知的，这些事情都将在其后的几十年里研究清楚。在那充满创造力的年代，如果图灵还活着，他可能会带来许多新发现， 然而时间定格在1954年，图灵永远停止了创造。 作为本书的作者之一，巴里库珀在与图灵相伴的时间旅行中加
15、入了副书名“Computing the World”，并且建议不限制其 触及的范围，这对于图灵完全合适，他拒绝受任何思想领域的限制。在19531954年最后的笔记中，图灵显露出他正在思考基 础物理，受到狄拉克的影响，笔记记录了他关于旋量以及重构量子力学的一些想法。某些批评者可能认为这些好像是单纯的涂 鸦，或者初始的疯狂。但是在他最后的明信片中，“创世纪光锥”这一神来之笔正确地预见到：在现代物理学中，光的几何已经 被证明是关键的思想，并且宇宙大爆炸的光锥在本书作者之一罗杰彭罗斯的工作里形成了清晰的数学思想。图灵那颇为怪诞的 格言“粒子是源”，其实参考了基本粒子和力都是对称群表示的思想：20世纪末
16、最伟大的发现之一就是，次核粒子夸克是由对 称群SU（3）描述的。 我的兴趣并非无所偏倚：我自己在数学工作中已经在发展罗杰彭罗斯的想法，用基于光锥的“磁扭线”几何取代费曼图， 形成粒子物理的中心台柱。其实，理查德费曼自身忍受着与图灵的比较，在原子弹工程中崭露头角后，20世纪40年代晚期他在 基础物理中的工作就是图灵机的相似物。费曼也写了一些有关科学的极有个性且很受欢迎的书，这些书斐然可观，用生活化的笔 触诠释了更广泛的科学文化，这是其他书很少能够企及的。费曼和图灵还有一个小小的交集。就在艾森哈特女士道出那句流传至 今的“别逗了，费曼先生”之前，她刚刚送走阿兰图灵，一位同样令人尴尬的参会者，在同样
17、令人窒息的普林斯顿研究生院茶 会上。此后，费曼开始了量子计算的早期思考，他和图灵可能已经发现了共同的战场。他们的嬉笑怒骂总是为人津津乐道，即使 是向权威说明想法时，他们也不会留意任何外交辞令。 可是，也存在明显的不同点：对于图灵，长期保持做一个诚实的人是非常不容易的。在布莱切利园的密码工作比原子弹工作 要更为隐秘。而图灵的性取向相对于费曼不仅仅是不方便，更是禁忌的，是不可言说的，是犯罪，甚至是国家安全问题。理论上 说，抗争的自由在第二次世界大战期间没有完全被忘记，而且说出自己的想法也不是完全不可能。斯堪的纳维亚半岛早期争取同 性恋权利的运动促使图灵于1952年夏天去了趟挪威（在同一年，六年级学
18、生阿兰加纳骄傲地写了篇正能量的杂文，研究古希腊 的性生活）。那些微弱的抵制活动带来了一些微小的变化。但是一直等到20世纪70年代，布莱切利园大规模密码破译工作的成 功才为人所知，这时提到它的首席科学家的性取向才是可接受的。 今天的情况截然不同，这么多科学家对本书的热情回应反映了人们对于图灵的极大兴趣，包括他的为人以及所做过的事，与 图灵相关的一切都成了人们的关注点。真难想象图灵会怎样看待自己的“复兴”或者在科学和历史中的地位。他永远无法知道， 自己到底是个默默无闻的密室人物，还是个值得公众注目的特殊个体。他1950年的论文有着强烈的私人潜台词：它的主题 是“智能机器”，同时图灵阐述它的方式是，
19、坚持“我是人类”，并且把注意力引向自己，如同精明的学术媒体今天所做的一样 生动。在“发表或毁灭”的世界里，图灵在两边做了不错的妥协。费曼的“物理讲义”非常出名，但是里面没有图灵的“逻辑与 计算机讲义”的相应部分。如果费曼放入了这部分，那么整个计算机科学这一新领域就会贴上费曼的名字。图灵1950年的论文 发表了，并且成为现代哲学的高引论文之一。而1948年的论文毁灭了（至少在1968年前），因而没人知道他的神经网络模型 （在本书中，克里斯托夫托伊舍将描述它）。 1948年的论文包含图灵在科学行进中艰苦奋斗的形象：“搜寻新技术一定要视作为全人类，而非为个人。”图灵对自己 的知识史一直保持沉默，在描
20、述计算机的本质时，要参考他1936年的论文中提出的通用机器，但是他从来不解释是如何想到通 用机器的，以及如何实现“实用通用计算机器”。官方的保密规定会是个问题（他可能永远不能解释自己是如何获得数字电子知 识的），可是他也许找到了一个方法来绕过它。图灵拒绝评论他和冯诺依曼的关系，导致后来的历史学家在阐释这一问题时遇 到了很多麻烦。对此，我们能了解到的仅仅是，1946年12月26日的田径运动会后，在晚间新闻的体育栏目报道中，图 灵“将为ACE（Automatic Computing Engine）辛勤工作的功劳记给了美国人”。1953年，第一本关于计算机的半通俗读物 比思考还快给了他展开分析的空间
21、，他给出了如下基本原则： 如果人们在数学符号的辅助下能够相当明白地用英语描述一项计算是如何完成的，那么只要存储空间够用，就总能通过编程 让数字计算机来完成那些计算。 这句话包含图灵对可计算性的定义，以及作为通用机器的计算机的概念。可是没有哪个读者有可能理解它的重要性。（现代逻辑 学家和哲学家的眼睛习惯于盯着丘奇论题表述中的微小区别，不负责任且漫不经心。图灵补充说：“这种东西不能清楚地证明， 可是对于在该领域工作的人，它就像白天一样清楚。”然而，这并没有使他的描述变得更精确。）那本书的编辑B.V.鲍登在附录 的词汇表中用一个词条总结了图灵的成就： 图灵机（Tring machine）：1936年
22、图灵博士写了一篇论文，有关计算机器的设计与极限。基于此原因，有时人们用他的名 字来称呼这种机器。其中的日耳曼元音变音是个不自然且不必要的累赘，它只是大家的猜测这么难以理解的东西一定是德 国人研究出来的。 1954年后，图灵的声誉跌入更深的死亡沉睡中，部分原因是他的癖好，使他在活着的时候自掘坟墓，还有就是环绕他的审 判和死亡的阴影。计算机科学，作为区别于数学而出现的这门工程学科，也没有爱护他。（由计算机学会设立的阿兰图灵奖是 个例外。）另外一个因素可能是，有些数学家长时间瞧不起计算，即使在20世纪70年代计算复杂性理论已经显露出数字计算的 数学深度时也是这样。今天全都变了，很大程度上这是由于通用
23、计算机在社会传播的转型中呈现出的力量。图灵的时代现在呈现 为愚昧的时代，从字面意义上讲，这是由于历史记载的缺失。在探索20世纪40年代计算机的起源时，历史学家发现自己的论断 只能基于口头传说的二手故事，而不能依据理性的探索一步步地累积素材。或许，亚瑟王传奇与曾经之图灵有更多的联系，不过 现在是时候打开大门，通向图灵之未来了。 第一部分 置身可计算的世界，探索普适性数学 在布莱切利园重建的“图灵-威尔士曼炸弹”解码机。照片经约亨菲霍夫授权 1954年，图灵在企鹅科学新闻上发表了他的最后一篇论文，这篇论文向广大读者传达了数学中可计算性的重要性。但他 并没有对自己的图灵机做出太多改进：只有一篇论文将
24、它应用于代数学中的一个可判定问题，完全未涉及新兴的计算机科学。这 在数理逻辑上留下了一个缺口，直到1958年才被马丁戴维斯在他的专著可计算性和不可解性中系统解决。目前，戴维斯对 图灵在1954年为阐释“希尔伯特第十问题”丢番图方程可解性问题所做的略微通俗的工作进行了仿真，在这项工作里图灵对 可计算性进行了非常完备的定义。1970年，马丁戴维斯对这一问题的优美解法做出了主要贡献，并且指出这项工作是如何精炼 和拓展了图灵1936年经典论文的关键部分。 最令人震惊的是马丁关于普适性和不可计算性的看法。从他与合作者的著名工作中得出的结果优雅地阐明了图灵可计算性在 经典层面上的延伸和局限。图灵后来的工作
25、预料到了现今人们对从自然过程中得到的“新计算范式”和虚拟机前景的兴趣。关于 这些计算模型能在何种程度上归属于图灵1936年的范式，有许多重要和深刻的问题被提出，并随着虚拟机的发展进入了应用层 面。普适性和延伸的概念持续不断地给今天的学者带来基本问题。 马丁海兰通过发掘阿兰图灵与罗宾甘地的紧密联系填补了历史缺失的一角。这是阿兰加纳故事的姊妹篇，是同一段 岁月中的另一段秘史。他使图灵曾经研究过但从未获得成果的议题重新焕发了生机，这便是类型论。当时人们觉得这个理论十分 抽象，现在则将其视为计算机科学（一个在图灵时代并不存在的概念）形式结构的关键，更广泛地讲，与科学理论中语言的使用 有关。 马丁的贡献
26、集中在与大多数现今科学关注点相比鲜为人知但相当基础的观点。罗宾甘地早期研究论文的标题关于理论物 理学基础理论逻辑结构的一些思考为科学与逻辑框架接下来的融合提供了清晰关联。之后发展的一个关键方面是图灵和甘地对 于丘奇类型论相互关联的兴趣。马丁指出： 图灵作为导师对甘地的影响明确和类型论有关，我在开始写这一章的时候想，图灵对这一领域的兴趣很大程度上被遗忘了。 马丁说：“是时候聊聊兴趣了。”紧接着是书中最引人入胜的讨论之一，提出了图灵与众不同的并且往往是有预见性的、以 一种相当独特的方式对抽象和具象进行的关联。在此后的一百年间未曾有人涉及此领域，更别提以这样一种权威和博文广识的方 式。 安德鲁布克通
27、过讲述图灵在1939年开始制作的特殊机器和1950年在曼彻斯特计算机上编程的故事，阐述了图灵在解析数论 中的工作，为软件如何替代特殊机器编程给出了一个非常好的示例。布克的讨论将话题引到了著名问题黎曼猜想的现代地位和图 灵计算理念长久的重要性上。 安德鲁布克对数论中图灵工作的描述强调了图灵往往对更深远的问题感兴趣。在这种情况下，他意识到计算机的出现会不 可避免地影响数学证明的本质，并对数学家们如何适应这些改变做出了有远见的猜测。图灵后来写作的一大主题是思索计算机如 何与人类创造力相辅相成，以及思维和机器之间平衡的演变。正如布克所说，这个越来越重要和复杂的关系甚至可能会导致道德 方面的影响。 有感
28、于我们对图灵战前的密码学思考和新兴的密码安全问题知之甚少，乌力毛勒讲述了另一个平行的故事。他这样来描述 这一部分： 计算和信息是计算机科学中两个最基础的概念，就像质量、能量、时间和空间是物理学中的基础概念一样。 他接下来描述了图灵计算模型和克劳德香农信息论扮演的重要和互补性作用。除了现代密码学的实际问题之外，他的讨论 还涉及另一当代尚未解决的重大问题，即P=？NP问题。乌力毛勒写道： 人们只能猜测，如果图灵在理论密码学上花费更多时间的话，他能够在这一领域取得什么样的成就。 但是图灵在1938年之后所做的工作仍然是个秘密。黛利拉的语音加密项目报告持续50年都不为人知，直到2012年全文才被发 表
29、。同样在2012年，两篇相当基础的图灵论文被公开，这两篇论文解释了贝叶斯分析的基础和它在海军恩尼格玛（Enigma）“班 部里斯马斯”（Banburismus）解码法中的应用。接下来也许还有更多值得期待。 GCHQ为纪念图灵诞辰一百周年而及时发布的新版本让我们回忆起阿兰图灵在布莱切利园做出的最具原创性和重要意义的 贡献。能够造出用来拦截德军消息的“炸弹”和“巨人”解码机的关键在于贝叶斯统计技术的应用。在第5章中，统计学家坎蒂 马蒂亚和逻辑学家巴里库珀仔细分析了发生在布莱切利园的这一段历史，并谈到了对于我们现在的“大数据”而言统计的重要 性。“恩尼格玛统计学是现在所谓的统计生物信息学的前身”，这
30、一章中写道。 通过翔实的示例、内容大纲和已发布的重要论文，马蒂亚和库珀把我们带回了类型信息的数学基础，以及为了对经典图灵计 算得到的数据进行“类型归约”而使用的抽样技术。从这种角度，他们讲述了图灵的贝叶斯技术发挥的译码作用如何使我们在更 广的语义中理解“大数据”面临的挑战。 第1章 算法、方程和逻辑 马丁戴维斯 有史以来，人们一直通过算法来和数字打交道。算法是机械地依照一系列指令实现的过程，而不需要任何创造性的思维。 20世纪30年代前人们从未觉得需要精确的数学定义或特征来说明什么是“算法”。然而，在那些年，为了尝试证明一些问题没 有算法解答时，这种需求出现了。1935年，阿兰图灵独自在剑桥大
31、学研究这个问题。同时，在普林斯顿大学，库尔特哥德尔、 阿隆佐丘奇、丘奇的学生斯蒂芬克莱尼和J.巴克利罗瑟正在研究相同的问题。从20世纪20年代起，E.L.波斯特也像图灵一样开 始独自思考这些问题。尽管他们最后得出的公式看上去有着天壤之别，但它们其实是等价的。关于算法过程的这些共识后来被称 为丘奇-图灵论题。 图灵的构想与其他人的区别在于，他是通过一台抽象机器来表示的。其特性的惊人之处在于他表明了只要有无限的数据存储 能力，就算用非常有限的基础操作也足够实现所有算法。进而，他展示了无论是什么算法，都可以设计出一台称为“通用机 器”的机器来实现。这些远见在现代多用途计算机的发展中扮演着至关重要的角
32、色。但是，这些也会变成更加清晰的、通用性更 广的理念延伸至与计算相距甚远的数学领域。1 图灵从数学逻辑的一个问题开始他的研究，这个问题的重要性被大卫希尔伯特特别强调，其内容如下： 找到一个算法来判定根据给定前提和逻辑推理能否得出一个特定结论。 到1935年，有足够的理由相信这一算法并不存在，而这正是图灵要证明的。图灵先从用他的机器找到一个不可解问题开 始，看它对于一台给定机器是否会输出0。然后他展示了如何将这个“输出”问题转换为数理逻辑语言，这样就能使用一个算法 来解决这个输出问题，而后面他将证明这不可能实现。之后，波斯特用输出问题的不可解性证明了之前提出的半群单词问题同样 不可解。再之后，图
33、灵使用一个复杂构造改进和拓展了波斯特的结论。图灵优美的论文（Turing，1954）清晰简洁地向大众解 释了不可解性。 当图灵发现这项工作得出的结论与他在普林斯顿所做的工作类似时，他前往普林斯顿并在那里待了两年。一个被称为可计算 性理论、递归函数论或者递归论的数学新分支正在蓬勃发展。这个分支的一个方向是证明来自数学各个分支问题的不可解性。本 章将会讲述这个过程。 1 图灵1936年的这篇论文在许多地方被重印过多次。 1.1 方法概览 我们的讨论限制在自然数0，1，2，3，中，我们将使用三种不同的方法来获取一个特定的自然数集合： 一个列出集合中所有数的算法。 一个能判定元素是否属于集合的算法。
34、一个有解方程的参数值。 考察这些概念如何互相联系将会得出惊人和深远的结论。 1949年，当我还是研究生时，我猜想上面三个中的两个是等价的，即自然数集和通过自然数集确定的集合是一样的。尽管 这个猜想若为真可能会有非常重要的影响，但它看上去不像真的。我很难想象会需要20年来证明这一猜想，参与人员包括美国 最杰出的哲学家、第一位入选美国国家科学院的女数学家、一位年轻的俄罗斯数学家和我自己。 虽然数学上严格的处理需使用由图灵和之前提到的其他人提出的技术概念，但在本章大部分内容中，算法将以不那么严格的 松散方式处理。 1.2 例子：完全平方数集 通过将自然数乘以自身而获得的数称为完全平方数。因此，完全平
35、方数的集合是0，1，4，9，16，25，。 列出完全平方数的算法 从0开始，重复添加1，生成所有自然数的序列。每生成一个数字，乘以它自己并将结果放在一个列表中。 注意，完全平方数是无穷多的，所以列出这些数的计算将永远持续下去。下表第二行中展示了完全平方数列表： 定义 如果一个自然数集合存在列出其所有元素的算法（允许重复，可以任何顺序列出），则这个集合称为可列集。1 用于判定某个数是否隶属完全平方数集合的算法 要判定某给定数n是否是一个完全平方数，可如之前所述那样有序列出完全平方数。如果某个完全平方数等于n，即可停止程 序，并判定n是一个完全平方数；如果一个完全平方数大于n，也可以停止，并判定n
36、不是一个完全平方数。 定义 如果对于一个自然数集，有一个算法可以判定其元素所属，则这个集合称为可判定集。2 使用方程指定完全平方数的集合 在方程a-x2=0中，我们将a视为参数，x视为未知数。这意味着对于不同的a值，我们欲寻求满足方程的自然数x。因为这个方 程明显等价于a=x2，所以存在这种解的a的值正好是完全平方数。 通常当我们使用“方程”一词时，可以将其看成一个等于0的多项式表达式。多项式表达式可以涉及任何数量的未知数，并 且还可以包括参数a。可以通过使用加法、减法和乘法组合字母及任意数量的自然数常数来形成表达式。下面是一些多项式表达 式的例子： 定义 如果有一个带有参数a的多项式方程有自
37、然数解，那么a的可能取值组成的自然数集合称为丢番图集。 丢番图集的例子 a-（x+2）（y+2）=0定义了合数集，即大于1的非素数。 a-（2x+3）（y+1）=0定义了不是2的幂的自然数集（因为它们有非1的奇因子）。 佩尔方程x2-a（y+1）2-1=0已被很好地研究过。可以证明，除了明显的解，当a不是一个完全平方数时它有解。 1 可以代替“可列”的术语：可递归枚举、可计算枚举。 2 可以代替“可判定”的术语：可计算、递归的。 1.3 一些关系 定理 每个可判定的集合也是可列的。 证明 令S是可判定集。按顺序生成自然数。随着每个数字的生成，测试它是否属于S。如果是，将它放在一个列表中。移 动
38、到下一个自然数。该算法将列出S的元素。 集合S的补集，写为S，是不属于S的所有自然数的集合。 定理 集合S是可判定的，当且仅当S和S都是可列的。 证明 如果S是可判定的，那么显然S也是可判定的，因此两者都是可列的。 另一方面，如果S和S都是可列的，那么，给定一个数字n，我们可以按如下方法判定它是否属于S。我们用两个列举算法开 始制作S和S的列表，希望看看n最终出现在哪个列表中。然后我们将知道n是否属于S。 不可解性定理 有一个可列集K，其补集是不可列集，那么K是不可判定的。 证明 见附录。 定理 所有丢番图集都是可列的。 证明 令S是一个丢番图集，由一个含有参数a和未知数x1，xk的方程表述。
39、有序列出所有形如a，x1，xk的 （k+1）元组1，然后依次测试。对于每个元组，将数字代入方程。检查这些数字是否满足公式只是一个算术问题。如果方程由 特定元组满足，则将来自该元组的a的值置于列表上。该算法将列出S的元素。 1 给元组排序时，可以引入从小到大排列的自然数，对于每个自然数，均列出那些包含该自然数与该自然数之前的自然数元 组。元组排序如下：0，0，0，1，1，0，1，1，0，2，2，0，1，2，2，1，2，2， 1.4 猜想变成定理的故事 1950年写博士论文的时候，我冒着风险写下如下猜想： 猜想 每个可列集也是丢番图集。 表面上这个猜想相当不可信。为什么可以通过算法列出的任何集合也
40、可以通过简单的多项式方程来表示？此外，出于某些我 之后会解释的原因，这个猜想暗示着一些相当不可信的结论，即存在常数m和n，使得每个丢番图集可以由小于等于m的度数和 小于等于n的未知数方程指定。然而，如果这个假设为真，将可以引出对一个著名希尔伯特问题的解答。 在1900年国际数学家大会上，大卫希尔伯特列举了23个问题作为未来的挑战。这些问题被称为希尔伯特问题，除了它们的 内在价值之外，这些问题已经引起了特别关注，这源于希尔伯特在数学界的领军地位。列表中的第十个问题可以表述如下： 问题 找到一个算法来判定具有整系数的任何给定多项式方程是否具有自然数解。1 不难看出，若我的猜想为真，则会以否定的方式
41、来解决希尔伯特第十问题，即没有这样的算法存在。原因是我的猜想意味着 从上文不可解定理得到的集合K是丢番图集。因此，在参数a属于K的情况下，给定a为参数的方程将有解。因此，如果存在希尔 伯特所要求的算法，则其可以用于判定集合K的元素所属，这与K不可判定的事实相矛盾。 尽管它显然不可信，但我有理由认为我的猜想可能是真的。我能够证明有一个丢番图集S，其补集S不是丢番图集。与不可 解定理相比，这一结论是很惊人的。我的证明非常简短，但不具建设性（即证明没有给出任何这样集合的示例，而只能证明它的 存在性）。易知丢番图集是一个与可列集具有其他共同属性的类。2 我试图证明这个猜想，但如我的论文中所述，我能做到
42、的是证明对于每个可列集S，存在一个含参数a、q和k的方程，使得 数a属于S当且仅当有一个数q0，对于q=q0和所有kq0，使方程有解（注：利用逻辑符号 p（a，k，q，x1，xn）=0，其中，p是一个整系数多项式。）。尽管这和我想要的相差甚远，但这个结果在接下来的 过程中发挥了重要作用。 当我参加1950年在哈佛大学举办的国际数学家大会时，我结识了数学家朱莉娅罗宾逊，她所做的工作我非常熟悉，她也一 直在研究丢番图集。但是，我一直循着自顶向下的方式开展研究，试图为可列集找到一个类似丢番图集的表达方法，而她一直循 着自底向上的方式，尝试不同集合的丢番图定义。阿尔弗雷德塔斯基曾建议应证明2的幂集1，
43、2，4，8，16，不是丢番图 集。朱莉娅被这个问题所吸引，但她没有成功地证明塔斯基提出的猜测，转而试图证明2的幂集是丢番图集。当然，如果塔斯基 是对的，那么我的猜想就是错的。而朱莉娅也不能证明这个集合是丢番图集。但她证明了，如果可以找到一个（我称为）金发姑 娘方程，那么不仅2的幂集是丢番图集，而且素数集以及许多其他集合也是丢番图集。 在民间故事中，金发姑娘偷偷来到小熊家，看到椅子、食物和床时，她都先确定哪些太大，再确定哪些太小，最后才找到那 些“刚刚好”的。这里我们考虑具有两个参数a和b的方程。如果存在使方程有解的a和b满足baa，则这样的方程太大了。如果 有一个数k，使得对于使方程有解的所有
44、a和b满足bak，则它太小。因此，当一个方程既不太大也不太小时，才是刚刚好的金 发姑娘方程。朱莉娅试图找到这样的金发姑娘方程，但她没有成功。 1957年夏天，希拉里普特南和我开始在康奈尔大学历时一个月的“逻辑学院”内合作。我们在那个夏天获得了一些初步结 果，但突破发生在两年后。我们的想法是看看如果在方程里允许有可变指数，我的猜想会有什么变化。因此除了像x5y- 7y3a2z+5=0这样的方程，我们也考虑像x5yz-7y3a2z+5=0这样的方程。虽然我们从我的论文开始入手，但是引入可变指数恰好 将我们带入了朱莉娅罗宾逊的领域，我们发现自己在使用一些她的方法的推广。由带有一个参数的方程指定的集合
45、（其中允许 可变指数）称为指数丢番图集。我们试图证明： 每个可列集都是指数丢番图集 （*） 我们接近目标了。但是我们必须利用一个虽然被广为相信但尚未证明的素数性质： PAP 对于任何自然数n，必有素数p和自然数k使得自然数p，p+k，p+2k，p+nk都是素数。 我们试图证明： 定理 如果PAP是对的，那么（*）也是对的。 实际上，我们现在知道PAP是对的，因为它已在2004年被证明。所以在某种意义上，我们的关于（*）的证明也是正确 的。但是在1959年，没有时间机器，我们不得不满足于仅仅只有暗示。 金发姑娘方程的存在也引人注目。从朱莉娅的工作中很容易得出，如果有一个金发姑娘方程，那么每个指数
46、丢番图集也是丢 番图集。希拉里和我引入了缩写： JR 存在一个金发姑娘方程。 所以我们已经证明，如果JR和PAP都是真的，那么我的猜想也是真的。 我们写下了所有这些用于发表，当然，也发送了一份副本给朱莉娅。她很快给了回复：她对我们的工作表示高兴，并告诉我 们，她已经找到了规避PAP的方式。她的第一个对（*）的证明相当复杂和巧妙。但后来，她大大简化了它，实际上，她将证 明分成一个不需要素数的部分，并展示了在仍需素数的证明部分如何规避PAP。我们三个人同意合著一份带有脚注的论文，标注 各自做出的贡献。 所以现在，为了证明我的猜想，仍需证明JR，即找到金发姑娘方程。但尝试十年，我们中还是没有人能够想
47、到如何构建一个 金发姑娘方程。普遍的意见仍然是，我的猜想是错的，所以，仅仅是金发姑娘方程不存在而已。在那些年我对我们的工作做宣讲 的时候，常常指出如果没有金发姑娘方程，那么每一个具有两个参数的方程都会变得太小或者太大，这和我的猜想一样令人惊 奇。在提问阶段，有人几乎确定地问我关于这样的方程的存在性问题。我打趣道：“噢，我觉得JR是对的，它将被一个年轻聪明 的俄罗斯人所证明。”事实证明我是一个预言家。那位俄罗斯人叫作尤里马季亚谢维奇，他在1970年，在他还是22岁的时候， 就展示了一个金发姑娘方程。尤里使用了著名的斐波那契数列：1，1，2，3，5，8，13，（除了前两个数以外，每个数都是 它之前
48、两个数的和）。如果把第n个斐波那契数写作Fn，那么尤里的等式有u和v两个参数，并且这个等式的解满足形式v=F2u。 根据我们对斐波那契数的理解，这显示了他的等式确实是“刚刚好正确”。 在我提出猜想20年之后，它最终从猜想演变成了定理。因为马季亚谢维奇在证明中使用的非常美丽的构造，这个定理常常 被称作马季亚谢维奇定理。它也常常被称为MRDP定理，来彰显我们四个人在这个定理构建过程中所扮演的角色。尤里自己也慷 慨地建议把它叫作DPRM定理： 马季亚谢维奇/MRDP/DPRM定理 如果一个集合是可列的，那么它同样是丢番图的。 这个定理有令人惊奇和十分重要的结果，部分结果已经在前面提及，但值得在这里重
49、述一下。回想一下集合K是可列的，但 不是可判定的。 推论 存在一个多项式po（a，x1，xl），使得等式po（a，x1，xl）=0确定了集合K。因此，不存在这样一个算法， 该算法可判定对于一个给定值a，是否存在一系列自然数x1，xl满足该等式。 之前已经提到，这表明： 希尔伯特第十问题（丢番图方程的可解性）的不可解性 推论 不存在这样一个算法，该算法可判定对于一个拥有整系数的多项式方程，该方程是否具有自然数解。 1 事实上，希尔伯特想找一个对于任意整数（正整数、负整数和零）均成立的算法。然而，不难证明，这两种形式的问题是等 价的。 2 例如，两个丢番图集合的并集或者交集依然是丢番图集。 1.5