更改

==== 列表法（Cutland 1980）：把"对角线"画成一张表 ====

==== 列表法（Cutland 1980）：把"对角线"画成一张表 ====

上面的一行证明把对角线方法压缩到了极致——好处是直接，坏处是看不出"对角线"长什么样。[[奈杰尔·卡特兰|Cutland]] 在《Computability》<ref name="cutland1980"/> §2.3 (Theorem 2.3) 给出过一种更直观的列表法证明，用一张"行 = 枚举、列 = 位置"的二维表，把"对角线"和"沿对角线的循环"都画在纸面上。三步走。

上面的一行证明把对角线方法压缩到了极致——好处是直接，坏处是看不出"对角线"长什么样。[[奈杰尔·卡特兰|Cutland]] 在《Computability》<ref name="cutland1980"/> §2.3 (Theorem 2.3）中给出过一种更直观的列表法证明，用一张"行 = 枚举、列 = 位置"的二维表，把"对角线"和"沿对角线的循环"都画在纸面上。

 

* '''1. 把"所有可计算函数的枚举"摆成一张表'''

* '''1. 把"所有可计算函数的枚举"摆成一张表'''

* '''3. 沿 <math>D</math> 把 <math>f</math> 套进去，得到 <math>f</math> 的不动点'''

* '''3. 沿 <math>D</math> 把 <math>f</math> 套进去，得到 <math>f</math> 的不动点'''

设 <math>f</math> 是任意全可计算函数。沿 <math>D</math> 的每一项先用 <math>f</math> 变一下号，再去取对应的可计算函数，得到另一个枚举：

设 <math>f</math> 是任意全可计算函数。沿 <math>D</math> 的每一项先用 <math>f</math> 得到新的程序编号（源代码），再去取对应的可计算函数，得到另一个枚举：

: <math>D^* = (\phi_{f(\phi_0(0))},\phi_{f(\phi_1(1))}, \phi_{f(\phi_2(2))},\ldots)</math>

: <math>D^* = (\phi_{f(\phi_0(0))},\phi_{f(\phi_1(1))}, \phi_{f(\phi_2(2))},\ldots)</math>

<math>D^*</math> 也可计算（由 <math>f(h(x))</math> 给出）——既然 <math>D^*</math> 本身也是"枚举可计算函数"的一种方式，它必然是表里某一行 <math>E_m</math>。这正是循环闭合的地方：套用 <math>f</math> 之后，必然撞回表内。

<math>D^*</math> 也可计算（由 <math>f(h(x))</math> 给出）——既然 <math>D^*</math> 本身也是"枚举可计算函数"的一种方式，它必然是表里某一行 <math>E_m</math>。这正是循环闭合的地方：套用 <math>f</math> 之后，必然撞回表内。

取 <math>k = m：D^* =E_m</math>，所以 <math>D^*</math> 的第 <math>(m+1)</math> 项 = <math>E_m</math> 的第 <math>(m+1)</math> 项 = <math>\phi_{\phi_m(m)}</math>。而 <math>D^*</math> 的第 <math>(m+1)</math> 项由定义也是 <math>\phi_{f(\phi_m(m))}</math>：

取 <math>k = m：D^* =E_m</math>，所以 <math>D^*</math> 的第 <math>(m+1)</math> 项 = <math>E_m</math> 的第 <math>(m+1)</math> 项 = <math>\phi_{\phi_m(m)}</math>。而 <math>D^*</math> 的第 <math>(m+1)</math> 项由定义也是 <math>\phi_{f(\phi_m(m))}</math>：<math>\phi_{\phi_m(m)} = \phi_{f(\phi_m(m))}</math>'''

 

* '''4. <math>\phi_{\phi_m(m)} = \phi_{f(\phi_m(m))}</math>'''

Cutland 用 Lemma 2.1 把"第 <math>m</math> 行"调整成全的（即 <math>\phi_m</math> 是全函数），所以 <math>\phi_m(m)</math> 是一个良定的自然数 <math>n</math>。设 n = <math>\phi_m(m)</math>：

Cutland 用 Lemma 2.1 把"第 <math>m</math> 行"调整成全的（即 <math>\phi_m</math> 是全函数），所以 <math>\phi_m(m)</math> 是一个良定的自然数 <math>n</math>。设 <math>n =\phi_m(m)</math>，则：

: <math>\phi_n = \phi_{f(n)}</math>

: <math>\phi_n = \phi_{f(n)}</math>