Reducibility

---

Undecidable Problems for Language Theory

通过将已知不可判定问题（如 \(A_{TM}\)）归约到新问题，来证明新问题也是不可判定的。核心思路：假设新问题可判定，利用其判定器构造出 \(A_{TM}\) 的判定器，导出矛盾。

\(\mathrm{HALT}_{TM}\)

\[ \mathrm{HALT}_{TM} = \{\langle M, w \rangle \mid M \text{ is a TM and } M \text{ halts on input } w\}. \]

Theorem: \(\mathrm{HALT}_{TM}\) is undecidable.

NoteProof

假设 \(R\) 判定 \(\mathrm{HALT}_{TM}\)。构造判定 \(A_{TM}\) 的 TM \(S\)：

\(S\) on input \(\langle M, w \rangle\):

1. Run \(R\) on \(\langle M, w \rangle\).
2. If \(R\) rejects, reject.（\(M\) 在 \(w\) 上不停机，自然不接受）
3. If \(R\) accepts, simulate \(M\) on \(w\) until it halts.
4. If \(M\) accepted, accept; if \(M\) rejected, reject.

\(S\) 判定 \(A_{TM}\)，矛盾。\(\square\)

直觉：用 \(\mathrm{HALT}_{TM}\) 的判定器先确认 \(M\) 会停机，这样模拟 \(M\) 就一定能结束，从而安全地获得 \(M\) 的接受/拒绝结果。

---

\(\mathrm{E}_{TM}\)

\[ \mathrm{E}_{TM} = \{\langle M \rangle \mid M \text{ is a TM and } L(M) = \varnothing\}. \]

Theorem: \(\mathrm{E}_{TM}\) is undecidable.

NoteProof

Step 1：给定 \(\langle M, w \rangle\)，构造 TM \(M_1\)：

\(M_1\) on input \(x\):

1. If \(x \ne w\), reject.
2. If \(x = w\), run \(M\) on \(w\) and accept iff \(M\) accepts.

则 \(M\) accepts \(w \iff L(M_1) \ne \varnothing\)。

Step 2：假设 \(R\) 判定 \(\mathrm{E}_{TM}\)。构造判定 \(A_{TM}\) 的 TM \(S\)：

\(S\) on input \(\langle M, w \rangle\):

1. Construct \(M_1\) from \(M\) and \(w\).
2. Run \(R\) on \(\langle M_1 \rangle\).
3. If \(R\) accepts (即 \(L(M_1) = \varnothing\)), reject; if \(R\) rejects, accept.

\(S\) 判定 \(A_{TM}\)，矛盾。\(\square\)

---

\(\mathrm{REGULAR}_{TM}\)

\[ \mathrm{REGULAR}_{TM} = \{\langle M \rangle \mid M \text{ is a TM and } L(M) \text{ is a regular language}\}. \]

Theorem: \(\mathrm{REGULAR}_{TM}\) is undecidable.

NoteProof

给定 \(\langle M, w \rangle\)，构造 TM \(M_2\)：

\(M_2\) on input \(x\):

1. If \(x\) has the form \(0^n 1^n\), accept.
2. Otherwise, run \(M\) on \(w\) and accept iff \(M\) accepts.

分析：

• 若 \(M\) accepts \(w\)：\(M_2\) 对”非 \(0^n 1^n\)“形式的输入也全部接受，故 \(L(M_2) = \Sigma^*\)（正则）。
• 若 \(M\) 不接受 \(w\)：\(M_2\) 只接受 \(\{0^n 1^n\}\)，不正则。

因此 \(M\) accepts \(w \iff L(M_2)\) is regular。

假设 \(R\) 判定 \(\mathrm{REGULAR}_{TM}\)，则 \(S\)：构造 \(M_2\)，运行 \(R(\langle M_2 \rangle)\)，同意其输出，即可判定 \(A_{TM}\)。矛盾。\(\square\)

---

\(\mathrm{EQ}_{TM}\)

\[ \mathrm{EQ}_{TM} = \{\langle M_1, M_2 \rangle \mid M_1, M_2 \text{ are TMs and } L(M_1) = L(M_2)\}. \]

Theorem: \(\mathrm{EQ}_{TM}\) is undecidable.

NoteProof

归约自 \(\mathrm{E}_{TM}\)。假设 \(R\) 判定 \(\mathrm{EQ}_{TM}\)。构造 TM \(S\) 判定 \(\mathrm{E}_{TM}\)：

\(S\) on input \(\langle M \rangle\):

1. Let \(M_1\) be a TM that rejects all inputs (so \(L(M_1) = \varnothing\)).
2. Run \(R\) on \(\langle M, M_1 \rangle\).
3. If \(R\) accepts, accept; if \(R\) rejects, reject.

