更改

第二递归定理最直接、也最让人着迷的威力，是它'''一劳永逸地解释了"自指"现象为什么合法'''。但要先澄清一个容易混淆的关键点：这些里程碑可以从'''两个正交的维度'''来理解——

第二递归定理最直接、也最让人着迷的威力，是它'''一劳永逸地解释了"自指"现象为什么合法'''。但要先澄清一个容易混淆的关键点：这些里程碑可以从'''两个正交的维度'''来理解——

- '''结论的性质'''：是"否定性"（证否某物不存在：Cantor、Russell、Turing、Gödel），还是"肯定性"（证实自指对象存在：自复制、quine、SRT 本身）；

* '''结论的性质'''：是"否定性"（证否某物不存在：Cantor、Russell、Turing、Gödel），还是"肯定性"（证实自指对象存在：自复制、quine、SRT 本身）；

- '''结论活在哪个世界'''：纯集合论（SRT 够不着），还是程序 / 可计算世界（SRT 够得着）。

* '''结论活在哪个世界'''：纯集合论（SRT不适用），还是程序 / 可计算世界（可以用SRT）。

两个维度交叉，得到下表：

两个维度交叉，得到下表：

! '''肯定性结论'''（证实某物存在）

! '''肯定性结论'''（证实某物存在）

|-

|-

| '''纯集合论'''（SRT 够不着）

| '''纯集合论'''（SRT不适用）

| Cantor 不可数、Russell 悖论

| [[康托尔论证实数不可数]]、[[罗素悖论]]

| （无）

| （无）

|-

|-

| '''程序 / 可计算'''（SRT 够得着）

| '''程序 / 可计算'''（可以用SRT）

| '''Turing 停机、Gödel 不完备'''

| '''[[图灵停机问题]]、[[哥德尔不完备定理]]'''

| von Neumann 自复制、quine、自省程序、SRT 本身

| [[冯诺伊曼自复制自动机]]、[[quine程序]]、[[自省程序]]、SRT 本身

|}

|}

由此看清每个现象的双重身份：'''Turing 停机、Gödel 不完备'''在"风格"上是否定性自指（与 Cantor、Russell 同类），但它们活在程序世界，所以'''又能被 SRT 事后统一推出'''；Cantor、Russell 活在纯集合论世界，SRT 造不出"实数"或"集合"，只能算'''同源但独立'''。下面逐个讲清楚。

由此看清每个现象的双重身份：'''[[图灵停机问题]]、[[哥德尔不完备定理]]'''在"风格"上是否定性自指（与 [[康托尔不可数问题]]、[[罗素悖论]]同类），但它们活在程序世界，所以'''又能被 SRT 事后统一推出'''；康托尔不可数问题、罗素悖论位于纯集合论世界，SRT 造不出"实数"或"集合"，只能算'''同源但独立'''。下面逐个讲清楚。

==== Cantor 对角线论证（1891） ====

==== 康托尔对角线论证（1891） ====

'''现象'''：实数集不可数。假设每个实数都被编号 0, 1, 2, <math>\ldots</math>；定义一个新实数，令它的第 n 位小数与"编号 n 的实数"的第 n 位小数都不同。这个新实数不在原表里——矛盾。<ref name="cantor1891" />

'''现象'''：实数集不可数。假设每个实数都被编号 <math>0, 1, 2, \ldots</math>；定义一个新实数，令它的第 n 位小数与"编号 n 的实数"的第 n 位小数都不同。这个新实数不在原表里——矛盾。<ref name="cantor1891" />

'''与 SRT 的关系：同源，但独立'''。两者做了同一件事——取"第 i 个对象在第 i 个位置上的值"（对角线）：Cantor 取"第 i 个实数的第 i 位小数"，SRT 取"第 e 个程序在输入 e 上的值"<math>\phi_e(e)</math>（即证明里的 S(e, e)）。但'''方向相反'''：Cantor 取对角线后'''改动'''它，制造一个"不在表里"的对象，从而证明实数'''不可数'''；SRT 取对角线后'''固定'''它，得到一个"引用自己编号"的程序，从而证明自指程序'''存在'''。注意，SRT '''推不出''' Cantor 定理——SRT 的结论都活在"程序 / 可计算"的世界里，给不出"实数不可数"这种纯集合论命题；两者只是共享了同一个技巧。<ref name="cantor1891" /><ref name="moschovakis2010" />

'''与 SRT 的关系：同源，但独立'''。两者做了同一件事——取"第 i 个对象在第 i 个位置上的值"（对角线）：Cantor 取"第 i 个实数的第 i 位小数"，SRT 取"第 e 个程序在输入 e 上的值"<math>\phi_e(e)</math>（即证明里的 S(e, e)）。但'''方向相反'''：Cantor 取对角线后'''改动'''它，制造一个"不在表里"的对象，从而证明实数'''不可数'''；SRT 取对角线后'''固定'''它，得到一个"引用自己编号"的程序，从而证明自指程序'''存在'''。注意，SRT '''推不出''' Cantor 定理——SRT 的结论都活在"程序 / 可计算"的世界里，给不出"实数不可数"这种纯集合论命题；两者只是共享了同一个技巧。<ref name="cantor1891" /><ref name="moschovakis2010" />