更改

跳到导航 跳到搜索
添加10字节 、 2026年9月13日 (星期日)
第255行: 第255行:  
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>,则:
 
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 \simeq \phi_{f(n)}</math>
    
<math>n</math> 就是 <math>f</math> 的不动点 ∎<ref name="cutland1980">'''Cutland, N. J. (1980).''' ''Computability: An Introduction to Recursive Function Theory''. Cambridge University Press.【§1.9 定理 1.9 给出 totally <math>\psi</math>-introspective 程序的原始定义与存在性证明——"自省程序"概念的最早明确出处(§[[#自省程序与自省式自改进程序|5.7.7]]);§2.3 定理 2.3 给出 SRT 的"列表法"证明(§[[#列表法(Cutland 1980):把"对角线"画成一张表|5.2.2]])】</ref>.
 
<math>n</math> 就是 <math>f</math> 的不动点 ∎<ref name="cutland1980">'''Cutland, N. J. (1980).''' ''Computability: An Introduction to Recursive Function Theory''. Cambridge University Press.【§1.9 定理 1.9 给出 totally <math>\psi</math>-introspective 程序的原始定义与存在性证明——"自省程序"概念的最早明确出处(§[[#自省程序与自省式自改进程序|5.7.7]]);§2.3 定理 2.3 给出 SRT 的"列表法"证明(§[[#列表法(Cutland 1980):把"对角线"画成一张表|5.2.2]])】</ref>.
    
'''与"一行证明"的关系''':[[#一行对角线|§5.2.1]] 的证明把表上 <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.2.1]] 的证明把表上 <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) 列表法证明的视觉化。'''上半''':四行四列的"枚举之枚举"表 <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> 的不动点。|缩略图|800x800像素]]
+
[[文件:列表法证明.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 \simeq \phi_{f(n)}</math>——<math>f</math> 的不动点。|缩略图|800x800像素]]
    
=== 直观图景:程序如何"谈论"自己的代码 ===
 
=== 直观图景:程序如何"谈论"自己的代码 ===

导航菜单