3,094
个编辑
更改
跳到导航
跳到搜索
第245行：
第245行： − # 把"所有可计算函数的枚举"摆成一张表+ − + 第253行：
第253行： − # 对角线枚举<math>D</math>+ − + − + − + − # 沿 <math>D</math> 把 <math>f</math> 套进去，得到 <math>f</math> 的不动点+ − # <math>D^* = (\phi_{f(\phi_0(0))},\phi_{f(\phi_1(1))}, \phi_{f(\phi_2(2))},\ldots)</math>+ − + − # <math>\phi_\phi_m(m) = \phi_{f(\phi_m(m))}</math>+ 第284行：
第284行： − + − −
→列表法（Cutland 1980）：把"对角线"画成一张表
上面的一行证明把对角线方法压缩到了极致——好处是直接，坏处是看不出"对角线"长什么样。[[奈杰尔·卡特兰|Cutland]] 在《Computability》<ref name="cutland"/> §2.3 (Theorem 2.3) 给出过一种更直观的'''列表法'''证明，'''用一张"行 = 枚举、列 = 位置"的二维表，把"对角线"和"沿对角线的循环"都画在纸面上'''。三步走。
上面的一行证明把对角线方法压缩到了极致——好处是直接，坏处是看不出"对角线"长什么样。[[奈杰尔·卡特兰|Cutland]] 在《Computability》<ref name="cutland"/> §2.3 (Theorem 2.3) 给出过一种更直观的'''列表法'''证明，'''用一张"行 = 枚举、列 = 位置"的二维表，把"对角线"和"沿对角线的循环"都画在纸面上'''。三步走。
* 1.把"所有可计算函数的枚举"摆成一张表
按 §2.2，每个可计算部分函数都有一个编号；所有这种编号的全体记作 {<math>\phi_k</math>}。对任意"枚举函数" <math>E</math>（把一列编号映射成一列可计算函数），<math>E</math> 的第 <math>n</math> 项就是 <math>\phi_{E(n)}</math>，即"编号为 <math>E(n)</math> 的程序"。现在考虑'''所有"可计算函数的枚举"'''——它们每一个都是某个可计算函数 <math>h</math>。Cutland 把它们自身也排成一张表：用编号为 <math>k</math> 的程序 <math>\phi_k</math> 自己去枚举，得到
按 §2.2，每个可计算部分函数都有一个编号；所有这种编号的全体记作 <math>\{\phi_k\}</math>。对任意"枚举函数" <math>E</math>（把一列编号映射成一列可计算函数），<math>E</math> 的第 <math>n</math> 项就是 <math>\phi_{E(n)}</math>，即"编号为 <math>E(n)</math> 的程序"。现在考虑'''所有"可计算函数的枚举"'''——它们每一个都是某个可计算函数 <math>h</math>。Cutland 把它们自身也排成一张表：用编号为 <math>k</math> 的程序 <math>\phi_k</math> 自己去枚举，得到
: <math>E_k</math> = "以 <math>\phi_k</math> 为枚举函数的那种枚举"，即 <math>E_k</math> 的第 <math>n</math> 项 = <math>\phi_{\phi_k(n)}</math>
: <math>E_k</math> = "以 <math>\phi_k</math> 为枚举函数的那种枚举"，即 <math>E_k</math> 的第 <math>n</math> 项 = <math>\phi_{\phi_k(n)}</math>
——双重编号 <math>\phi_{\phi_k(n)}</math>。把 <math>E_0</math>、<math>E_1</math>、<math>E_2</math>、<math>\ldots</math> 并排写下来就是一张二维表（图 6 的上半部）：'''每行 <math>E_k</math> 是一个枚举'''、'''每列 <math>n</math> 是"该行第 <math>n</math> 个值"'''、'''每格是某个具体的可计算函数'''。这张表把"枚举可计算函数的所有方式"完整地、不重不漏地列了出来。
——双重编号 <math>\phi_{\phi_k(n)}</math>。把 <math>E_0</math>、<math>E_1</math>、<math>E_2</math>、<math>\ldots</math> 并排写下来就是一张二维表（图 6 的上半部）：'''每行 <math>E_k</math> 是一个枚举'''、'''每列 <math>n</math> 是"该行第 <math>n</math> 个值"'''、'''每格是某个具体的可计算函数'''。这张表把"枚举可计算函数的所有方式"完整地、不重不漏地列了出来。
* 2.对角线枚举<math>D</math>
把这张表沿'''主对角线'''的格子圈出来——它们正是
把这张表沿'''主对角线'''的格子圈出来——它们正是
: <math>D = (\phi_\phi_0(0), \phi_\phi_1(1), \phi_\phi_2(2),\ldots)</math>
: <math>D = (\phi_{\phi_0(0)}, \phi_{\phi_1(1)}, \phi_{\phi_2(2)},\ldots)</math>
<math>D</math> 仍然是一个可计算的枚举：由 <math>h(x) = \phi_x(x)</math> 给出（图 6 黄底一行的"沿主对角线"）。它满足一个关键性质：
<math>D</math> 仍然是一个可计算的枚举：由 <math>h(x) = \phi_x(x)</math> 给出（图 6 黄底一行的"沿主对角线"）。它满足一个关键性质：
: '''<math>D</math> 和每行 <math>E_k</math> 都共享一项：第 <math>(k+1)</math> 项都是 <math>\phi_\phi_k(k)</math>'''
: '''<math>D</math> 和每行 <math>E_k</math> 都共享一项：第 <math>(k+1)</math> 项都是 <math>\phi_{\phi_k(k)}</math>'''
——因为 <math>E_k</math> 的第 <math>(k+1)</math> 项 = <math>\phi_\phi_k(k)</math>，而 <math>D</math> 的第 <math>(k+1)</math> 项 = <math>\phi_\phi_k(k)</math>，两者恰好对得上（图 6 右侧红字注释）。
——因为 <math>E_k</math> 的第 <math>(k+1)</math> 项 = <math>\phi_{\phi_k(k)}</math>，而 <math>D</math> 的第 <math>(k+1)</math> 项 = <math>\phi_{\phi_k(k)}</math>，两者恰好对得上（图 6 右侧红字注释）。
* 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^*</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>：
* 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>。设 n = <math>\phi_m(m)</math>：
'''与"一行证明"的关系'''：§5.3 的证明把表上 <math>D^* = E_m</math> 的循环直接写成 <math>\psi(S(e,e), x)</math> 的柯里化形式——<math>h(x) = \phi_x(x)</math> 对应"<math>e </math>= 编号(<math>\psi(S(y,y), x)</math>)"，<math>S(e,e)</math> 就是用自应用把表上的对角线点亮；'''列表法只是把这一行在表格里完整地展开'''。两者本质相同：列表法暴露了"为什么沿对角线循环必会撞回表里"——'''每行 <math>E_k</math> 都被对角线穿一格，循环天然闭合'''。
'''与"一行证明"的关系'''：§5.3 的证明把表上 <math>D^* = E_m</math> 的循环直接写成 <math>\psi(S(e,e), x)</math> 的柯里化形式——<math>h(x) = \phi_x(x)</math> 对应"<math>e </math>= 编号(<math>\psi(S(y,y), x)</math>)"，<math>S(e,e)</math> 就是用自应用把表上的对角线点亮；'''列表法只是把这一行在表格里完整地展开'''。两者本质相同：列表法暴露了"为什么沿对角线循环必会撞回表里"——'''每行 <math>E_k</math> 都被对角线穿一格，循环天然闭合'''。
[[文件:列表法证明.png|缩略图|'''图6'''：Cutland (1980) 列表法证明的视觉化。'''上半'''：四行四列的"枚举之枚举"表 E_0, E_1, E_2, E_k，每格填 \phi_{\phi_i(j)}；主对角线（红圈）上的格子构成对角枚举 D。'''黄底 D 行'''：把对角线上的格子抽出，得到 D = (\phi_{\phi_0(0)}, \phi_{\phi_1(1)}, \phi_{\phi_2(2)}, \ldots)。'''D* 行'''：把 f 套到 D 上得到 D* = (\phi_{f(\phi_0(0))}, \phi_{f(\phi_1(1))}, \ldots)——可计算 \Rightarrow 必是某行 E_m。'''绿框'''：取 k = m 撞上 E_m，得 \phi_{\phi_m(m)} = \phi_{f(\phi_m(m))}，再设 n = \phi_m(m) 即得 \phi_n = \phi_{f(n)}——f 的不动点。]]
[[文件:列表法证明.png|缩略图|'''图6'''：Cutland (1980) 列表法证明的视觉化。'''上半'''：四行四列的"枚举之枚举"表 <math>E_0, E_1, E_2, \cdots, E_k</math>，每格填 <math>\phi_{\phi_i(j)}</math>；主对角线（红圈）上的格子构成对角枚举 <math>D</math>。'''黄底 <math>D</math> 行'''：把对角线上的格子抽出，得到 <math>D = (\phi_{\phi_0(0)}, \phi_{\phi_1(1)}, \phi_{\phi_2(2)}, \ldots)</math>。'''<math>D^*</math> 行'''：把 <math>f</math> 套到 <math>D</math> 上得到 <math>D^* = (\phi_{f(\phi_0(0))}, \phi_{f(\phi_1(1))}, \ldots)</math>——可计算 <math>\Rightarrow</math> 必是某行 <math>E_m</math>。'''绿框'''：取 <math>k = m</math> 撞上 <math>E_m</math>，得 <math>\phi_{\phi_m(m)} = \phi_{f(\phi_m(m))}</math>，再设 <math>n = \phi_m(m)</math> 即得 <math>\phi_n = \phi_{f(n)}</math>——<math>f</math> 的不动点。]]
'''图6'''：Cutland (1980) 列表法证明的视觉化。'''上半'''：四行四列的"枚举之枚举"表 <math>E_0</math>, <math>E_1</math>, <math>E_2</math>, <math>E_k</math>，每格填 <math>\phi_\phi_i(j)</math>；主对角线（红圈）上的格子构成对角枚举 <math>D</math>。'''黄底 <math>D</math> 行'''：把对角线上的格子抽出，得到 <math>D = (\phi_\phi_0(0),\phi_\phi_1(1),\phi_\phi_2(2), \ldots)</math>。*''<math>D</math>'' 行*''：把 <math>f</math> 套到 <math>D</math> 上得到 <math>D'' = (\phi_{f(\phi_0(0))},\phi_{f(\phi_1(1))},\ldots</math>)——可计算 <math>\Rightarrow </math>必是某行 <math>E_m</math>。'''绿框'''：取 <math>k = m</math> 撞上 <math>E_m</math>，得 <math>\phi_\phi_m(m) = \phi_{f(\phi_m(m))}</math>，再设 <math>n = \phi_m(m)</math> 即得 <math>\phi_n = \phi_{f(n)}</math>——<math>f</math> 的不动点。
=== 直观图景：程序如何"谈论"自己的代码 ===
=== 直观图景：程序如何"谈论"自己的代码 ===