3,094
个编辑
更改
→一行对角线
以表述 A 为例，全部证明如下：
以表述 A 为例，全部证明如下：
首先，根据[[s-m-n定理]]，对于任意的编号为<math>a</math>的二元输入可计算函数，以及任意的自然数<math>y</math>，这个二元函数都等价于一个一元可计算函数：
:<math>
:<math>
\phi_{S(a,y)}(x)=\phi_a(y,x)
\phi_{S(a,y)}\simeq\phi_a(y,\cdot)
</math>
</math>
其中，<math>S(a,y)</math>为这个对应的一元函数的编码，它在<math>x</math>上的计算效果等价于编号为<math>a</math>的二元函数在输入<math>y,x</math>上的计算效果。
其中，<math>S(a,y)</math>为这个对应的一元函数的编码，它在任意输入<math>x</math>上的计算效果等价于编号为<math>a</math>的二元函数在输入<math>y,x</math>上的计算效果（当无定义的时候，两边同时无定义）。
其次，不难知道函数 <math>\psi(S(y, y), x)</math> 是可计算的（它只是把 [[#s-m-n 定理（柯里化 / 参数特化）|§2.3]] 的[[柯里化操作]] <math>S</math> 和 <math>\psi</math> 复合起来），所以它有编号，设为 <math>e</math>。令 '''<math>f = S(e, e)</math>'''，则对任何输入 <math>x</math>：
其次，不难知道函数 <math>\psi(S(y, y), x)</math> 是可计算的（它只是把 [[#s-m-n 定理（柯里化 / 参数特化）|§2.3]] 的[[柯里化操作]] <math>S</math> 和 <math>\psi</math> 复合起来），所以它有编号，设为 <math>e</math>。令 '''<math>f = S(e, e)</math>'''，则对任何输入 <math>x</math>：
: <math>\phi_f(x) = \phi_{S(e,e)}(x) = \phi_e(e, x) = \psi(S(e,e), x) = \psi(f, x)</math> ∎
: <math>\phi_f(x) = \phi_{S(e,e)}(x) = \phi_e(e, x) = \psi(S(e,e), x) = \psi(f, x)</math> ∎
第一步是 <math>f</math> 的定义；第二步是柯里化的定义（<math>S(e,e)</math> 就是"把 <math>e</math> 的第一个输入写死为 <math>e</math>"）；第三步是 <math>e</math> 的定义；第四步再回到 <math>f</math> 的定义。'''唯一实质操作是第三步前那个自应用 <math>S(e,e)</math>：让程序 <math>e</math> 作用于自己的编号。''' 这就是[[对角线论证|对角线方法]]——与 Cantor 证明实数不可数、Gödel 构造"本句不可证"、Turing 证明停机问题不可解是同一种技术<ref name="kleene1938" /><ref name="rogers1967" />。
第一步是 <math>f</math> 的定义；第二步是s-m-n定理，即柯里化的应用（<math>S(e,e)</math> 就是"把 <math>e</math> 的第一个输入写死为 <math>e</math>"）；第三步是 <math>e</math> 的定义；第四步再回到 <math>f</math> 的定义。'''唯一实质操作是第三步前那个自应用 <math>S(e,e)</math>：让程序 <math>e</math> 作用于自己的编号。''' 这就是[[对角线论证|对角线方法]]——与 Cantor 证明实数不可数、Gödel 构造"本句不可证"、Turing 证明停机问题不可解是同一种技术，改步骤也就是构造自指<ref name="kleene1938" /><ref name="rogers1967" />。
[[文件:对角线证明.png|替代=对角线证明|缩略图|图3：第二递归定理证明的三步拆解与对角线自应用的视觉化——核心动作就是让程序 <math>e</math> 在 <math>S(e,e)</math> 里"看见自己"，从而闭合循环。]]
[[文件:对角线证明.png|替代=对角线证明|缩略图|图3：第二递归定理证明的三步拆解与对角线自应用的视觉化——核心动作就是让程序 <math>e</math> 在 <math>S(e,e)</math> 里"看见自己"，从而闭合循环。]]