叹息与奋斗

计算无处不在。

进入计算机房，听着服务器排成一排的墙之间风扇的噪音，你似乎可以闻到0和1在*处理器和内存之间的连续流动。从计数和计数到今天的计算机，我们用来计算的工具终于开始有质的飞跃。电脑可以做越来越多的事情，甚至超过它们的制造商。上世纪末，深蓝凭借其前所未有的搜索和判断国际象棋的能力，成为第一台击败国际象棋世界冠军的计算机，但它的胜利仍然依赖于人类大师丰富的国际象棋知识。然而，仅仅过了10年，沃森已经能够用自己的算法“理解”这个问题，然后有针对性地在大量数据库中找到相关答案。从长远来看，这种工具将在更多方面超越它的制造者。所有这些都来自越来越复杂的计算。

计算似乎无所不能，就像一个新的上帝。但即使是这个“上帝”也无法逃脱逻辑设定的界限。

图灵是第一个发现这个的人。

“计算的极限”系列

波斯特哀叹时代的流逝，断言有一些形式系统，我们不能在有限的时间内知道这些命题中的一个是否能被证明。可以说，他的断言与10年后哥德尔的不完全性定理非常相似。那么，为什么“不完全定理”之前的名字不是波斯特，而是数学史上的哥德尔？因为尽管《邮报》在1921年获得了这一结果，但它必须等到1943年，在哥德尔、图灵和丘奇的黄金时代过去之后，才能在很短的时间内出版。

他跟不上时代。

当时，美国数学界对数理逻辑普遍不感兴趣。波斯特和他的导师凯泽当时是不同的。直到欧洲数学家在第二次世界大战前夕移民到美国，这种情况才开始改变。波斯特曾将他的想法写在接下来的两篇论文中，并将第一篇提交给《数学年鉴》。然而，他收到的答复非常令人失望。同行评议报告在是否应该出版的问题上意见不一，编辑部也没有给出具体的决定。如果前一个没有理论基础，那么下一个只是空谈。

但没人感兴趣并不是最致命的问题。事实上，波斯特没有真正的证据。也就是说，他实际上并没有证明他的结论，那只是一种推测加上一些关于证明的想法。尽管他的结论和想法从我们的后见之明来看是正确的，毕竟，他没有一个可以被其他人详细检验的证据。

在数学中，证明就是一切。没有证据，即使结论似乎是正确的，即使有更多的间接证据，即使最好的数学家的想法只能是猜想，而不是定理。要建立一个定理，必须有无懈可击的证明。这是数学的规则。不幸的是，波斯特的研究风格比图灵的更直观，换句话说，不那么严谨。波斯特的直觉足以预见超越时代的结论，但他没有相应的能力在当下将他的直觉组织成严密而有组织的证明。他的野心超过了哥德尔，甚至超过了图灵和丘奇，但他没有足够的工具或能力来完成这样一个伟大的目标。

但是也许波斯特可以花更多的时间整理他的想法，并写一份完整的证明来说服数学界。不幸的是，命运没有给他这样的机会。

波士顿取得突破后不久，也许是因为结果的影响太大，他的头脑失去了平衡。然而，论文未能发表加剧了这种混乱。他患有躁郁症，病人会在无缘无故的快乐和无缘无故的抑郁之间摇摆。从那以后，他被双相情感障碍困扰了10多年，并且在数学方面没有任何成果。由于受到攻击，应用型大学的教学岗位不得不放弃。在此期间，他只能以中学教师的身份生活。直到1935年，他才回到学术界。

从1921年到1935年，波斯特错过了哥德尔、图灵和丘奇。当他困惑的时候，时代的巨轮已经呼啸而过，他错过了数理逻辑的黄金时代。1941年，他写了一篇文章，详述了他以前关于逻辑不完全性的工作，并加入了《美国数学杂志》。当时的编辑赫尔曼·韦尔拒绝了这篇文章:

我毫不怀疑你20年前的作品没有受到尊重，部分原因是它的革命性。但是我们不能让时针倒转。在此期间，哥德尔、丘奇和其他人完成了他们的工作，而《美国数学杂志》不是发表历史评论的地方。

作为一名编辑，威尔的决定是正确的。探索的前线不是救济迷失的地方；历史是。历史不会忘记这些被忽视的探险家，他们所有的成就、痛苦和悲伤。波斯特厚厚的研究笔记是历史的见证。那时发生的事情将会被人们一次又一次地以不同的形式变成类型和重复，成为集体记忆的一部分。

我们所能做的就是为传说写诗并一直传播它们。

来自维基媒体

对波士顿来说，错过时代的节拍不是最大的打击。

那时，人们对精神疾病的理解还很肤浅。没有有效的药物或有效的疗法，一切都要探索。波斯特的躁郁症也没有标准疗法。当时的想法是，既然狂喜和抑郁的极端情绪出现在发作期间，就应该尽可能避免这种极端情绪的发生。最好的方法是限制导致极端情绪的活动，这就是波斯特的数学。他的医生开出的治疗方法是限制波斯特的数学时间:从下午4: 00到5: 00，吃东西，然后从晚上7: 00到晚上9: 00，一天总共三个小时。对于热爱数学的数学家来说，这是一种类似于精神疾病的折磨，就像让美食家用牙签吃他们最喜欢的肉酱意大利面一样。我不知道波斯特是如何忍受这种焦虑的。

