Automata Theory 简明教程

Turing Machine Halting Problem

Input - 图灵机和输入串 w 。

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

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

halting machine

现在，我们将设计一个 inverted halting machine (HM)’ 为 −

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

  2. 如果 H 返回 NO，则停止。

以下是“逆求解器”的框图 −

inverted halting machine

此外，构建了一台将自身作为输入的机器 (HM)2 ，如下所示 −

  1. 如果 (HM)2 在输入时停止，则无限循环。

  2. Else, halt.

在此，我们得到了一个矛盾。因此，求解问题是 undecidable 。