更改

==== Russell 悖论（1901） ====

==== Russell 悖论（1901） ====

'''现象'''：考虑 R = {x : x <math>\notin x</math>}（所有"不属于自己"的集合组成的集合）。问 R <math>\in R</math> 是否成立？若 R <math>\in R</math>，则按定义 R <math>\notin R</math>；若 R <math>\notin R</math>，则按定义 R <math>\in R</math>。两边都矛盾，这个悖论动摇了朴素集合论。<ref name="russell1908" />

'''现象'''：考虑 <math>R = \{x : x \notin x\}</math>（所有"不属于自己"的集合组成的集合）。问 <math>R\in R</math> 是否成立？若 <math>R\in R</math>，则按定义 <math>R\notin R</math>；若 <math>R\notin R</math>，则按定义 <math>R\in R</math>。两边都矛盾，这个悖论动摇了朴素集合论<ref name="russell1908" />。

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

'''与 SRT 的关系：同源，但独立'''。Russell 悖论也是"把谓词'不属于自身'同时用于所有集合"的对角线操作，和 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） ====

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