跳转至

可计算性理论

概述

可计算性理论研究计算的根本极限：哪些问题可以被算法解决，哪些问题本质上不可计算。这些结果揭示了数学与计算的深层联系。

1. Church-Turing论题

1.1 核心主张

Church-Turing论题：任何能被"有效计算"的函数都可以被图灵机计算。

这不是定理（无法证明），而是一个定义/假说，将直觉上的"可计算"概念与图灵机的数学定义等同。

1.2 等价计算模型

多种独立发展的计算模型被证明等价：

模型 提出者 年份
图灵机 Turing 1936
\(\lambda\)-演算 Church 1936
\(\mu\)-递归函数 Kleene 1936
Post系统 Post 1936
马尔可夫算法 Markov 1951

这些模型的等价性为Church-Turing论题提供了强有力的证据。

2. 可判定性与可识别性

2.1 基本定义

图灵可识别（recursively enumerable, RE）：存在图灵机 \(M\)，使得

\[ L(M) = \{w \mid M \text{ 在输入 } w \text{ 上接受}\} \]

\(M\) 可能对不属于 \(L\) 的输入永不停机。

图灵可判定（recursive, decidable）：存在图灵机 \(M\)，使得对任意输入 \(w\)：

  • \(w \in L \implies M\) 接受
  • \(w \notin L \implies M\) 拒绝

\(M\) 对所有输入都停机。

2.2 语言类的层次

graph TB
    DEC["可判定语言<br>(Decidable)"]
    RE["图灵可识别<br>(RE)"]
    coRE["co-RE"]
    ALL["所有语言"]
    DEC --> RE --> ALL
    DEC --> coRE --> ALL

关键定理：\(L\) 是可判定的 \(\iff\) \(L\) 和 \(\overline{L}\) 都是图灵可识别的。

3. 停机问题

3.1 问题定义

停机问题 \(HALT\)：

\[ HALT = \{\langle M, w \rangle \mid M \text{ 是图灵机且 } M \text{ 在输入 } w \text{ 上停机}\} \]

3.2 不可判定性证明（对角化）

定理：\(HALT\) 是不可判定的。

证明（反证法）：

假设存在判定器 \(H\) 使得：

\[ H(\langle M, w \rangle) = \begin{cases} \text{accept} & \text{if } M \text{ 在 } w \text{ 上停机} \\ \text{reject} & \text{if } M \text{ 在 } w \text{ 上不停机} \end{cases} \]

构造图灵机 \(D\)：

\[ D(\langle M \rangle) = \begin{cases} \text{reject} & \text{if } H(\langle M, \langle M \rangle \rangle) = \text{accept} \\ \text{循环不停} & \text{if } H(\langle M, \langle M \rangle \rangle) = \text{reject} \end{cases} \]

考虑 \(D(\langle D \rangle)\)：

  • 若 \(D\) 在 \(\langle D \rangle\) 上停机 \(\implies\) \(H\) 接受 \(\implies\) \(D\) 拒绝（停机）...循环
  • 若 \(D\) 在 \(\langle D \rangle\) 上不停机 \(\implies\) \(H\) 拒绝 \(\implies\) \(D\) 循环不停...

无论哪种情况都矛盾。因此 \(H\) 不存在。\(\square\)

对角化的思想

这个证明方法与Cantor证明实数不可数的对角化论证本质相同。\(D\) 的行为在"对角线"上与假设的 \(H\) 矛盾。

3.3 停机问题的意义

  • \(HALT\) 是图灵可识别的（模拟运行即可），但不可判定
  • \(\overline{HALT}\) 不是图灵可识别的
  • 程序验证的根本限制：不存在通用的程序终止性检查器

4. 可判定问题示例

4.1 关于DFA的可判定问题

