跳到主要内容

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 论题可有效计算 = 图灵可计算是论题,不是定理