概念

可计算性理论

研究「什么是可计算的」：图灵机与递归函数给出计算的精确模型，停机问题的不可判定性表明存在本质不可解的问题，复杂性层级则度量求解代价。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

可计算性理论逻辑与集合论

01定义

可计算性理论研究「什么是可计算的」：图灵机与递归函数给出计算的精确数学模型，邱奇-图灵论题断言其捕捉了直觉的全部。停机问题的不可判定性表明存在本质不可解的问题。

图灵机：一切算法的数学模型

图灵机、λ-演算、递归函数三种定义殊途同归（邱奇-图灵论题）——「算法」获得了不依赖机型的数学定义。

不存在判断「程序 $P$ 在输入 $x$ 上是否停机」的通用算法——对角线论证给出证明，这是第一个严格意义的「不可解问题」。

图灵度刻画不可计算问题的相对难度；算术层级按量词复杂度分层——「不可解」本身也有精细结构。

\text{HALT}=\{(P,x):P(x)\ \text{停机}\}\ \text{不可判定}

希尔伯特 1928 年提出判定问题（Entscheidungsproblem）；邱奇 1936 年以 λ-演算、图灵以图灵机分别给出否定答案——不可判定性成为计算理论的起点。

编译器与静态分析的理论极限（完美的 bug 检测不可能）、程序验证的可判定片段选取、人工智能的能力边界讨论都以可计算性理论为参照。

图灵机：二进制计数器逐步执行：读写头移动、状态转移、纸带改写

步数6