图灵停机问题

本文最后更新于：4 个月前

前言

这个问题来自于我前两天看的一个视频【计算机科学速成课】 P15阿兰·图灵一节。小姐姐把问题阐述的很清楚，但即使有动画图解我仍然无法理解证明方法。以下给出我在知乎上看到一个答主给的总结。

给定图灵机描述和输入，是否有算法可以确定机器会永远计算下去（死循环）还是会到某一时刻停机？

一个例子就是如果我写了一个程序，是否可以通过某一程序事先确定我写的程序是会陷入死循环还是能够正常结束？

答案是否定的，以下是反证法的证明。

为了沟通方便，事先约定如下：

设一个程序为P，运行时需要传入一个参数，若要运行它，则这么表示：

P(参数)

而如果想强调这一程序的代码本身，则记为：

[P]

停机自动判定程序记作H，它应该有两个参数。参数1：待判定程序P；参数2：运行P程序时的传入参数。（对于某个需要参数的程序P，不能单纯地说它会不会停机。有可能传入101时会停机，而传入42后又陷入死循环了，所以传入参数不能省略。）

所以，以下给出H的使用范例：

如果P(42)会死循环不停机，那么H([P], 42)返回false；

如果P("apple")会停机，那么H([P], "apple")返回true。

图灵首先定义了一个跟H对着干的程序U，代码如下：

定义程序 U(参数)
{
    if (H(参数, 参数) == true) {
        while (true) {} //死循环
    }
    else {
        return true;
    }
}

简略解释以下，如果停机自动判定程序H返回true，那么就让程序U陷入死循环；如果H返回false，那就返回true。

那么如果将U的代码数据传入U中，那么就变成了：

定义程序 U([U])
{
    if (H([U], [U]) == true) {
        while (true) {} //死循环
    }
    else {
        return true;
    }
}

① H([U], [U])返回true意味着，停机自动判定程序H认为U([U])这个程序能够正常停机。但如果程序U([U])进入了当前的if分支则会陷入死循环而无法正常停机，矛盾！

② H([U], [U])返回false意味着，停机自动判定程序H认为U([U])这个程序会陷入死循环。同理，如果程序U([U])进入了当前的else分支则会返回true正常停机，再次矛盾！

双重矛盾表明，“停机自动判定程序H”根本不存在。

停机问题的反证法很巧妙，精髓在于想出来U(参数)和H(参数, 参数)的互相转换和[U]的代入。

计算机科学

#计算机科学