逻辑大结局——直觉、复杂度和终极悖论，统治一切的程序
在古希腊法庭上既没有直接证据也没有目击证人会怎样？陪审团不能依赖亚里士多德的逻辑，因为原告和被告都不使用逻辑来揭示真相。亚里士多德描述了以下一个案例：
一个小个子X指责一个大个子Y袭击了他。一个陪审员问X一个假设性的问题：如果是你先挑起的争斗呢？
X可以争辩说，一个更小更弱的人“不可能”挑起战斗，因为他“肯定”会吃亏。
另一方面，Y可能会反驳说，他看起来比X大得多、强壮得多，“不太可能”发动战斗，因为他在法庭上“肯定”百口莫辩。
陪审团需要决定哪一方的“推理”更“可信”。有趣的是，这种推理和数学家解决问题的原理是一样的。
波利亚（George Pólya）：直觉作为似然推理
波利亚，1887 - 1985
波利亚，匈牙利数学家，现代数学教育问题之父，认为数学直觉的背后是似然推理，这与庞加莱关于逻辑和直觉的观点一致。他的名言脍炙人口：
数学家创造性工作的结果是演示推理，但证据是通过似然推理和猜测发现的。
波利亚没有赞美伟大的数学家的直觉，或者嫉妒他们的运气，而是使用一本推理手册来揭开他们的猜测艺术的神秘面纱。下面的图表显示了如何从一个一般的三角形开始，遵循不同的似然推理模式得到一个等边三角形，通过类比得到一个四面体或多面体，通过概括来得到一个一般的多边形。
似然推理模式
关于类比，波利亚说：
类比贯穿于我们所有的思维，我们的日常讲话和我们得到琐碎的结论，以及艺术的表达方式和最高的科学成就。
似然推理适用于解决问题，也适用于所有层次的科学发现。例如，图灵在停机问题的不可解性和形式系统的不完备性之间进行了类比，哥德尔将其与德国数学家康托尔提出的关于实数是否多于自然数的问题进行了类比。
回顾希尔伯特的判定问题
现在，让我们回顾希尔伯特的判定问题来看看似然推理或直觉在其中扮演了什么角色。由于判定问题产生于计算机发明之前，希尔伯特和他的同事们肯定不了解计算机科学。他们可能“直觉地”认为，“数学直觉”可以用简单的蛮力搜索代替，在所有可能的证明步骤中。他们几乎肯定忽略了这种搜索的运行时间，这是有问题的。为了理解这一点，如果我们换个方式问问题呢？考虑到我们只对比N短的证明感兴趣。对不同的N，我们有计算判定问题。对于这样一个计算判定问题，肯定有一个解决方案，那就是简单地循环所有可能的比N短的证明。现在的问题从可能性变成了可行性：当N变大时，这种蛮力搜索可行吗？
这就是计算复杂度的来源。根据计算复杂度理论，运行时间主要有多项式和指数两种。给定一个规模为N的问题，前者的运行时间以N的多项式速度增长，如2N或3N^2，后者的运行时间以N的指数形式增长，如2^N或3^N。一个以指数增长的问题被认为是“不可行的”，因为对于这样的问题，即使使用一台消耗了宇宙中所有资源的计算机，也要等待宇宙的年龄那样长的时间才能得到答案。
人类vs.机器证明
如果已经有一个证明，我们可以写一个多项式时间程序来检验它的可行性。然而，这并不意味着一个程序“找到”一个证明是多项式时间。可以用多项式时间程序求解的复杂度类别称为P，而通过“猜测”一个答案并在多项式时间内验证它可以解决的问题称为NP。我们可以看到，机器验证是NP。复杂度类别P包含所有在多项式时间内可解的问题，它包含在NP中。一个问题是根据已知的解决它的最快程序分配一个复杂类别（如P或NP）。因此，当发现一个更快的程序时，问题可能会改变类别。目前，计算判定问题被考虑在NP类中。对于机器证明多项式时间解是否存在有多大意义？
哥德尔预见到了计算复杂性理论的重要性，并在1956年写给约翰·冯·诺依曼（1903-1957，数学家，物理学家，以冯·诺依曼结构而闻名）的信中写道：
如果真的有一台机器具有[运行时间]kN（或者甚至只有kN^2）[对于某个与N无关的常数k]，这将产生巨大的后果。也就是说，它将清楚地表明，尽管判定问题是不可解的，但数学家在是或否问题上的脑力劳动可以完全被机器取代。人们确实需要选择一个如此大的N，如果机器没有产生结果，那么也就没有理由进一步思考这个问题。
“数学家的脑力劳动”是什么？根据庞加莱和波利亚，数学家解决问题分两个阶段：第一阶段，使用似然推理（直觉），或猜测艺术，形成猜想；第二阶段，使用逻辑来证明猜想。同样，机器证明分为两个阶段：寻找证明和逻辑验证证明。希尔伯特最初的问题是，是否存在一种普遍的证明机制来消除使用直觉的必要性。哥德尔有效地将问题重新表述为，是否存在多项式时间的“智能”搜索或相当于直觉的“巧妙”猜测。
机器证明vs人类证明
斯蒂芬·库克和列奥尼德·列文：统治一切的程序
布尔可满足性（SAT）问题询问是否对布尔公式中的变量赋值为0 （FALSE）或1 （TRUE），例如(x1 ∨ ¬x2) ∧ (¬x1 ∨ x2 ∨ x3) ∧ ¬x1，它的值为1。斯蒂芬·库克和列昂尼德·列文，美国-加拿大计算机科学家和数学家，俄裔美国数学家，分别独立证明了SAT在P时，即具有多项式时间解，那么“所有”NP问题可以简化为SAT，并在多项式时间内求解。换句话说，这意味着P=NP，因为所有NP问题都可以在多项式时间内被解决！
判断这样一个超级程序是否存在被称为P vs NP问题，这被认为是现代科学中最大的开放性问题。正如我们现在所看到的，哥德尔所认为的“巨大的后果”实际上是P=NP。多项式时间SAT解算器是“一个程序来统治所有的程序”，就像《指环王》中的“一个环”。还有一些像SAT这样的问题，它的答案是P=NP。所有这些问题统称为NP完备问题。
今天的SAT解题器已经被用于解决数学难题、芯片设计、软件检查等许多领域。为什么我们仍然关注P vs NP？如果“一个程序”出现了，并由此证明了P = NP，那么它将与停机问题和普遍证明机制一样具有破坏性。数学上的独创性和创造力将变得微不足道，数学家们将不再需要在合理推理方面的训练。事实上，它甚至会完全消除人工智能和机器学习领域充满活力和激动人心的研究的必要性。从本质上说，这将是对数学家和计算机科学家的精神努力的最后一击。今天，人们普遍认为“一个程序”不存在，即P != NP。就像图灵证明停机问题无解一样。证明P != NP是极其困难的。这种P与NP之间的屏障，似乎是“人类的守护者”。
人工智能与人类
如今，人工智能研究人员正试图让计算机学会我们如何利用直觉，而不是像形式主义者所希望的那样，试图取代人类的直觉。正如逻辑研究的是逻辑推理如何独立于其应用的环境，现代AI研究的是相对独立于其使用和产生的数据的直觉。
问题是，我们是想让人工智能模仿我们每个人，还是跨代地模仿我们所有人？为了回答这个问题，让我们来看看过去我们是如何解决难题的。
最长的证明（200tb）是对布尔毕达哥拉斯三元组问题的证明
有没有可能把每个正整数都涂成蓝色或红色，这样就不会有满足勾股定理a^2+b^2=c^2的整数三联体a、b、c是完全相同的颜色？
这个问题是在20世纪80年代提出的。然而，直到2016年Heule等人证明，到7824之前，用这种方式为整数着色是可能的，但从7825开始就不可能了。证据如此之长，人类要花100亿年的时间才能读取全部200tb的数据。
至于解决一个问题所需的时间，人类证明四色定理花了125年，费马大定理更是花了358年！
关于人类能否成为人工智能的“榜样”，可能有两个问题：
人类证明者在他们的证明中使用了计算机
前面提到的这些问题在数学界被广泛研究和讨论了几十年甚至几个世纪之后才被解决。
对于第一个问题，人类将乏味的任务交给计算机就像一个程序调用子例程或库。关于第二个问题，如果人类可以随着时间的推移积累数学知识，那么人工智能使用互联网的速度也可以快一个数量级。事实上，人工智能最近取得突破的原因之一是，它消耗和消化人类的思维。
看来，我们不是试图让人工智能成为一个数学天才，而是让它遵循人类的集体思维。然而，人工智能是否能在辩论、头脑风暴和交换想法方面模仿人类的智力合作还有待观察。
最后一个悖论
让我们回顾一下到目前为止所讨论的内容：
亚里士多德为正确的推理建立了逻辑，而用直觉建立了第一原则。
从亚里士多德到希尔伯特，数学家和逻辑学家已经发展了从心理和语言技能到符号操作科学的高级逻辑。
相信逻辑是基础和唯一的驱动力，形式主义者努力“机械化”数学，以消除使用直觉和（对人类）有意义的必要性。
哥德尔和图灵表明，形式主义者的梦想是无法实现的“可计算性”，因为不可避免的自我参照悖论在他们的系统中；计算机被认为是一种证明直觉必要性的工具。
从“计算复杂度”的角度来看，由于指数时间的蛮力搜索，判定问题的不可解性可以被视为不可行的。
与形式主义者的直觉方法相反，人工智能研究人员正试图模仿人类利用直觉解决问题的方式。
有朝一日人工智能会完全取代数学直觉吗？哥德尔，一个自我承认的柏拉图主义者，相信人类永远优于计算机，而且永远不会被计算机程序取代。他谈到了人类思维的发展：
思维在使用中不是静止的，而是不断发展的，也就是说，随着我们不断地使用抽象术语，我们对它们的理解也越来越准确，越来越抽象的术语进入了我们的理解范围。
显然，他并没有把人类优于机器的原因归结于个人，而是归结于集体的、跨代的人性。矛盾的是，如果人类如此优越，为什么它不能在足够的时间内写出能思考的程序？随着我们的发展，人类的思维一直在不断进化。在电脑发明后，我们不再强调用算盘计算，也不再使用纸和铅笔计算。事实上，我们仍处在发现我们为计算机编程的潜力的早期阶段。
另一方面，图灵相信机器最终可以超越人类：
不可能同时战胜所有的机器。简而言之，可能会有人比任何机器更聪明，但也可能会有其他机器更聪明，以此类推。
然而，图灵认为，人类将是决定机器是否比人类更聪明的最终裁判。在他具有里程碑意义的论文《计算机器与智能》中，图灵描述了图灵测试，在这个测试中，一台计算机试图以智慧战胜一个人类审问者，使其相信自己是人类。他提出，如果人工智能能够通过这样的测试，它就应该被认为是能够思考的。
发展中的思维和更聪明的AI之间的自我参照关系如下所示：
另一方面，如果人类和人工智能在这样一个正反馈循环中相互提升会发生什么？那么，接下来要问的问题就是：人类和人工智能是否会融合在一起，成为科幻小说和推测性未来预测中经常描述的那种类似上帝的实体？例如，在艾萨克·阿西莫夫的科幻短篇小说《最后一个问题》中，人类一直在询问全球人工智能计算机Multivac，如何逆转热力学第二定律，使宇宙免于热死，故事以万能的进化人，Multivac的后代与人类融合，点燃了下一个宇宙的大爆炸而结束。
在现实中，根据图灵的说法，随着我们不断发展人工智能，我们对自己的了解也越来越多：
整个思考过程对我们来说仍然相当神秘，但我相信，制造一台思考机器的尝试将极大地帮助我们“发现我们是如何思考自己的”。
然而，人工智能预测的准确性必须得到重视，它推理的优雅必须得到赞赏，它模仿我们的程度必须令人敬畏。最终，在没有人工智能的情况下，大脑将如何保持优越性？谁将验证人工智能是否更聪明？这也许是最后一个悖论。