Decidability

---

At first, we define two types of languages (problems):

1. 图灵可识别 (Turing-recognizable)：存在某台图灵机 \(M\)，使得对每个输入串 \(w\)，若 \(w \in A\) 则 \(M\) 在有限步后接受 \(w\)；若 \(w \notin A\)，则 \(M\) 要么拒绝、要么无限循环。换言之，\(M\) “能在属于 \(A\) 的输入上说 YES，并保证停机”，但对不属于 \(A\) 的输入可能永远跑不完。

2. 可判定 (decidable / Turing-decidable)：存在一台判定器（即对所有输入都停机的图灵机），它在 \(w \in A\) 时接受、在 \(w \notin A\) 时拒绝。也就是说，它永远给出 YES/NO 且不会卡死。

后者显然比前者强：可判定语言一定是可识别的，但反之不成立。

---

Decidable problems concerning Regular Languages

For Regular Languages (by DFA/NFA/regular expression), many natural decision problems are decidable.

\(A_{\text{DFA}}\)

Define \[ A_{\text{DFA}} = \{ \langle B, w \rangle \mid B \text{ 是一个 DFA 且 } B \text{ 接受 } w \}. \]
即给定一个确定性有限自动机 \(B\) 以及一个输入串 \(w\)，问 \(w \in L(B)\) 这个问题能否被图灵机可停机地解决。

Theorem: \(A_{\text{DFA}}\) is decidable.

NoteProof

Construct a Turing Machine \(M\) that, on input \(\langle B,w\rangle\), executes:

1. Simulate DFA \(B\) on input \(w\) step by step;
2. If \(B\) accepts \(w\), then \(M\) accepts; otherwise \(M\) rejects.

In implementation, \(B\)’s encoding includes:

• its state set \(Q\)
• alphabet \(\Sigma\)
• transition function \(\delta\)
• initial state \(q_0\)
• accepting state set \(F\).

\(M\) parses this encoding, tracking “current state” and “current input position”, and progresses according to \(\delta\) until \(w\) is read, then judging based on whether it is in an accepting state.

\(A_{\text{NFA}}\)

Define \[ A_{\text{NFA}} = \{ \langle B, w \rangle \mid B \text{ 是一个 NFA 且 } B \text{ 接受 } w \}. \]
即给定一个 NFA 和一个字符串，判断该字符串是否在其语言中。

Theorem: \(A_{\text{NFA}}\) is decidable.

NoteProof

其一条标准证明是先把 NFA 通过子集构造法转化为等价的 DFA，然后调用上一小节的判定器。形式化地，设图灵机 \(N\)：

1. 把给定的 NFA \(B\) 转换为等价的 DFA \(C\)；
2. 调用前述判定 \(M\) 来判断 \(\langle C,w\rangle\) 是否在 \(A_{\text{DFA}}\)；
3. 若 \(M\) 接受，则接受；否则拒绝。

\(A_{\text{REX}}\)

Define \[ A_{\text{REX}} = \{ \langle R,w\rangle \mid R \text{ 是一个正则表达式并生成串 } w \}. \]

Theorem: \(A_{\text{REX}}\) is decidable.

NoteProof

基本思路：把正则表达式 \(R\) 转换为等价的 NFA（或 DFA），再归约到 \(A_{\text{NFA}}\) 或 \(A_{\text{DFA}}\) 的可判定性。

\(E_{\text{DFA}}\)

Define \[ E_{\text{DFA}} = \{ \langle B \rangle \mid B \text{ 是一个 DFA 且 } L(B)=\emptyset \}. \]

Theorem: \(E_{\text{DFA}}\) is decidable.

A DFA accepts some string if and only if reaching an accept state from the start state by traveling along the arrows of the DFA is possible.

NoteProof

\(T\) on \(\langle B \rangle\):

1. Mark the start state of \(B\).
2. Repeat until no new states get marked: Mark any state that has a transition coming into it from any state that is already marked.
3. If no accept state is marked, then accept; otherwise, reject.

\(EQ_{\text{DFA}}\)

Define \[ EQ_{\text{DFA}} = \{ \langle A,B \rangle \mid A \text{ 和 } B \text{ 都是 DFA 且 } L(A)=L(B) \}. \]

Theorem: \(EQ_{\text{DFA}}\) is decidable.

NoteProof

From \(A\) and \(B\) we construct a DFA \(C\) that \[ L(C) = \left( L(A) \cap \overline{L(B)} \right) \cup \left( \overline{L(A)} \cap L(B) \right) \] i.e., the symmetric difference between \(L(A)\) and \(L(B)\). Then we can use \(E_{\text{DFA}}\) to check if \(L(C)=\emptyset\).

更具体地，构造判定器 \(F\)：

\(F\) on input \(\langle A, B \rangle\):