幸运的是，波斯特没有停下来。症状缓解后不久，他又回到了数理逻辑的研究。就在图灵发表了他关于图灵的论文之后，波斯特在对图灵的研究一无所知的情况下，发表了另一个与图灵非常相似的模型，现在叫做波斯特机器，它更类似于我们的普通计算机。驱动计算的与其说是状态的转移，不如说是语句的执行。他猜想波斯机器具有与λ演算相同的计算能力，这是一个正确的猜测，但当时他无法证明这一点。图灵的王冠没有半途而废。在看过图灵的结构和证明后，波斯特把这一切都记在心里。他的探索又失去了意义。他还考虑了图灵机在许多维度上的扩展，这与后来的“细胞自动机”非常相似。著名的“生命游戏”是细胞自动机的一个例子。不幸的是，他没有发表这个想法。

后来，波斯特转向布尔函数的研究，即那些变量和值为“真”或“假”的函数。1941年，他发表了一个非常重要的结果:具有复合闭函数的布尔函数类的分类定理。这些类别形成了一个称为“格”的数学结构，现在称为“后格”。对当时的研究人员来说，尽管波斯特的结果非常有意义，但研究的对象还是有些偏见。此外，波斯特的典型的模糊和晦涩的写作风格，波斯特的结果在当时没有得到太多的关注。直到几十年后，当人们研究约束满足的问题时，邮差才回到人们的眼前。

来自*

虽然这个结果起初并不被重视，但它仍然是一个严肃的研究结果。这样，通过不懈的努力，波斯特逐渐赶上了当时数理逻辑的研究趋势，尽管每天只能做三个小时的研究。

1944年，波斯特应邀在美国数学协会发表演讲。后来，他把演讲的内容写进了一篇论文并发表了。他自己可能没有想到这篇论文会成为他最有影响力的论文之一。本文的主题是“正整数的递归可枚举集及其判定问题”。它想回答的问题很简单:关机问题有多难？有没有比关机问题更容易计算的问题？

有时错过时代的节拍也可能是一件好事，至少对波斯特来说，他与主流的疏远给他带来了不同的视角。对他来说，判断问题的计算是形式系统的演绎和证明，形式系统的相互包含是一个非常自然的问题。例如，定义自然数的Piano公理系统是一个形式系统，该系统中的所有命题都可以被翻译成集合论的zermelo-Frank (ZF)公理系统，并且可以被Piano公理证明的数学命题在翻译后可以在ZF得到证明。可以说，ZF体系包括钢琴公理体系。然后，给定两个不同的公理系统A和B，我们自然要检查它们的包含关系，例如，B是否包含A。换句话说，我们想知道是否有办法把A中的命题翻译成B，并希望翻译后，A中可以证明的命题仍然可以在B中得到证明

证据法规

波斯特的另一个优点是，他以前的研究已经涉及到了这类具体的翻译问题，但所使用的术语不是翻译，而是简化。从一般形式系统到规则形式A，然后到规则形式B，然后到一个非常特殊的演绎规则，这些都是归约。在形式系统不完全性的研究中，波斯特自己已经构造了许多这样的约简。从特殊归约到一般的“归约”概念，对数学家来说只有一步之遥。

为了简洁起见，波斯特没有使用正则形式的概念，而是将计算问题表示为一组自然数。对于数学逻辑学家来说，无论是形式系统、判断问题还是一组自然数，本质上没有区别。形式系统的命题可以用字符串表示，因此它们可以转换成自然数。判断一个命题是否可以从公理中推导出来，等同于判断相应的自然数是否属于相应的可推导命题集合。对应于集合的决策问题是输入是否作为自然数存在于集合中。因此，指定由自然数组成的集合相当于指定一个决策问题。在这个框架下，约简的定义更加方便和直观。

有许多不同种类的还原，它们是强的和弱的。波斯特在研究形式系统时使用了约简，即上面提到的“公理系统之间的翻译”，它是较弱的一种，也称为“多一约简”。然而，最强的图灵约简在判断A中命题的对错时，可以在可计算的范围内任意生成B中的命题并得到解，然后从这些解的任意个数中提取结论。你能得到的答案越多，你能解决的问题就越多，也就是说，你的能力就越强。

图灵归约是波斯特研究的最终目标，但它的能力太强，无法研究。因此，在这篇1944年的论文中，波斯特主要研究了更简单的一个——更多的约简和另一个稍强的“真值表约简”。他证明了在两种归约方法定义的困难概念下，存在这样的计算问题，它们是可计算的，但比停机问题容易。换句话说，如果根据这些简化定义的难度进行排序，在可计算问题和停机问题之间有无数的“中间层次”。从可计算问题到停机问题的这一步实际上已经跨越了无数个层次。

文章最后推测，为了更强的图灵归约，这样的“中间层次”也存在，不仅如此，还有无数的中间层次是可计算枚举的。这并不明显，因为减少的越多，不同问题之间的差距就越难填补。例如，又一个归约者认为问题A比问题B更难，但这可能是因为它太弱了。如果用图灵归约法代替，可以通过问更多的问题来得到答案。波斯特关于在计算中是否有一个枚举“中间层次”的问题也被称为波斯特问题。

波斯特在这篇论文中的新观点和新成果最终引起了美国逻辑学家的注意，并最终得到了他作为一名数学逻辑学家应得的赏识。也许他不需要任何安慰。

在那次演讲之后，在美国数学协会的一次聚会上，一个男人拦住了波斯特。这个人的名字叫克林，他也是一名数学逻辑学家(一些读者可能还记得提出λ微积分的丘奇，他是他的博士生导师)。他告诉波斯特他想看些东西，并邀请波斯特去他家。

这是波斯特和富兰克林之间伟大合作的开始。

来自*