置身图灵可计算的世界，探索普适性数学 _数学家

文章插图

图灵机的艺术化表示(图自维基)
1954 年，图灵在《企鹅科学新闻》上发表了他的最后一篇论文，这篇论文向广大读者传达了数学中可计算性的重要性。但他并没有对自己的图灵机做出太多改进：只有一篇论文将它应用于代数学中的一个可判定问题，完全未涉及新兴的计算机科学。这在数理逻辑上留下了一个缺口，直到 1958 年才被马丁·戴维斯在他的专著《可计算性和不可解性》中系统解决。目前，戴维斯对图灵在 1954 年为阐释“希尔伯特第十问题”——丢番图方程可解性问题所做的略微通俗的工作进行了仿真，在这项工作里图灵对可计算性进行了非常完备的定义。1970 年，马丁·戴维斯对这一问题的优美解法做出了主要贡献，并且指出这项工作是如何精炼和拓展了图灵 1936 年经典论文的关键部分。
最令人震惊的是马丁关于普适性和不可计算性的看法。从他与合作者的著名工作中得出的结果优雅地阐明了图灵可计算性在经典层面上的延伸和局限。图灵后来的工作预料到了现今人们对从自然过程中得到的“新计算范式”和虚拟机前景的兴趣。关于这些计算模型能在何种程度上归属于图灵 1936 年的范式，有许多重要和深刻的问题被提出，并随着虚拟机的发展进入了应用层面。普适性和延伸的概念持续不断地给今天的学者带来基本问题。

文章插图

马丁·海兰通过发掘阿兰·图灵与罗宾·甘地的紧密联系填补了历史缺失的一角。这是阿兰·加纳故事的姊妹篇，是同一段岁月中的另一段秘史。他使图灵曾经研究过但从未获得成果的议题重新焕发了生机，这便是类型论。当时人们觉得这个理论十分抽象，现在则将其视为计算机科学（一个在图灵时代并不存在的概念）形式结构的关键，更广泛地讲，与科学理论中语言的使用有关。
马丁的贡献集中在与大多数现今科学关注点相比鲜为人知但相当基础的观点。罗宾·甘地早期研究论文的标题《关于理论物理学基础理论逻辑结构的一些思考》为科学与逻辑框架接下来的融合提供了清晰关联。之后发展的一个关键方面是图灵和甘地对于丘奇类型论相互关联的兴趣。马丁指出：
【置身图灵可计算的世界，探索普适性数学】图灵作为导师对甘地的影响明确和类型论有关，我在开始写这一章的时候想，图灵对这一领域的兴趣很大程度上被遗忘了。
马丁说：“是时候聊聊兴趣了。”紧接着是书中最引人入胜的讨论之一，提出了图灵与众不同的并且往往是有预见性的、以一种相当独特的方式对抽象和具象进行的关联。在此后的一百年间未曾有人涉及此领域，更别提以这样一种权威和博文广识的方式。
安德鲁·布克通过讲述图灵在 1939 年开始制作的特殊机器和 1950 年在曼彻斯特计算机上编程的故事，阐述了图灵在解析数论中的工作，为软件如何替代特殊机器编程给出了一个非常好的示例。布克的讨论将话题引到了著名问题黎曼猜想的现代地位和图灵计算理念长久的重要性上。
安德鲁·布克对数论中图灵工作的描述强调了图灵往往对更深远的问题感兴趣。在这种情况下，他意识到计算机的出现会不可避免地影响数学证明的本质，并对数学家们如何适应这些改变做出了有远见的猜测。图灵后来写作的一大主题是思索计算机如何与人类创造力相辅相成，以及思维和机器之间平衡的演变。正如布克所说，这个越来越重要和复杂的关系甚至可能会导致道德方面的影响。

文章插图

在布莱切利园重建的“图灵-威尔士曼炸弹”解码机。照片经约亨·菲霍夫授权
有感于我们对图灵战前的密码学思考和新兴的密码安全问题知之甚少，乌力·毛勒讲述了另一个平行的故事。他这样来描述这一部分：
计算和信息是计算机科学中两个最基础的概念，就像质量、能量、时间和空间是物理学中的基础概念一样。
他接下来描述了图灵计算模型和克劳德·香农信息论扮演的重要和互补性作用。除了现代密码学的实际问题之外，他的讨论还涉及另一当代尚未解决的重大问题，即 P=NP? 问题。乌力·毛勒写道：
人们只能猜测，如果图灵在理论密码学上花费更多时间的话，他能够在这一领域取得什么样的成就。