1. 构造 DFA \(C\)，使得 \(L(C) = (L(A) \cap \overline{L(B)}) \cup (\overline{L(A)} \cap L(B))\)（对称差）。DFA 对交、并、补封闭，所以 \(C\) 可构造。
2. 在 \(\langle C \rangle\) 上运行判定 \(E_{\text{DFA}}\) 的 TM \(T\)。
3. 若 \(T\) 接受（即 \(L(C) = \emptyset\)），则 \(L(A) = L(B)\)，接受；否则拒绝。

Decidable problems concerning CFL

\(A_{\text{CFG}}\)

Define \[ A_{\text{CFG}} = \{ \langle G, w \rangle \mid G \text{ 是一个 CFG 且 } G \text{ 能生成 } w \}. \]

Theorem: \(A_{\text{CFG}}\) is decidable.

NoteProof

朴素想法是：对给定 CFG \(G\)，尝试穷举所有推导来看看 \(w\) 能否被推出。但如果 \(G\) 不能生成 \(w\)，这种穷举可能永远不会停机，因此那只给出了“识别器”而非“判定器”。

关键改进依赖 Chomsky 范式 (Chomsky Normal Form, CNF) 的两个事实：

1. 任何 CFL 都可等价地由某个处于 CNF 的 CFG 生成；
2. 若 CFG \(G\) 处于 CNF 且生成非空串 \(w\)，则 \(w\) 的任意推导长度至多是 \(2|w|-1\) 步。

算法（判定器 \(S\)）如下：

1. 把 \(G\) 转换为等价的 CNF；
2. 枚举所有长度 \(\le 2|w|-1\) 的推导（若 \(w=\varepsilon\)，特殊地只检查是否存在 \(S \to \varepsilon\)）；
3. 若发现某个推导导出正好是 \(w\)，则接受；若无，则拒绝。

因为推导长度被一个关于 \(|w|\) 的有限上界所限制，这个过程必停机，从而 \(A_{\text{CFG}}\) 可判定。

\(E_{\text{CFG}}\)

Define \[ E_{\text{CFG}} = \{ \langle G \rangle \mid G \text{ 是一个 CFG 且 } L(G)=\emptyset \}. \]

Theorem: \(E_{\text{CFG}}\) is decidable.

NoteProof

思路：不要尝试枚举所有可能串 \(w\)（因为这可能无限进行），而是自底向上标记 CFG 中“能生成某个全终结符串”的变量：

1. 先把所有终结符标记为“可生成”；
2. 反复扫描产生式 \(A \to U_1 \cdots U_k\)，如果右侧每个符号 \(U_i\) 目前都被标记为“可生成”，就把 \(A\) 标记为“可生成”；
3. 当没有新变量可标记时停止。

若此时开始符号仍未被标记为“可生成”，说明该文法生成不出任何全终结符串，即语言为空；否则语言非空。据此我们得到一个停机的判定过程。

\(EQ_{\text{CFG}}\)

Define \[ EQ_{\text{CFG}} = \{ \langle G,H \rangle \mid G,H \text{ 是 CFG 且 } L(G) = L(H) \}. \]

Theorem: \(EQ_{\text{CFG}}\) is undecidable.

NoteProof

证明 \(EQ_{\text{CFG}}\) 不可判定的一个经典方法是将其归约到已知的不可判定问题。这里我们通过归约 \(A_{TM}\) 来证明。

假设 \(EQ_{\text{CFG}}\) 是可判定的，即存在一个判定器 \(R\) 可以判定任意两个 CFG 是否生成相同的语言。

我们将构造一个判定器来判定 \(A_{TM}\)，这将导致矛盾。

构造过程：给定 \(\langle M, w \rangle\)，我们构造两个 CFG：

1. \(G_1\)：生成语言 \(\Sigma^*\)（所有串）
2. \(G_2\)：生成的语言定义如下：
   • 如果 \(M\) 在输入 \(w\) 上接受，则 \(L(G_2) = \Sigma^*\)
   • 如果 \(M\) 在输入 \(w\) 上不接受（拒绝或循环），则 \(L(G_2) = \emptyset\)

关键观察：\(L(G_1) = L(G_2)\) 当且仅当 \(M\) 在 \(w\) 上接受。

然而，实际上我们无法有效地构造出满足上述条件的 \(G_2\)，因为这需要我们首先解决 \(A_{TM}\) 问题。更严格的证明需要使用 Post 对应问题 (Post Correspondence Problem, PCP) 或其他中间问题。

结论：由于 \(A_{TM}\) 已知是不可判定的，而判定两个 CFL 是否相等至少和判定 \(A_{TM}\) 一样困难，因此 \(EQ_{\text{CFG}}\) 是不可判定的。

也就是说，给定两个 CFG，是否生成完全相同的语言，是一个比上面两个更困难的问题，已超出了图灵可判定范围。

