数学|逻辑的极限与数学的困境，罗素用了362页才推导出1+1=2( 三 ) 机器

【数学|逻辑的极限与数学的困境，罗素用了362页才推导出1+1=2】停机问题
在定义了图灵机之后，图灵进一步证明了希尔伯特通用证明机制的不存在性。受到哥德尔的编号方案的启发，图灵将机器编码为数字，这样机器就可以被研究为数字，这些数字可以作为其他机器的输入。现在图灵可以提出停机问题了：有没有一种机器N ，可以决定是否有任何机器在给定的输入下停止或永远循环。图灵指出，仅仅是这种机器N的存在就会导致矛盾。

1954年， NACA“计算机”与显微镜和计算器一起工作。

图灵假设有一个特殊的机器M ，它的工作与N的工作完全相反。如果N判定一台机器在将自己作为输入时停止， M将永远循环。另一方面，如果N判定一台机器永远循环，在这种情况下M将停止。这样，你可以说M是被设计来故意破坏N的。现在的问题是：当特殊机器M将自己作为输入时，它会停机吗？

如果M在M上停止，根据M的定义， M将永远循环——矛盾
如果M在M上永远循环， M将停止——另一个矛盾

这个自我参照悖论如下所示：

停机问题。

因此， N不存在。停机问题无法解决，或者从技术上讲，它是无法确定的。
现在我们可以回到希尔伯特的判定问题。如果存在通用证明机制，我们可以通过将任何对N的查询表述为一个数学语句，使其成为N 。然而， N并不存在，通用证明机制也不存在。另一方面，如果N确实存在，我们可以用以下简单的方式实现通用证明机制：首先，编写一个程序，无限地搜索一个数学语句的所有可能的证明，找到一个就停止；接下来，我们询问N这样的搜索程序是否停止。因此，停机问题的不可解性意味着判定问题的不可解，反之亦然。
如果我们想象有N存在，我们就可以很容易地解决许多困难的或开放的数字理论问题。例如，我们可以证明哥德巴赫猜想，即每个大于2的偶数都是两个质数的和。我们可以简单地编写一个程序来遍历从4开始的所有偶数，并检查每个偶数是否确实是两个素数的和。然后，我们将把程序提供给N ，并询问它是否停止，从而证明猜想。事实上，这个问题还没有解决。

不要为人类理性的力量设定任何界限，而要为数学中纯粹形式主义的可能性设定界限。

换句话说，哥德尔和图灵所展示的是没有使用直觉的逻辑推理的局限性。他们实际上证实了庞加莱的观点，即逻辑虽然严谨和确定，但它只是一种演示工具，需要由直觉来辅助。
希尔伯特的形式理论是数学知识的近似值。正如宇宙的物理现实仍然是一个谜，需要物理学家去解决它，数学知识的前沿对数学家来说仍然是难以捉摸的。现在，数学家和他们的直觉又回到了游戏中。
计算机的诞生和程序员的崛起
在对停机问题的证明中，假设的机器M必须有一种方法能够运行N来破坏它。为了实现这一点，图灵创造了通用机器，它可以读取任何图灵机的编码。从外部来看，你无法分辨是通用机器还是特定的机器在工作。现代计算机是以通用机为基础的，通用机通常被描述为“强大”到可以做任何可以想象到的事情。但是，它的力量从何而来？它实际上是一个用来运行其他图灵机的空壳，这些机器肯定是由某些人编写的，不是通过逻辑推理，而是通过创造力、洞察力、判断和我们心理的许多其他方面的努力，这些努力可以统称为直觉。从这个角度来看，图灵不仅发明了计算机，而且创造了程序员的角色，他们负责利用通用机器的“表达能力”来编程。我们拥有的是几乎触及我们日常生活方方面面的万能电脑，而不是把自己锁在象牙塔里的全能逻辑机器！
想了解更多精彩内容，快来关注老胡说科学