则 \(L(M) = \varnothing \iff L(M) = L(M_1) \iff R\) accepts。\(S\) 判定 \(\mathrm{E}_{TM}\)，矛盾。\(\square\)

---

Reductions via Computation Histories

通过将 TM 计算过程编码为字符串（计算历史），可以利用语言理论工具来推导新的不可判定性结果。

NoteDefinition: Computation History

Let \(M\) be a TM and \(w\) an input string. An accepting computation history for \(M\) on \(w\) is a sequence of configurations \[C_1, C_2, \dots, C_\ell\] where \(C_1\) is the start configuration of \(M\) on \(w\), \(C_\ell\) is an accepting configuration, and each \(C_i\) legally follows from \(C_{i-1}\) according to the rules of \(M\).

A rejecting computation history is defined similarly, except \(C_\ell\) is a rejecting configuration.

Linear Bounded Automata (LBA)

NoteDefinition: LBA

A linear bounded automaton (LBA) is a TM whose tape head is not permitted to move off the portion of the tape containing the input. If the machine tries to move off either end, the head stays put.

\[ \mathrm{A}_{LBA} = \{\langle M, w \rangle \mid M \text{ is an LBA that accepts } w\}. \]

Theorem: \(\mathrm{A}_{LBA}\) is decidable.

NoteProof

Lemma: 一个有 \(q\) 个状态、带字母表大小为 \(g\) 的 LBA，在输入长度为 \(n\) 时恰好有 \(q \cdot n \cdot g^n\) 种不同的格局（\(q\) 种状态 \(\times\) \(n\) 个读头位置 \(\times\) \(g^n\) 种带内容）。

构造判定器 \(L\) on input \(\langle M, w \rangle\):

1. Simulate \(M\) on \(w\) for at多 \(q \cdot n \cdot g^n\) steps or until it halts.
2. If \(M\) halted and accepted, accept; if halted and rejected, reject.
3. If \(M\) has not halted within \(q \cdot n \cdot g^n\) steps, it must have repeated a configuration (鸽巢原理), hence looping — reject.

\(L\) 对所有输入都停机，因此 \(\mathrm{A}_{LBA}\) 可判定。\(\square\)

LBA 虽然格局空间是指数级的，但它是有限的。这与普通 TM 不同——普通 TM 的带可以无限延伸，格局空间无穷，所以不能简单地用有界模拟来判定 \(A_{TM}\)。

---

\(\mathrm{E}_{LBA}\) is Undecidable

\[ \mathrm{E}_{LBA} = \{\langle M \rangle \mid M \text{ is an LBA and } L(M) = \varnothing\}. \]

Theorem: \(\mathrm{E}_{LBA}\) is undecidable.

NoteProof

给定 TM \(M\) 和输入 \(w\)，构造 LBA \(B\)：

\(B\) on input \(x\):

1. 把 \(x\) 按分隔符拆成 \(C_1, \dots, C_\ell\)。
2. 检查：
   • \(C_1\) 是 \(M\) 在 \(w\) 上的起始格局；
   • 每个 \(C_{i+1}\) 合法地跟随 \(C_i\)；
   • \(C_\ell\) 是接受格局。
3. 全部满足则接受，否则拒绝。

则 \(M\) accepts \(w \iff L(B) \ne \varnothing\)。

假设 \(R\) 判定 \(\mathrm{E}_{LBA}\)。构造 \(S\) on input \(\langle M, w \rangle\)：构造 \(B\)，运行 \(R(\langle B \rangle)\)，若 \(R\) accepts（\(L(B) = \varnothing\)）则 reject；若 \(R\) rejects 则 accept。\(S\) 判定 \(A_{TM}\)，矛盾。\(\square\)

关键教训：即使模型本身的成员问题可判定（\(\mathrm{A}_{LBA}\)），其语义属性（如空性）仍可能不可判定。

---

\(\mathrm{ALL}_{CFG}\) is Undecidable

\[ \mathrm{ALL}_{CFG} = \{\langle G \rangle \mid G \text{ is a CFG and } L(G) = \Sigma^*\}. \]

Theorem: \(\mathrm{ALL}_{CFG}\) is undecidable.

NoteProof

给定 TM \(M\) 和输入 \(w\)，构造 CFG \(G\) 使得： \[ M \text{ accepts } w \iff L(G) \ne \Sigma^*. \]

即 \(G\) 生成除了 \(M\) 在 \(w\) 上的接受计算历史之外的所有字符串。

