1 / 4概念
Computability
可计算性回答的是“是否存在一个对所有输入都停机的程序”。它不关心程序跑多久,而关心能不能保证给出答案;判断标准不是“这个问题看起来很难”,而是能否写出判定器、能否从已知不可判定问题归约过来。
1 概念
1.1 一句话定义
可计算性研究哪些函数/语言能被图灵机计算。一个问题可判定,当且仅当存在一个图灵机,对每个输入都在有限步内停机并输出是/否;可识别只要求对“是”的输入最终停机接受,对“否”的输入可以不停机。
1.2 它解决什么问题
- 停止无效搜索:当一个问题被证明不可判定时,不要再找“更聪明的算法”,而要改需求、加限制或接受近似。
- 给工具划边界:静态分析、类型检查、程序验证必须限制语言或性质,否则会撞上不可判定。
- 区分“难”和“不可能”:指数时间仍是可判定;不可判定是连“最终给答案”都做不到。
- 设计归约:把一个已知不可判定问题映射到新问题,快速证明新问题也不可判定。
没有可计算性,团队会把“目前没找到算法”误当成“还没有人优化”,在不可判定问题上无限投入。
1.3 不属于本页的内容
| 主题 | 去哪 |
|---|---|
| DFA/NFA、CFG、PDA、泵引理 | Automata & Formal Languages |
| P/NP、NP 完全性、近似算法 | Computational Complexity |
| 具体程序的性能优化 | Complexity Analysis |
| 形式化验证工具的使用 | 形式化方法页面(待补) |
| 停机问题的工程近似与超时 | 运行时/可观测性相关页面 |
1.4 关键术语
| 术语 | 含义 | 容易混淆的点 |
|---|---|---|
| 图灵机 | 有限状态 + 可读写纸带的计算模型 | 不是“物理机器” |
| 格局 | 当前状态、纸带内容、读写头位置 | 不是程序计数器 |
| 可判定 | 对每个输入都停机并给出是/否 | 不是“能算但很慢” |
| 可识别 | 对“是”的输入最终接受 | 对“否”的输入可能不停 |
| 补可识别 | 补集可识别 | 与可判定差一个“两边都停” |
| 归约 | 把问题 A 的实例映射成问题 B 的实例 | 方向决定结论 |
| 多一归约 | 每个实例映射成一个实例,答案保持 | 不是“调用 B 的算法” |
| 对角化 | 用程序枚举构造一个“反例” | 不是普通反证 |
| Rice 定理 | 非平凡语义性质不可判定 | 不覆盖语法性质 |
| Church-Turing 论题 | 可有效计算 = 图灵可计算 | 是论题,不是定理 |
2 机制
2.1 心智模型
把图灵机想成“有限状态机 + 一条无限纸带”。可判定是“两边都保证停”:是就接受,否就拒绝;可识别是“只保证是的这边停”:否可能永远跑。若一个语言和它的补都可识别,就能并行跑两个识别器,谁先停就采纳谁,于是变成可判定。
2.2 机制拆解
- 图灵机:七元组
(Q, Σ, Γ, δ, q₀, q_accept, q_reject);δ 读当前符号,改写、移动读写头、换状态。纸带无限长,格局是“状态 + 纸带 + 头位置”的快照。 - Church-Turing 论题:lambda 演算、递归函数、RAM、细胞自动机等模型与图灵机等价;“可有效计算”就是“图灵可计算”。它是论题,不是可证明的定理。
- 停机问题:假设存在判定器
H(P, I)判断程序 P 在输入 I 上是否停机;构造D(P):若H(P, P)为真就死循环,否则停机。把 D 作用于自身得到矛盾,所以 H 不存在。 - 归约:
A ≤_m B表示存在可计算映射 f,使x ∈ A ⇔ f(x) ∈ B。若 B 可判定,则 A 可判定;若 A 不可判定且A ≤_m B,则 B 不可判定。 - Rice 定理:对部分可计算函数的任意非平凡语义性质(有的函数满足、有的不满足),判断“程序是否具有该性质”都不可判定。它不管语法怎么写,只看程序行为。
- 可识别与补可识别:停机问题是可识别的(模拟执行,停机就接受),但不可判定;其补集不可识别。一个语言可判定,当且仅当它和补集都可识别。
- 不可判定问题族:停机、空纸带停机、程序等价、CFG 等价、CFG 歧义、PCP、希尔伯特第十问题、群的字问题等。
2.3 完整枚举
| 问题 | 对象 | 可判定 | 可识别 | 典型证明工具 |
|---|---|---|---|---|
| DFA 成员 | 自动机 + 串 | 是 | 是 | 直接模拟 |
| CFG 成员 | 文法 + 串 | 是 | 是 | CYK / Earley |
| 图灵机停机 | 程序 + 输入 | 否 | 是 | 对角化 |
| 空纸带停机 | 程序 | 否 | 是 | 从停机问题归约 |
| 图灵机空语言 | 程序 | 否 | 否(补可识别) | 从停机问题归约 |
| 图灵机等价 | 两个程序 | 否 | 否 | 归约 + 补集论证 |
| 程序是否输出 42 | 程序 | 否 | 是 | Rice 定理/归约 |
| PCP | 多米诺骨牌集合 | 否 | 是 | 从停机问题归约 |
| CFG 等价 | 两个文法 | 否 | 否(补可识别) | 文法/自动机归约 |
| 希尔伯特第十问题 | 整系数方程 | 否 | 是 | Matiyasevich 定理 |
| 有限表示群的字问题 | 群表示 + 字 | 否 | 是 | Novikov-Boone 定理 |
补充:可判定问题对补封闭;可识别问题对并、交封闭,对补不一定;可判定 = 可识别 ∩ 补可识别。
2.4 关键数字与边界结果
| 结果 | 量级/含义 | 说明 |
|---|---|---|
| 停机问题 | 不可判定 | 不是“很难”,而是不存在判定器 |
| 可识别语言 | 枚举器可枚举 | 与图灵机接受的语言等价 |
| 可判定语言 | 递归语言 | 存在对所有输入都停机的判定器 |
| 忙 Beaver Σ(n) | 增长快于任何可计算函数 | 不可计算,常用于不可判定性证明 |
| PCP | 不可判定 | 字符串匹配/病毒检测类问题的源头 |
| Rice 定理 | 覆盖所有非平凡语义性质 | 语法限制可以绕开,语义性质不行 |
3 实践
3.1 最小示例
# 停机问题的对角化证明骨架。
ASSUME H(P, I): returns true iff program P halts on input I
D(P):
if H(P, P) == true: LOOP_FOREVER
else: HALT
# 把 D 作用于自身:
# 若 D(D) 停机,则 H(D,D)=true,于是 D(D) 死循环;
# 若 D(D) 死循环,则 H(D,D)=false,于是 D(D) 停机。矛盾。
# 归约:HALT(M,w) <= BLANK_HALT(N)
# 构造 N:忽略自己的输入 x,模拟 M 在 w 上运行;M 停则 N 停。
N(x):
IGNORE(x)
RUN(M, w)
HALT
# 因此:M 在 w 上停机 <=> N 在空纸带上停机。
# 若 BLANK_HALT 可判定,则 HALT 可判定;HALT 不可判定,所以 BLANK_HALT 不可判定。
3.2 常用操作与解法
| 目标 | 做法 | 注意 |
|---|---|---|
| 证明可判定 | 构造一个对所有输入都停机的判定器 | 不能只写“模拟”,要证明会停 |
| 证明可识别 | 构造识别器:是则接受,否则可不停 | 不要声称否也会停 |
| 证明不可判定 | 从已知不可判定问题归约到目标 | 方向不能反 |
| 证明不可识别 | 证明补集不可识别,或用 Rice/归约 | 需要额外论证 |
| 证明非平凡语义性质 | Rice 定理 | 先确认性质是语义且非平凡 |
| 证明受限版本可判定 | 给语言/结构加限制,构造判定器 | 限制必须真的排除通用性 |
3.3 标准流程
- 把问题写成语言:输入如何编码,什么算“是”。
- 先判断是否已有判定器;不要一上来就归约。
- 若怀疑不可判定,选一个已知不可判定问题 A,构造
A ≤_m B。 - 证明映射可计算、答案保持;检查方向和限制条件。
- 若要证不可识别,补集论证或选择合适归约;不要只证“不可判定”。
- 写清“停机/不停机”的语义,避免把“没有找到算法”当成“不可判定”。
3.4 与相邻技术的组合
- 自动机:正则/CFL 的成员问题可判定,是“可判定侧”的基准。
- 计算复杂性:可判定问题再按资源分 P/NP;不可判定问题不进入 P/NP 讨论。
- 静态分析:完全精确的语义分析往往不可判定,工程上用抽象解释/类型系统做保守近似。
- 形式化验证:限定状态空间或性质类别,把不可判定问题变成可判定/可半判定。
- 编译器优化:程序等价不可判定,实际优化依赖可判定的保守规则。
3.5 选型维度
| 维度 | 取值 | 影响 |
|---|---|---|
| 目标 | 找算法 / 证不可能 | 决定用构造还是归约 |
| 性质 | 语法 / 语义 | Rice 只覆盖语义 |
| 限制 | 通用 / 受限 | 受限版本可能可判定 |
| 输入编码 | 标准 / 自定义 | 归约必须可计算 |
| 证据 | 判定器 / 识别器 | 决定“是否保证停” |
3.6 决策规则
- 能写出对每个输入都停机的判定器:问题可判定,停止找不可判定证明。
- 只能写出“是则停”的识别器:问题可识别,但不一定可判定。
- 已知问题包含停机问题作为特例:优先尝试归约证明不可判定。
- 性质是程序的输入输出行为且非平凡:先试 Rice 定理。
- 性质是语法/结构(如“是否有 10 个状态”):Rice 不适用,另找归约或构造。
- 问题在实际输入上有可判定限制(有限状态、无递归、单调):先证受限版本可判定。
3.7 替代方案对比
| 方法 | 优势 | 代价 | 适用 |
|---|---|---|---|
| 构造判定器 | 直接、可执行 | 只适用于可判定问题 | 受限语言/结构 |
| 对角化 | 证明力强 | 只针对特定自指结构 | 停机、通用性质 |
| 多一归约 | 可复用已知结论 | 需要设计映射并证明 | 大多数不可判定性 |
| Rice 定理 | 一行结论 | 只覆盖语义性质 | 程序行为性质 |
| 补集/可识别论证 | 区分可识别与可判定 | 需要额外构造 | 不可识别性 |
| 复杂度归约 | 区分 P/NP | 前提是问题可判定 | NP 完全性 |
3.8 何时不该用
- 问题只是指数时间却宣称不可判定:可判定性与复杂度是两回事。
- 对语法性质套 Rice 定理:结论不成立,先检查性质是否语义。
- 归约方向反了:从目标归约到停机只能证明“目标不比停机难”,不能证明不可判定。
- 受限输入其实可判定却套通用结论:先看限制是否排除了图灵完备。
- 把“目前没有算法”当成“不存在算法”:需要证明,不是经验判断。
4 边界
4.1 典型故障
| 症状 | 根因 | 处理 |
|---|---|---|
| 归约结论不成立 | 方向写反,或映射不可计算 | 检查 A ≤_m B 的方向与可计算性 |
| Rice 定理被误用 | 性质是语法/结构,不是语义 | 改用具体归约 |
| 把可识别当成可判定 | 识别器对“否”可能不停 | 补一个补集识别器或判定器 |
| 把不可判定当成“很慢” | 混淆可计算性与复杂度 | 区分“没有判定器”与“指数时间” |
| 受限版本被忽略 | 通用结论套到有限状态/无递归场景 | 先证受限版本可判定 |
| 编码不标准导致映射失败 | 输入格式不统一 | 固定编码并证明转换可计算 |
| 对角化自指写错 | D 没有把程序文本作为输入 | 明确“程序即数据”的编码 |
| 证明“不可识别”却只证了“不可判定” | 缺少补集论证 | 补证补集也不可识别 |
4.2 反模式
| 做法 | 后果 | 替代 |
|---|---|---|
| 用“跑得慢”证明不可判定 | 逻辑不成立 | 构造归约/对角化 |
| 对所有性质都套 Rice | 语法性质被误判 | 先分类性质 |
| 只写“模拟执行”就称判定器 | 可能不停机 | 证明终止或改识别器 |
| 归约时调用目标问题的算法 | 循环论证 | 只做实例映射 |
| 忽略输入编码 | 映射不可计算 | 固定标准编码 |
4.3 可观测信号
在工程里,可计算性不直接产生指标;它体现为“分析器是否承诺终止”“类型检查是否对所有程序给出答案”“静态分析是否只能保守近似”。若一个分析工具声称对任意程序精确判定语义性质,先怀疑它偷偷限制了语言或性质。
4.4 安全 / 性能 / 一致性边界
- 正确性:不可判定性的结论依赖模型(图灵机/通用语言);受限模型可能可判定。
- 安全:恶意程序可以构造“检测器永远跑不完”的输入;沙箱要超时和资源上限,而不是承诺判定。
- 工程:静态分析只能做保守近似;把“可能”报成“一定”会制造假阳性/假阴性。
- 一致性:可判定性不随机器速度改变;换更快的机器不能让停机问题可判定。