Reducibility

本章我们检验一些 additional unsolvable problems, 并介绍证明 unsolvability 的 primary method: reducibility.

Reduction

A reduction is a way of converting one problem to another problem in such a way that a solution to the second problem can be used to solve the first problem.

当 \(A\) 可以被 reduce 到 \(B\) 时, 解决 \(A\) 的难度不可能大于 \(B\), 因为由 \(B\) 的 solution 可以得到 \(A\) 的 solution. 因此, 若 \(B\) 是 decidable 的, 那么 \(A\) 也是 decidable 的.

借此, 我们要证明一个问题 \(B\) 是 undecidable 的时, 只需要找到一个 undecidable 的问题 \(A\), 使得 \(A\) reduces to \(B\) 即可.

Undecidable Problems from Language Theory

Halting problem

The problems of determining whether a Turing machine halts (by accepting or rejecting) on a given input is widely known as the halting problem.

令

\[ HALT_{\textsf{TM}} = \{\langle M, w \rangle \vert M \text{ is a \textsf{TM} and } M \text{ halts on input }w\}. \]

Theorem

\(HALT_{\mathsf{TM}}\) is undecidable.

Proof

用反证法证明 \(HALT_{\mathsf{TM}}\) 是 decidable 时可以 reduces to \(A_{\mathsf{TM}}\) 也是 decidable 的从而导出矛盾.

假设存在 TM \(R\) 能 decide \(HALT_{\mathsf{TM}}\), 我们构造 TM \(S\) 使其能 decide \(A_{\mathsf{TM}}\).

\(S\) = "On input \(\langle M, w \rangle\), an encoding of a TM \(M\) and a string \(w\):

1. Run TM \(R\) on input \(\langle M, w \rangle\).
2. If \(R\) rejects, reject.
3. If \(R\) accepts, simulate \(M\) on \(w\) until it halts.
4. If \(M\) accepts, accept; if \(M\) has rejected, reject."

另一个与 TM 有关的 interesting problem 是 determine whether a given Turing machine recognizes a language that also can be recognized by a simpler computational model. 例如, 令 \(REGULAR_{\mathsf{TM}}\) 表示 determing whether a given TM has an equivalent finite automaton, 这等价于 determing whether the TM recognizes a regular language:

\[ REGULAR_{\mathsf{TM}} = \{\langle M \rangle \vert M\text{ is a \textsf{TM} and }L(M)\text{ is a regular language} \}. \]

同样的方法, 我们可以证明以下定理.

Theorem

\(E_{\mathsf{TM}}, EQ_{\mathsf{TM}}, REGULAR_{\mathsf{TM}}\) is undecidable.

Reductions via computation histories

Computation history

Let \(M\) be a Turing machine and \(w\) an input string. An accepting computation history for \(M\) on \(w\) is a sequence of configurations, \(C_{1}, C_{2}, \dots, C_{l}\), where \(C_{1}\) is the start configuration of \(M\) on \(w\), \(C_{l}\) is an accepting configuration of \(M\), and each \(C_{i}\) legally follows from \(C_{i-1}\) according to the rules of \(M\). A rejecting computation history for \(M\) on \(w\) is defined similarly, except that \(C_{l}\) is a rejecting configuration.