一个重要 corollary（在讲义中给出）：每一个 CFL 本身都是可判定的语言，也就是说，CFL 的成员判定可以由某台停机的 TM 完成。

Undecidability

到目前为止我们已经看到大量“可判定”的语言。自然问题是：是否所有“合理”的判定问题都可判定？答案是否定的。讲义特别强调：存在具体而自然的计算问题，它们在理论上就是无解的，不是因为当前计算机太慢，而是因为逻辑上不存在任何总能停机给出正确答案的程序。

%%{init: {'theme':'base', 'themeVariables': {'primaryColor':'#fff','primaryBorderColor':'#333','lineColor':'#333','secondaryColor':'#fff','tertiaryColor':'#fff','background':'transparent','mainBkg':'transparent','secondBkg':'transparent','tertiaryBkg':'transparent','clusterBkg':'transparent'}}}%%
graph TD
    subgraph TR["Turing-recognizable"]
        subgraph D["Decidable"]
            subgraph CF["Context-Free"]
                subgraph R["Regular"]
                end
            end
        end
    end

\(A_{TM}\)

Define \[ A_{TM} = \{ \langle M,w \rangle \mid M \text{ 是图灵机且 } M \text{ 在输入 } w \text{ 上接受} \}. \]

Theorem: \(A_{TM}\) is undecidable.

也就是说，不存在一台通用的、对所有输入都停机的图灵机 \(H\)，它能正确回答“\(M\) 会不会接受 \(w\)”。

NoteProof 1: 流行证法

假设 \(A_{TM}\) 可判定，即存在判定器 \(H\) 使得： \[ H(\langle M,w \rangle) = \begin{cases} \text{接受} & \text{若 } M \text{ 接受 } w \\ \text{拒绝} & \text{若 } M \text{ 不接受 } w \end{cases} \]

构造新的图灵机 \(D\)：

• 输入：\(\langle M \rangle\)（某台图灵机的编码）
• 运行 \(H(\langle M, \langle M \rangle \rangle)\)
• 若 \(H\) 接受，则 \(D\) 拒绝
• 若 \(H\) 拒绝，则 \(D\) 接受

现在考虑 \(D\) 在输入 \(\langle D \rangle\) 上的行为：

• 若 \(D\) 接受 \(\langle D \rangle\)，则根据 \(D\) 的定义，\(H(\langle D, \langle D \rangle \rangle)\) 拒绝，即 \(D\) 不接受 \(\langle D \rangle\)，矛盾。
• 若 \(D\) 不接受 \(\langle D \rangle\)，则 \(H(\langle D, \langle D \rangle \rangle)\) 接受，根据 \(D\) 的定义，\(D\) 接受 \(\langle D \rangle\)，矛盾。

因此假设不成立，\(A_{TM}\) 不可判定。

The Diagonalization Method

Let \(f: A \to B\) be a function.

