更改

'''与 SRT 的关系：同源，但独立'''。罗素悖论也是"把谓词'不属于自身'同时用于所有集合"的对角线操作，和 SRT 共享同一个技巧，但 SRT 同样'''推不出'''它——它是朴素集合论内部的问题，不涉及程序。真正值得注意的，是 Rogers 指出的一个'''类比'''：把"集合"换成"可枚举的集合 <math>W_e</math>"、把"<math>\in</math>"换成"<math>e\in W_e</math>"，就得到 <math>K = \{e : e\notin W_e\}</math>——<math>K</math> 可枚举、其补集不可枚举。而"<math>K</math> 的补集不可枚举"恰好'''等价于停机问题不可判定'''（见 5.7.3），后者才是 SRT 真正推得出来的。换言之，"停机问题不可判定"可以看作"递归论版的罗素悖论"，但罗素悖论本身与SRT只是同源关系。<ref name="russell1908" /><ref name="rogers1967" />

'''与 SRT 的关系：同源，但独立'''。罗素悖论也是"把谓词'不属于自身'同时用于所有集合"的对角线操作，和 SRT 共享同一个技巧，但 SRT 同样'''推不出'''它——它是朴素集合论内部的问题，不涉及程序。真正值得注意的，是 Rogers 指出的一个'''类比'''：把"集合"换成"可枚举的集合 <math>W_e</math>"、把"<math>\in</math>"换成"<math>e\in W_e</math>"，就得到 <math>K = \{e : e\notin W_e\}</math>——<math>K</math> 可枚举、其补集不可枚举。而"<math>K</math> 的补集不可枚举"恰好'''等价于停机问题不可判定'''（见 5.7.3），后者才是 SRT 真正推得出来的。换言之，"停机问题不可判定"可以看作"递归论版的罗素悖论"，但罗素悖论本身与SRT只是同源关系。<ref name="russell1908" /><ref name="rogers1967" />

==== Turing 停机问题（1936） ====

==== 图灵停机问题（1936） ====

'''现象'''：不存在算法 H 能判定"任意程序 e 在任意输入 x 上是否会停机"。这是可计算性理论第一个、也是最著名的"不可判定"结果。<ref name="turing1936" />

'''现象'''：不存在算法 <math>H</math> 能判定"任意程序 <math>e</math> 在任意输入 <math>x</math> 上是否会停机"。这是可计算性理论第一个、也是最著名的"不可判定"结果。<ref name="turing1936" />

'''双重身份'''：停机不可判定在'''结论性质'''上是否定性的（证明"判定器不存在"），与 Cantor、Russell 同类；但因为它活在"程序"世界，'''又能被 SRT 推出'''。下面展示完整的"套用"过程——这是所有例子里最干净的一个，最能看清 SRT 到底在哪里发力。

'''双重身份'''：停机不可判定在'''结论性质'''上是否定性的（证明"判定器不存在"），与康托尔、罗素问题同类；但因为它活在"程序"世界，'''又能被 SRT 推出'''。下面展示完整的"套用"过程——这是所有例子里最干净的一个，最能看清 SRT 到底在哪里发力。

'''套用 SRT 造否定性自指程序的完整演示'''：

'''套用 SRT 造否定性自指程序的完整演示'''：

1. '''假设'''存在判定器 H（H(e,x)=1 表示"程序 e 在输入 x 停机"，=0 表示不停机）。

1. '''假设'''存在判定器 <math>H</math>（<math>H(e,x)=1</math> 表示"程序 <math>e</math> 在输入 <math>x</math> 停机"，<math>=0</math> 表示不停机）。

2. '''写出"想要的行为"，把"自己"写成参数 z'''：我们要一个与 H 唱反调的捣乱程序——"如果 H 说程序 z（在输入 z 上）会停机，我就死循环；如果 H 说不停机，我就立即停机"。写成可计算规则：

2. '''写出"想要的行为"，把"自己"写成参数 <math>z</math>'''：我们要一个与 <math>H</math> 唱反调的捣乱程序——"如果 <math>H</math> 说程序 <math>z</math>（在输入 <math>z</math> 上）会停机，我就死循环；如果 <math>H</math> 说不停机，我就立即停机"。写成可计算规则：

  > <math>\psi(z, x)</math> = 若 H(z, z) = 1，则'''发散'''（死循环）；若 H(z, z) = 0，则'''输出 0'''（立即停机）。

: <math>\psi(z, x) = \text{若} H(z, z) = 1，\text{则发散（死循环）；若} H(z, z) = 0，\text{则输出0（立即停机）。}</math>

3. '''套 SRT'''：存在编号 f，使 <math>\phi_f(x) = \psi(f, x)</math>。SRT 在这一步把参数 z 换成了 f 自己，循环闭合：

3. '''套 SRT'''：存在编号 f，使 <math>\phi_f(x) = \psi(f, x)</math>。SRT 在这一步把参数 z 换成了 f 自己，循环闭合：

  > <math>\phi_f(x)</math> = 若 H(f, f) = 1，则发散；若 H(f, f) = 0，则输出 0。

: <math>\phi_f(x) = \text{若} H(f, f) = 1，\text{则发散；若 }H(f, f) = 0\text{，则输出 0。}</math>

4. '''代入 x = f 制造矛盾'''：若 H(f,f)=1（H 说"f 在输入 f 停机"），但此时 <math>\phi_f(f)</math> 发散——H 判错；若 H(f,f)=0（H 说不停机），但此时 <math>\phi_f(f)=0</math> 停机——H 又判错。于是 H 无论如何都错 <math>\to </math>'''H 不存在'''。∎

4. '''代入 <math>x = f</math> 制造矛盾'''：若 <math>H(f,f)=1</math>（<math>H</math> 说"<math>f</math> 在输入 <math>f</math> 停机"），但此时 <math>\phi_f(f)</math> 发散——<math>H</math> 判错；若 <math>H(f,f)=0</math>（<math>H</math> 说不停机），但此时 <math>\phi_f(f)=0</math> 停机——<math>H</math> 又判错。于是 <math>H</math> 无论如何都错 <math>\to </math>'''<math>H</math> 不存在'''。∎

关键就在第 3 步：<math>\psi</math> 里用的是参数 z（可以正常定义），SRT 把它换成 f 自己——'''没有 SRT，"<math>\phi_f</math> 的行为取决于 H 对 f 的判决"就是非法循环定义，写不出来'''。SRT 的全部威力，就是把这种循环合法化：你只管把"自己"写成参数，存在性交给定理。<ref name="moschovakis2010" /><ref name="rogers1967" />

关键就在第 3 步：<math>\psi</math> 里用的是参数 <math>z</math>（可以正常定义），SRT 把它换成 <math>f</math> 自己——'''没有 SRT，"<math>\phi_f</math> 的行为取决于 <math>H</math> 对 <math>f</math> 的判决"就是非法循环定义，写不出来'''。SRT 的全部威力，就是把这种循环合法化：你只管把"自己"写成参数，存在性交给定理<ref name="moschovakis2010" /><ref name="rogers1967" />。

==== Gödel 第一不完备定理（1931） ====

==== Gödel 第一不完备定理（1931） ====