问题 描述 可判定性
\(A_{DFA}\) DFA是否接受字符串 \(w\)？ 可判定，$O(
\(E_{DFA}\) DFA接受的语言是否为空？ 可判定，$O(
\(EQ_{DFA}\) 两个DFA是否等价？ 可判定

4.2 关于CFG的可判定问题

问题 描述 可判定性
\(A_{CFG}\) CFG是否生成字符串 \(w\)？ 可判定（CYK，\(O(n^3)\)）
\(E_{CFG}\) CFG生成的语言是否为空？ 可判定
\(EQ_{CFG}\) 两个CFG是否等价？ 不可判定

4.3 关于图灵机的不可判定问题

问题 描述
\(A_{TM}\) 图灵机是否接受字符串 \(w\)？
\(HALT_{TM}\) 图灵机是否在输入上停机？
\(E_{TM}\) 图灵机接受的语言是否为空？
\(EQ_{TM}\) 两个图灵机是否等价？

5. 归约

5.1 映射归约

定义：语言 \(A\) 映射归约到 \(B\)（记作 \(A \leq_m B\)），若存在可计算函数 \(f: \Sigma^* \to \Sigma^*\) 使得：

\[ w \in A \iff f(w) \in B \]

归约的含义：\(B\) 至少和 \(A\) 一样难。

定理：

  • 若 \(A \leq_m B\) 且 \(B\) 可判定，则 \(A\) 可判定
  • 若 \(A \leq_m B\) 且 \(A\) 不可判定，则 \(B\) 不可判定

5.2 归约示例

证明 \(E_{TM}\) 不可判定：

将 \(A_{TM}\) 归约到 \(\overline{E_{TM}}\)。

给定 \(\langle M, w \rangle\)，构造图灵机 \(M'\)：

\[ M'(x) = \begin{cases} \text{accept} & \text{if } x = w \text{ 且 } M \text{ 接受 } w \\ \text{reject} & \text{otherwise} \end{cases} \]

则：

  • \(M\) 接受 \(w \iff L(M') = \{w\} \neq \emptyset \iff \langle M' \rangle \in \overline{E_{TM}}\)
  • \(M\) 不接受 \(w \iff L(M') = \emptyset \iff \langle M' \rangle \in E_{TM}\)

因此 \(A_{TM} \leq_m \overline{E_{TM}}\)。由于 \(A_{TM}\) 不可判定，\(\overline{E_{TM}}\) 也不可判定，从而 \(E_{TM}\) 也不可判定。\(\square\)

6. Rice定理

6.1 陈述

Rice定理：图灵机所识别语言的任何非平凡性质都是不可判定的。

形式化：设 \(P\) 是图灵可识别语言的一个性质（即 RE 语言集合的子集），若 \(P\) 非平凡（\(P \neq \emptyset\) 且 \(P \neq \text{所有RE语言}\)），则：

\[ L_P = \{\langle M \rangle \mid L(M) \in P\} \]

是不可判定的。

6.2 应用

以下问题都是不可判定的（因为它们都是关于图灵机所识别语言的非平凡性质）：

  • 图灵机是否识别空语言？
  • 图灵机是否识别正则语言？
  • 图灵机是否识别有限语言？
  • 图灵机是否识别 \(\Sigma^*\)？

Rice定理的限制

Rice定理只适用于语言（输入输出行为）的性质，不适用于图灵机本身结构的性质。例如，"图灵机是否有100个状态"是可判定的（直接检查编码）。

7. 递归定理

7.1 陈述

递归定理（Kleene不动点定理）：对任意可计算函数 \(t: \Sigma^* \times \Sigma^* \to \Sigma^*\)，存在图灵机 \(R\)，使得对所有输入 \(w\)：

\[ R(w) = t(\langle R \rangle, w) \]

即图灵机可以获取自身的描述。

7.2 直觉理解

递归定理说明自引用是可计算的：

  • 程序可以打印自身源代码（Quine）
  • 这为停机问题的另一种证明提供了工具
  • 计算机病毒的自复制机制的理论基础

7.3 应用：停机问题的另一证明

假设 \(H\) 判定 \(HALT\)。构造图灵机 \(B\)：

\(B\) 在输入 \(w\) 上：

  1. 通过递归定理获取自身描述 \(\langle B \rangle\)
  2. 运行 \(H(\langle B, w \rangle)\)
  3. 若 \(H\) 说停机，则循环；若 \(H\) 说不停机，则停机

无论 \(H\) 的回答是什么，\(B\) 的实际行为总是与 \(H\) 的预测相反。矛盾。\(\square\)

8. 不可判定问题一览

graph TD
    HALT[停机问题] --> ATM[接受问题 A_TM]
    ATM --> ETM[空性问题 E_TM]
    ATM --> EQTM[等价问题 EQ_TM]
    HALT --> PCP[Post对应问题]
    PCP --> EQCFG[CFG等价性]
    HALT --> RICE[Rice定理覆盖的所有问题]
    HALT --> HILBERT[Hilbert第十问题]

经典不可判定问题：

问题 描述
停机问题 程序是否终止
Post对应问题（PCP） 字符串匹配问题
Hilbert第十问题 丢番图方程是否有解
字问题（群论） 群中两个字是否相等
莫斯科拼砖问题 是否可以铺满平面

参考资料

  • Sipser, Introduction to the Theory of Computation, Chapters 3-6
  • Hopcroft, Motwani & Ullman, Introduction to Automata Theory

相关章节：

评论 #