AI停机问题

计算机科学中最有趣的非编程问题之一是研究什么问题能（以及不能）被计算。例如这个问题，“这个程序能不能完整执行？”，也就是说，判断它（程序）会不会进入死循环。对于任意一段代码，你将如何做出回答呢？你可以尝试去运行这个程序。不过假如它会运行很长时间呢？你要等待多长时间呢？

我们可以思考一下，这个问题是否存在一个通用的解决方案——一种适用于任意一段C代码的方法，它可以判断这段代码最终是否可以停止运行。

让我们假设你发现了这样一个解决程序（为明确起见以下简称为S程序，译者注）。这是一个有两个参数的程序：要判断的程序代码（为明确起见以下简称为P程序，译者注），以及它的输入。如果P程序在给定输入下执行并最终结束，则S程序返回Ture（真），如果P程序陷入无限循环，则S程序返回False（假）。我们可以把S程序命名为DOES-HALT，这个程序可以使用如下语法：
DOES-HALT(program, input)

现在，给定DOES-HALT，让我们看看它所作的事情有多酷。好的，现在任何程序不管它运行多长时间，我们都可以让它通行无阻，并且为它运行提供保护。它可以被用来证明极其复杂的，含有大量递归以及循环结构的程序是否有效。

我们也可以用DOES-HALT快速的计算一个程序是否可以通过所有的测试用例。这是一个小技巧。对于一个特定的输入来说，我们如何用DOES-HALT判断程序是否产生了一个恰当的输出呢？要知道DOES-HALT仅仅是用来判断程序是否停机的。那又怎么样，我们完全可以编写第二个程序，可以把它叫做COMPARE-OUTPUT（比较输出），它将会有三个参数：要检测的程序，程序的输入以及期待的输出，并且它不会陷入死循环。现在，我们所要做的全部事情就是运行DOES-HALT(COMPARE-OUTPUT, [program, input, expected output]) ，这样一来我们就会知道程序是否通过了测试用例，输入，和输出预期的输出。如果它停机了，好的，它通过了；否则它就没有通过。

想想看这个程序会在我们测试复杂的算法时给我们提供多大的帮助！

让我们看看接下来的情况。特别是，如果把一个程序自身当作它的输入是会发生什么，我们需要编写一个怎忙的程序来测试它呢？例如*nix（*nix，即Unix,Linux等Unix核心的操作系统，译者注）下的程序cat（cat是Linux中一个察看文件内容的命令，译者注），当运行它自己时，将会输出可执行文件的二进制内容。有些程序在把它们自己当作输入运行时，可能永远不会停下来，既然这样——那么让我们用DOES-HALT编写一端伪代码，用它来测试当一个程序把它自己作为输入参数时会发生什么好了。我们称它为SELF-HALT（意为自停机，译者注），这个程序（SELF-HALT）将会在输入程序自运行（在这里用自运行作为程序把自己作为参数运行的简单说法，译者）非停机状态时停机。

SELF-HALT(program)
{
 if(DOES-HALT(program, program))
 infinite loop
 else
 halt
}

这段代码非常清晰：如果程序在自运行时停机，则SELF-HALT进入死循环，否则SELF-HALT停机。

太漂亮了，因为我们可以用它来分辨一个用来分析其他程序的程序（例如DOES-HALT），当该程序用自己作为输入时是否会停机。

现在，如果我们用SELF-HALT来分析它自己会怎么样呢？好的，让我们来看看。如果DOES-HALT(SELF-HALT, SELF-HALT)，则SELF-HALT(SELF-HALT) 将会永远循环。因此假如SELF-HALT在运行它自己时停机了，那么它会永远循环（死循环）。

这没有道理，因此DOES-HALT(SELF-HALT, SELF-HALT)必须为False（假）。SELF-HALT(SELF-HALT)必须不停机。但是如果DOES-HALT(SELF-HALT, SELF-HALT)为假（False），SELF-HALT(SELF-HALT) 必须停机！一个悖论。

那么我们在哪儿出问题了呢？我们的SELF-HALT结构非常完美，没有任何问题。我们的依据也都完美无缺，没有任何错误。实际上，所有问题的根源都在于我们使用了DOES-HALT 这个程序。

事实是，上面的所有论证都是建立在停机问题成立的基础上的，然而停机问题仅仅是一个名词，在一般情况下我们根本无法实现它。DOES-HALT永远不会存在，假如它存在的话就会产生上述悖论——当一个程序无限循环时才会停机，并且当它停机时才会无限循环。