置身图灵可计算的世界（探索普适性数学）

TIPS：本文共有 2244 个字，阅读大概需要 5 分钟。

1954 年，图灵在《企鹅科学新闻》上发表了他的最后一篇论文，这篇论文向广大读者传达了数学中可计算性的重要性。但他并没有对自己的图灵机做出太多改进：只有一篇论文将它应用于代数学中的一个可判定问题，完全未涉及新兴的计算机科学。这在数理逻辑上留下了一个缺口，直到 1958 年才被马丁·戴维斯在他的专著《可计算性和不可解性》中系统解决。目前，戴维斯对图灵在 1954 年为阐释“希尔伯特第十问题”——丢番图方程可解性问题所做的略微通俗的工作进行了仿真，在这项工作里图灵对可计算性进行了非常完备的定义。1970 年，马丁·戴维斯对这一问题的优美解法做出了主要贡献，并且指出这项工作是如何精炼和拓展了图灵 1936 年经典论文的关键部分。

最令人震惊的是马丁关于普适性和不可计算性的看法。从他与合作者的著名工作中得出的结果优雅地阐明了图灵可计算性在经典层面上的延伸和局限。图灵后来的工作预料到了现今人们对从自然过程中得到的“新计算范式”和虚拟机前景的兴趣。关于这些计算模型能在何种程度上归属于图灵 1936 年的范式，有许多重要和深刻的问题被提出，并随着虚拟机的发展进入了应用层面。普适性和延伸的概念持续不断地给今天的学者带来基本问题。

马丁·海兰通过发掘阿兰·图灵与罗宾·甘地的紧密联系填补了历史缺失的一角。这是阿兰·加纳故事的姊妹篇，是同一段岁月中的另一段秘史。他使图灵曾经研究过但从未获得成果的议题重新焕发了生机，这便是类型论。当时人们觉得这个理论十分抽象，现在则将其视为计算机科学（一个在图灵时代并不存在的概念）形式结构的关键，更广泛地讲，与科学理论中语言的使用有关。

马丁的贡献集中在与大多数现今科学关注点相比鲜为人知但相当基础的观点。罗宾·甘地早期研究论文的标题《关于理论物理学基础理论逻辑结构的一些思考》为科学与逻辑框架接下来的融合提供了清晰关联。之后发展的一个关键方面是图灵和甘地对于丘奇类型论相互关联的兴趣。马丁指出：

图灵作为导师对甘地的影响明确和类型论有关，我在开始写这一章的时候想，图灵对这一领域的兴趣很大程度上被遗忘了。

马丁说：“是时候聊聊兴趣了。”紧接着是书中最引人入胜的讨论之一，提出了图灵与众不同的并且往往是有预见性的、以一种相当独特的方式对抽象和具象进行的关联。在此后的一百年间未曾有人涉及此领域，更别提以这样一种权威和博文广识的方式。

安德鲁·布克通过讲述图灵在 1939 年开始制作的特殊机器和 1950 年在曼彻斯特计算机上编程的故事，阐述了图灵在解析数论中的工作，为软件如何替代特殊机器编程给出了一个非常好的示例。布克的讨论将话题引到了著名问题黎曼猜想的现代地位和图灵计算理念长久的重要性上。

安德鲁·布克对数论中图灵工作的描述强调了图灵往往对更深远的问题感兴趣。在这种情况下，他意识到计算机的出现会不可避免地影响数学证明的本质，并对数学家们如何适应这些改变做出了有远见的猜测。图灵后来写作的一大主题是思索计算机如何与人类创造力相辅相成，以及思维和机器之间平衡的演变。正如布克所说，这个越来越重要和复杂的关系甚至可能会导致道德方面的影响。

有感于我们对图灵战前的密码学思考和新兴的密码安全问题知之甚少，乌力·毛勒讲述了另一个平行的故事。他这样来描述这一部分：

计算和信息是计算机科学中两个最基础的概念，就像质量、能量、时间和空间是物理学中的基础概念一样。

他接下来描述了图灵计算模型和克劳德·香农信息论扮演的重要和互补性作用。除了现代密码学的实际问题之外，他的讨论还涉及另一当代尚未解决的重大问题，即 P=NP? 问题。乌力·毛勒写道：

人们只能猜测，如果图灵在理论密码学上花费更多时间的话，他能够在这一领域取得什么样的成就。

但是图灵在 1938 年之后所做的工作仍然是个秘密。黛利拉的语音加密项目报告持续 50 年都不为人知，直到 2012 年全文才被发表。同样在 2012 年，两篇相当基础的图灵论文被公开，这两篇论文解释了贝叶斯分析的基础和它在海军恩尼格玛（Enigma）“班部里斯马斯”（Banburismus）解码法中的应用。接下来也许还有更多值得期待。

GCHQ 为纪念图灵诞辰一百周年而及时发布的新版本让我们回忆起阿兰·图灵在布莱切利园做出的最具原创性和重要意义的贡献。能够造出用来拦截德军消息的“炸弹”和“巨人”解码机的关键在于贝叶斯统计技术的应用。在第 5 章中，统计学家坎蒂·马蒂亚和逻辑学家巴里·库珀仔细分析了发生在布莱切利园的这一段历史，并谈到了对于我们现在的“大数据”而言统计的重要性。“恩尼格玛统计学是现在所谓的统计生物信息学的前身”，这一章中写道。

通过详实的事例、内容大纲和已发布的重要论文，马蒂亚和库珀把我们带回了类型信息的数学基础，以及为了对经典图灵计算得到的数据进行“类型归约”而使用的抽样技术。从这种角度，他们讲述了图灵的贝叶斯技术发挥的译码作用如何使我们在更广的语义中理解“大数据”面临的挑战。

本文摘自机械工业出版社《永恒的图灵：20 位科学家对图灵思想的解构与超越》，[遇见] 授权发布

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

如果觉得《置身图灵可计算的世界（探索普适性数学）》对你有帮助，请点赞、收藏，并留下你的观点哦！