第四章：可计算性与不可判定性

资源复杂度研究计算需要多少成本；可计算性首先判断满足规范的算法是否存在。不可判定性结论量化所有可终止算法，与当前硬件速度和实现技巧无关。

Decidable 与 recognizable

language $L$ 是 decidable，若存在图灵机 $M$ 对所有输入停机，且

M(x)=1\iff x\in L.

$L$ 是 Turing-recognizable，若：

$x\in L$ 时， $M$ 最终接受；
$x\notin L$ 时， $M$ 可以拒绝，也可以永不停止。

recognizer 可以枚举正例，但未必能确认负例。若 $L$ 与补集 $\overline L$ 都 recognizable，则并行模拟两个 recognizer，总有一个最终接受，因此 $L$ decidable。

Universal computation 与编码

通用机 $U$ 接收 $\langle M,x\rangle$ 并模拟 $M(x)$ 。机器描述必须是有限字符串，因此“程序作为输入”可以在同一模型内处理。

这使程序行为成为新的 decision problem，例如：

A_{\mathrm{TM}} = \{\langle M,x\rangle:M\text{ 接受 }x\}.

$A_{\mathrm{TM}}$ recognizable：直接模拟 $M(x)$ 。它不可判定，因为无法为拒绝和无限运行同时给出通用有限判断。

Halting problem

定义

\mathrm{HALT}_{\mathrm{TM}} = \{\langle M,x\rangle:M\text{ 在 }x\text{ 上停机}\}.

假设存在判定器 $H(M,x)$ 。构造程序 $D$ ：

text

D(M):
    if H(M, M) says "halts":
        loop forever
    else:
        halt

令输入为 $D$ 自身：

若 $H(D,D)$ 判断停机， $D(D)$ 按定义循环；
若判断不停机， $D(D)$ 按定义停机。

两种情况均矛盾，因此不存在 $H$ 。证明的关键不是运行时间过长，而是自引用与行为取反使任何候选判定器失败。

Diagonalization

对角化的一般结构是：枚举一族候选对象，并构造一个对象在第 $i$ 个位置与第 $i$ 个候选不同。Cantor 定理、停机问题和时间层次定理都采用这一结构。

用于计算时需要满足：

机器有有限描述，因而可枚举；
通用模型能够解释这些描述；
构造能够访问候选机在相关输入上的行为；
若要求资源界，还需支付模拟和时钟开销。

可计算性中的对角化允许无限等待；复杂度 separation 中必须在严格资源预算内完成，技术要求更高。

Mapping reduction 与不可判定性

可计算 many-one reduction 定义为存在 total computable $f$ ：

x\in A\iff f(x)\in B.

若 $A\le_m B$ 且 $B$ decidable，则 $A$ decidable。因此，为证明 $B$ 不可判定，应选择已知不可判定 $A$ 并构造 $A\le_m B$ 。

典型归约会构造一台新机器 $M'$ ，把源实例答案编码进 $M'$ 的行为。例如要证明“机器语言是否为空”不可判定，可令 $M'$ 忽略实际输入，仅模拟给定 $M(x)$ ；若模拟接受，则 $M'$ 接受某个固定字符串。

Rice theorem

Rice theorem：图灵可识别语言的任何非平凡语义性质都是不可判定的。语义性质只依赖机器识别的 language，不依赖状态数、源代码长度等语法。

“非平凡”表示至少有一台机器具有该性质，也至少有一台机器不具有。例如：

$L(M)=\varnothing$ ；
$L(M)$ 是否有限；
$M$ 是否接受某个回文串；
$L(M)$ 是否 regular。

“机器状态数是否超过 100”是可判定语法性质，不属于 Rice theorem。

Rice theorem 适合快速判断方向，但使用时仍需验证性质是 language 语义、非平凡，并明确机器类别。

不完备信息与静态分析

程序分析工具可以对受限语言、有限状态或保守近似给出结论。不可判定性不表示分析无用，而是排除同时满足以下条件的通用工具：

处理全部程序；
总是终止；
对目标语义性质既 sound 又 complete。

工程工具通常选择放弃其中一项：

abstract interpretation 保持 soundness，允许 false positive；
testing 观察有限执行，不保证覆盖；
bounded model checking 限制状态或步数；
proof assistant 要求用户提供不变量或证明。

Undecidable 与 intractable

需要区分：

undecidable：不存在对所有输入终止且正确的算法；
decidable but intractable：存在算法，但已知或猜测需要大量资源；
unknown：尚未证明属于上述哪类；
independent：相对于某公理系统无法证明或反驳某命题。

NP-complete 问题是可判定的，暴力搜索即可终止。 $\mathsf P\ne\mathsf{NP}$ 尚未证明，因此不能把 NP-hard 与不可计算混用。

本章自测

recognizer 对 no 实例可以表现为什么？
为什么 $L$ 和 $\overline L$ 都 recognizable 可以推出 $L$ decidable？
停机问题证明中的矛盾为何不依赖机器实际速度？
使用 Rice theorem 前需要检查哪三个条件？
不可判定性为何不排除 sound 但不 complete 的静态分析？

第四章：可计算性与不可判定性 ​

Decidable 与 recognizable ​

Universal computation 与编码 ​

Halting problem ​

Diagonalization ​

Mapping reduction 与不可判定性 ​

Rice theorem ​

不完备信息与静态分析 ​

Undecidable 与 intractable ​

本章自测 ​