Automata Theory 简明教程

Turing Machine Halting Problem

Input - 图灵机和输入串 w 。

Input − A Turing machine and an input string w.

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

Problem − Does the Turing machine finish computing of the string w in a finite number of steps? The answer must be either yes or no.

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

Proof − At first, we will assume that such a Turing machine exists to solve this problem and then we will show it is contradicting itself. We will call this Turing machine as a Halting machine that produces a ‘yes’ or ‘no’ in a finite amount of time. If the halting machine finishes in a finite amount of time, the output comes as ‘yes’, otherwise as ‘no’. The following is the block diagram of a Halting machine −

halting machine

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

Now we will design an inverted halting machine (HM)’ as −

  1. If H returns YES, then loop forever.

  2. If H returns NO, then halt.

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

The following is the block diagram of an ‘Inverted halting machine’ −

inverted halting machine

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

Further, a machine (HM)2 which input itself is constructed as follows −

  1. If (HM)2 halts on input, loop forever.

  2. Else, halt.

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

Here, we have got a contradiction. Hence, the halting problem is undecidable.