接受计算历史的格式为 \(\#C_1\#C_2\#\cdots\#C_\ell\#\)。\(G\) 生成所有满足以下至少一条的字符串：

1. 不以 \(C_1\)（起始格局）开头；
2. 不以接受格局结尾；
3. 存在某对相邻格局 \(C_i, C_{i+1}\)，\(C_i\) 不能合法转移到 \(C_{i+1}\)。

PDA 构造：先构造 PDA \(D\)，再转换为 CFG \(G\)。\(D\) 非确定性地选择检查上述三个条件之一。对第 3 条，\(D\) 猜测边界 \(C_j\)，把 \(C_i\) 压栈，再与 \(C_{i+1}\) 对比，只允许读头邻域处因转移函数而产生的差异。

反转技巧：栈弹出顺序与压入相反，因此将计算历史写成交替正反序的格局： \[\#\overrightarrow{C_1}\#\overleftarrow{C_2}\#\overrightarrow{C_3}\#\overleftarrow{C_4}\#\cdots\]

这样弹栈时恰好得到正确的比较顺序。\(\square\)

---

Mapping Reducibility

NoteDefinition: Computable Function

A function \(f : \Sigma^* \to \Sigma^*\) is computable if some TM \(M\), on every input \(w\), halts with \(f(w)\) on its tape.

NoteDefinition: Mapping Reducibility

Language \(A\) is mapping reducible to language \(B\), written \(A \le_m B\), if there exists a computable function \(f : \Sigma^* \to \Sigma^*\) such that for every \(w \in \Sigma^*\), \[w \in A \iff f(w) \in B.\] The function \(f\) is called the reduction from \(A\) to \(B\).

graph LR
    w["w"] -->|"f"| fw["f(w)"]
    subgraph langA ["Language A"]
        w
    end
    subgraph langB ["Language B"]
        fw
    end

Reductions and Decidability

Theorem: If \(A \le_m B\) and \(B\) is decidable, then \(A\) is decidable.

Corollary: If \(A \le_m B\) and \(A\) is undecidable, then \(B\) is undecidable.

NoteProof

设 \(M_B\) 判定 \(B\)，\(f\) 为 \(A\) 到 \(B\) 的归约。构造判定 \(A\) 的 TM \(N\)：

\(N\) on input \(w\):

1. Compute \(f(w)\).（\(f\) 可计算，一定停机）
2. Run \(M_B\) on \(f(w)\).
3. Output whatever \(M_B\) outputs.

正确性：\(w \in A \iff f(w) \in B \iff M_B\) accepts \(f(w)\)。\(\square\)

Reductions and Recognizability

Theorem: If \(A \le_m B\) and \(B\) is Turing-recognizable, then \(A\) is Turing-recognizable.

Corollary: If \(A \le_m B\) and \(A\) is not Turing-recognizable, then \(B\) is not Turing-recognizable.

证明类似：计算 \(f(w)\)，然后在 \(B\) 的识别器上运行。若 \(w \in A\)，则 \(f(w) \in B\)，识别器最终接受。

---

Example: \(A_{TM} \le_m \mathrm{HALT}_{TM}\)

构造归约函数 \(F\)：

\(F\) on input \(\langle M, w \rangle\):

1. Construct TM \(M'\):
   • \(M'\) on input \(x\): run \(M\) on \(x\).
   • If \(M\) accepts, accept.
   • If \(M\) rejects, enter an infinite loop.
2. Output \(\langle M', w \rangle\).

正确性：

• \(M\) accepts \(w\) \(\Rightarrow\) \(M'\) halts on \(w\)（接受） \(\Rightarrow\) \(\langle M', w \rangle \in \mathrm{HALT}_{TM}\)
• \(M\) 不接受 \(w\) \(\Rightarrow\) \(M'\) 要么无限循环（\(M\) 拒绝时），要么不停机（\(M\) 本身不停机）

因此 \(\langle M, w \rangle \in A_{TM} \iff F(\langle M, w \rangle) \in \mathrm{HALT}_{TM}\)。

---

\(\mathrm{EQ}_{TM}\) is Neither Recognizable nor co-Recognizable

Theorem: \(\mathrm{EQ}_{TM}\) is neither Turing-recognizable nor co-Turing-recognizable.

Not Turing-recognizable: \(\overline{A_{TM}} \le_m \mathrm{EQ}_{TM}\)

注意归约方向：是 \(\overline{A_{TM}} \le_m \mathrm{EQ}_{TM}\)。由于 \(\overline{A_{TM}}\) 不是图灵可识别的，\(\mathrm{EQ}_{TM}\) 也不是。

NoteProof

构造归约函数 \(F\) on input \(\langle M, w \rangle\):

1. 构造 \(M_1\)：对所有输入都拒绝（\(L(M_1) = \varnothing\)）。
2. 构造 \(M_2\)：对输入 \(x\)，忽略 \(x\)，模拟 \(M\) 在 \(w\) 上运行。若 \(M\) 接受 \(w\)，则 \(M_2\) 接受。
3. 输出 \(\langle M_1, M_2 \rangle\)。

正确性：

• \(M\) 接受 \(w\) → \(L(M_2) = \Sigma^*\), \(L(M_1) = \varnothing\), 故 \(\langle M_1, M_2 \rangle \notin \mathrm{EQ}_{TM}\)
• \(M\) 不接受 \(w\) → \(L(M_2) = \varnothing = L(M_1)\), 故 \(\langle M_1, M_2 \rangle \in \mathrm{EQ}_{TM}\)

因此 \(\langle M, w \rangle \in \overline{A_{TM}} \iff \langle M_1, M_2 \rangle \in \mathrm{EQ}_{TM}\)。\(\square\)

Not co-Turing-recognizable: \(\overline{A_{TM}} \le_m \overline{\mathrm{EQ}_{TM}}\)

NoteProof

构造归约函数 \(G\) on input \(\langle M, w \rangle\):

1. 构造 \(M_1\)：对所有输入都接受（\(L(M_1) = \Sigma^*\)）。
2. 构造 \(M_2\)：对输入 \(x\)，忽略 \(x\)，模拟 \(M\) 在 \(w\) 上运行。若 \(M\) 接受 \(w\)，则 \(M_2\) 接受。
3. 输出 \(\langle M_1, M_2 \rangle\)。

正确性：

• \(M\) 接受 \(w\) → \(L(M_2) = \Sigma^* = L(M_1)\), 故 \(\langle M_1, M_2 \rangle \in \mathrm{EQ}_{TM}\)
• \(M\) 不接受 \(w\) → \(L(M_2) = \varnothing \ne \Sigma^* = L(M_1)\), 故 \(\langle M_1, M_2 \rangle \notin \mathrm{EQ}_{TM}\)

因此 \(\langle M, w \rangle \in \overline{A_{TM}} \iff \langle M_1, M_2 \rangle \in \overline{\mathrm{EQ}_{TM}}\)。

由于 \(\overline{A_{TM}}\) 不是图灵可识别的，\(\overline{\mathrm{EQ}_{TM}}\) 也不是，即 \(\mathrm{EQ}_{TM}\) 不是 co-Turing-recognizable。\(\square\)

---

Rice’s Theorem

Theorem (Rice’s Theorem): Let \(P\) be any nontrivial property of Turing-recognizable languages. Then the problem of deciding whether the language of a given TM has property \(P\) is undecidable.

“Nontrivial” means: there exists some TM \(M_1\) with \(L(M_1)\) satisfying \(P\), and some \(M_2\) with \(L(M_2)\) not satisfying \(P\).

NoteProof

Assume WLOG that \(\varnothing\) does not satisfy \(P\) (otherwise consider \(\overline{P}\)).

Let \(T\) be a TM with \(L(T)\) satisfying \(P\) (exists by nontriviality).

Suppose \(R_P\) decides the language \(\{\ \langle M \rangle \mid L(M) \text{ has property } P \}\). We build a decider for \(A_{TM}\):

\(S\) on input \(\langle M, w \rangle\):

1. Construct TM \(M_w\): on input \(x\), first simulate \(M\) on \(w\). If \(M\) accepts \(w\), then simulate \(T\) on \(x\) and output \(T\)’s result.
2. Run \(R_P\) on \(\langle M_w \rangle\).
3. If \(R_P\) accepts, accept; if \(R_P\) rejects, reject.

正确性：

• 若 \(M\) 接受 \(w\)：\(M_w\) 模拟 \(T\)，故 \(L(M_w) = L(T)\)，满足 \(P\)，\(R_P\) 接受
• 若 \(M\) 不接受 \(w\)：\(M_w\) 不接受任何输入，\(L(M_w) = \varnothing\)，不满足 \(P\)，\(R_P\) 拒绝

因此 \(S\) 判定 \(A_{TM}\)，矛盾。Q.E.D.

Rice’s Theorem 是 \(\mathrm{REGULAR}_{TM}\)、\(\mathrm{E}_{TM}\) 等不可判定性的统一推广：任何关于 TM 语言（而非 TM 本身）的非平凡语义性质都是不可判定的。

graph LR
    ATM["A_TM"] -->|"≤m"| HALTTM["HALT_TM"]
    ATM -->|"≤m"| ETM["E_TM"]
    ATM -->|"≤m"| REGTM["REGULAR_TM"]
    ATM -->|"≤m"| EQTM["EQ_TM"]
    RICE["Rice's Theorem"] -.->|"generalizes"| REGTM
    RICE -.->|"generalizes"| ETM