图灵机停机问题

输入 − 一台图灵机和一个输入字符串 w。

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

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

现在我们将设计一个倒置停机机 (HM)' 作为 −

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

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

以下是"倒置停机机"的框图 −

此外，输入本身的机器(HM)₂的构造如下−

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

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