1. \(f\) is one-to-one if \(f(a) \neq f(a')\) whenever \(a \neq a'\).
2. \(f\) is onto if for every \(b \in B\), there exists \(a \in A\) such that \(f(a) = b\).

A and B are the same size if there is a one-to-one, onto function \(d: A \to B\).

A function that is both one-to-ont and onto is a correspondence.

injective: one-to-one

surjective: onto

bijective: one-to-one and onto

Definition: \(A\) is countable if it is either finite or has the same size as \(\mathbb{N}\).

Theorem: \(\mathbb{R}\) is not countable.

NoteProof (Cantor’s Diagonal Argument)

假设 \(\mathbb{R}\) 可数，则可以列出所有实数 \(r_1, r_2, r_3, \ldots\)。考虑区间 \([0, 1)\) 中的实数的十进制表示：

\[ \begin{aligned} r_1 &= 0.d_{11} d_{12} d_{13} \cdots \\ r_2 &= 0.d_{21} d_{22} d_{23} \cdots \\ r_3 &= 0.d_{31} d_{32} d_{33} \cdots \\ &\;\;\vdots \end{aligned} \]

构造新实数 \(x = 0.x_1 x_2 x_3 \cdots\)，其中 \(x_i \neq d_{ii}\)（例如取 \(x_i = (d_{ii} + 1) \bmod 10\)，避免 \(0\) 和 \(9\)）。

则 \(x\) 与列表中每个 \(r_i\) 都不同（至少第 \(i\) 位不同），但 \(x \in [0,1)\)，矛盾！

Q.E.D.

Corollary: Some languages are not Turing-recognizable.

NoteProof

Fix an alphabet \(\Sigma\).

1. 字母表 \(\Sigma\) 上的所有有限串 \(\Sigma^\*\) 是可数的。
2. 任何图灵机的完整描述（即其“程序”）都可以编码成某个有限串 \(\langle M\rangle\)，因此“所有图灵机的集合”也是可数的。
3. 但 \(\Sigma\) 上“所有语言”的集合其实是 \(\mathcal{P}(\Sigma^\*)\)，这是不可数的。

因此，绝大多数语言（以基数意义而言）根本不可能被任何图灵机识别。

直接推论：存在一些语言甚至不是图灵可识别的（即没有任何 TM 会在这些语言的成员上必定停机并接受它们）。这比“不可判定”更强：那些语言甚至连半判定器都没有。

Theorem: \(A_{TM}\) is undecidable.

NoteProof 2: 对角线法

Assume \(H\) is a decider for \(A_{TM}\). That is \[ H(\langle M, w \rangle) = \begin{cases} \text{accept} & \text{if } M \text{ accepts } w \\ \text{reject} & \text{otherwise} \end{cases} \]

\(D\) on \(\langle M \rangle\):

1. Run \(H\) on input \(\langle M, \langle M \rangle \rangle\).
2. Output the opposite of what \(H\) outputs. That is, if \(H\) accepts, then reject; and if \(H\) rejects, then accept: \[ D(\langle M \rangle) = \begin{cases} \text{accept} & \text{if } H(\langle M, \langle M \rangle \rangle) = \text{reject} \\ \text{reject} & \text{otherwise} \end{cases} \]

Then \[ D(\langle D \rangle) = \begin{cases} \text{accept} & \text{if } H(\langle D, \langle D \rangle \rangle) = \text{reject} \\ \text{reject} & \text{otherwise} \end{cases} \]

So we have a table:

	\(\langle M_1 \rangle\)	\(\langle M_2 \rangle\)	…	\(\langle D \rangle\)
\(M_1\)	accept	reject	…	accept
\(M_2\)	accept(opposite)	reject	…	accept
…	…	…	…	…
\(D\)	reject(opposite)	accept(opposite)	…	???

If \(D\) is in the figure, then a contradiction occurs at ‘?’

So the assumption is false, so that there is not such a decider \(H\) and not a such table.

虽然 \(A_{TM}\) 不可判定，但它是可识别的：存在“万能图灵机” \(U\)，在输入 \(\langle M,w\rangle\) 时模拟 \(M\) 在 \(w\) 上的运行；若 \(M\) 在有限步后进入接受状态则 \(U\) 接受；若 \(M\) 进入拒绝状态则 \(U\) 拒绝。这个 \(U\) 是 1936 年由 Turing 提出的“通用图灵机”原型。

换言之，\(A_{TM}\) 是图灵可识别但不可判定。我们将在下一节看到，这意味着它的补集并不是图灵可识别的。

co-Turing-recognizable

Definition: A language is co-Turing-recognizable if its complement is Turing-recognizable.

Theorem: A language is decidable if and only if it is both Turing-recognizable and co-Turing-recognizable.

NoteProof

• 若 \(A\) 可判定，那显然 \(A\)、\(\overline{A}\) 都是图灵可识别的：直接把判定器当识别器即可。
• 反向更有趣：若 \(A\) 和 \(\overline{A}\) 都是图灵可识别的，分别由 TM \(M_1\) 和 \(M_2\) 识别，那么我们可以并行地在输入 \(w\) 上同时运行 \(M_1\) 与 \(M_2\)。
  • 如果 \(M_1\) 先接受，就判定 \(w \in A\)；
    
  • 如果 \(M_2\) 先接受，就判定 \(w \notin A\)。
    这个并行模拟构成一台真正的“判定器”，保证在有限步内给出答案。

Corollary: \(\overline{A_{TM}}\) is not Turing-recognizable.

NoteProof

假设 \(\overline{A_{TM}}\) 是图灵可识别的。

我们已经知道 \(A_{TM}\) 是图灵可识别的（由万能图灵机 \(U\) 识别）。

根据前面的定理：如果一个语言和它的补集都是图灵可识别的，那么这个语言是可判定的。

因此，如果 \(\overline{A_{TM}}\) 是图灵可识别的，那么 \(A_{TM}\) 就是可判定的。

但是我们已经证明了 \(A_{TM}\) 是不可判定的，矛盾。

所以假设不成立，\(\overline{A_{TM}}\) 不是图灵可识别的。

小结

1. “可判定” = “有一台对所有输入都停机的图灵机”。
2. 正则语言、上下文无关语言的许多基本判定问题（成员关系、空语言、等价性等）是可判定的，常靠对自动机/文法的有效有限分析。
3. 存在自然但不可判定的问题（典型是 \(A_{TM}\)，即“程序会不会接受给定输入”），其证明基于自指/对角线。
4. 由于基数论证，存在语言甚至不是图灵可识别的。
5. “可判定”正好等价于“语言本身和其补集都图灵可识别”。