上一页我们用停机问题展示了'不可判定'的含义。要严格证明存在不可判定问题,必须先有一个能包揽所有计算的模型——图灵机。

沿箭头读：圆角是配置（状态+读头位置），矩形是查表与改写

上一页我们看到图灵机按转移规则一步步改写纸带。但要证明停机问题不可判定，我们得让一台图灵机把另一台图灵机的描述当输入来读——这要求把图灵机本身变成字符串。

把图灵机的状态、符号、转移规则全部翻译成 0/1 串，让它成为一个可被读取的字符串。

上页我们把图灵机编码成了字符串；现在反过来——图灵机读入字符串，会对它做出什么'回答'？正是这种'输入-回答'的视角，把图灵机和'语言'联系了起来。

按判定能力把语言分三层：递归 ⊂ 递归可枚举 ⊂ 所有语言；中间 r.e. 减去递归的部分正是不可判定语言所在。

前几页我们把图灵机打磨成了可编码的对象。但要证明「存在机器无法判定的问题」，还需要一把利器——康托尔在研究无限集合时发明的对角线方法。它告诉我们：无限之间也有大小之分。

二维表格与对角线构造

上页用对角线方法证明了实数不可数。现在要把同样思路搬到语言上：既然图灵机可枚举，能不能也翻转一下，造一个不在列表里的语言？

对角线语言 L_d 比停机问题更极端——它连递归可枚举都不是。

上一页用对角线方法抽象地证明了不可判定语言的存在。要把这个方法用到具体问题上，需要先有通用图灵机 U。

顺着箭头看：先分别编码，再配对成通用语言的一个实例

上节我们造出了通用图灵机，理论上能模拟任何图灵机——但有个朴素问题绕不过去：能不能再往前一步，造一个机器直接告诉你「任意程序会不会停下来」？这就是停机问题。

反证法的逻辑骨架：假设→构造→矛盾→否定假设。看推导链如何自我推翻。

用对角线法构造一台图灵机，让它在「是否停机」上自打嘴巴。

我们已经分别知道 L_d 和 A_TM 都不可判定。这一页看它们之间的桥梁：归约。理解了这个，两条不可判定性结论就串成一条逻辑链。

上一页证明了停机问题不可判定，但这并非孤例——借助「归约」这把钥匙，我们可以证明一大批问题同样不可判定。这一页看两个经典例子。

不可判定问题告诉我们有些问题算法根本无法解决。但对于那些可判定的问题呢？怎么衡量「算起来有多费劲」？这就需要时间复杂性。

上一页我们用「步数」衡量计算成本。但很多问题真正烧的不是时间，而是内存——SAT 求解器搜索指数棵树时，复用同一份草稿就够了。本页把度量换成带子上消耗的格子数。

时间与空间复杂性的关系

前面我们问'算不算得出来'——停机问题给出了边界。这一页切换视角：可判定的问题之间也有天壤之别。复杂性理论关心'花多少代价'，而 P 类就是这条天梯的第一道门槛。

上一页我们讲了P类问题——多项式时间内能找到答案的问题。但现实里大量问题，找答案很难，验证答案却很容易。这就是NP类问题的核心特征。

P 与 NP 都谈“多项式”，却分别描述求解与验证；是否相等仍未知。

从最小的正则语言逐层向上到递归可枚举语言，每一层都是严格的真包含关系。

我们已经看到停机问题不可判定，也了解了 P 类、NP 类和各种复杂性类。这些边界不是工程瓶颈，而是数学结构本身决定的——理解这一点，「无算法可解」才算真正落地。

证明停机问题不可判定时，对角线论证最关键的一步是？

• ✓自指 + 对角化是制造不可判定性的通用技法
• ✓停机问题无解，不是因为难，而是因为不存在算法
• ✓语言有清晰层次：递归 ⊊ 递归可枚举 ⊊ 全体
• ✓P 与 NP 问的是效率边界，不是可计算边界
• ✓图灵机划出了计算的绝对边界

先合上屏幕自己想，再翻看参考答案。三问分别落在回顾、应用、迁移三个层次。