图灵机停机问题

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

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

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

现在我们将设计一个反向停机机 (HM)’如下：

• 如果 H 返回 YES，则无限循环。

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

以下是“反向停机机”的框图：

此外，一个输入为自身的机器 (HM)₂ 构建如下：

• 如果 (HM)₂ 在输入上停止，则无限循环。
• 否则，停止。

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