问题解决：停机问题

停机问题

在现代计算的早期，一位名叫艾伦·图灵的英国学者提出了停机问题。这个问题与我们是否能够确定一个程序最终会停止运行还是永远运行有关，例如

console.writeline("hello")

将写入屏幕，然后停止。但是，看一下

dim x as integer = 9
while x > 8
  console.writeline("hello")
end while

这将永远不会结束，它永远不会停止，因为 x 始终大于 8，并且永远不会变小。这意味着 while 循环将永远持续下去，不断地打印出“hello”。在这两个所示示例中，很容易判断程序是否会停止，但并非所有程序都如此容易。想象一下，我们得到了一段更复杂的代码

dim x as integer = 9
dim total as integer = 0
while total < 100
  total = total + x
  x = x / 2
end while

这更难，但仍然可以通过更多思考和处理器上的更多时间来解决。我们可能会得到一段需要数周、数年甚至数千年才能完成的代码。但我们如何知道所有程序都会结束还是不会结束？为了确定程序是否停止，我们

• 运行一个程序，输入一个给定的输入，如果它停止，我们就知道它停止了
• 但如果它在合理的时间范围内持续运行，我们不能断定它会永远循环（也许我们还需要再等一段时间……）

我们当然可以创建一个数学证明来确定代码是否会结束，我听到你说。那么让我们证明恰好相反

停机解决方案 H 接受一个输入程序 A 和一组输入 X，然后它确定该程序是否会完成执行或不会。

您可以用程序 A 的副本替换输入 X。由于程序 A 是由代码组成的，因此可以将其转换为 1 和 0，从而为 H 提供数据输入。

让我们创建一个程序 K，如果 H 的结果是停止，它将永远循环，如果 H 的结果是永远循环，它将停止。

function K(i):
    if H(i,i) = halt then
        loop forever
    else
        halt

如果 H 说停止，K 将循环。如果 H 说循环，K 将停止，因此停机解决方案 H 将是不可判定的

因此，我们可以看到，存在诸如 K 之类的程序示例，我们无法确定它们是否会永远停止。

• 了解更多关于停机问题的信息