图灵机停机问题

输入- 图灵机和输入字符串w。

问题- 图灵机是否能在有限步数内完成字符串w的计算？答案必须是肯定或否定。

证明- 首先，我们假设存在这样的图灵机来解决这个问题，然后我们将证明它是自相矛盾的。我们将这种图灵机称为停机机，它在有限的时间内产生“是”或“否”。如果停止的机器在有限时间内完成，则输出为“是”，否则为“否”。以下是停止机的框图 -

现在我们将设计一个倒立停机机（HM）'：

• 如果H返回 YES，则永远循环。

• 如果H返回 NO，则停止。

以下是“倒立停机机”的框图 -

此外，输入本身的机器（HM）₂的构造如下 -

• 如果 (HM) ₂在输入时停止，则永远循环。
• 否则，停下来。

在这里，我们遇到了一个矛盾。因此，停止问题是不可判定的。