3,094
个编辑
更改
→一行对角线
以表述 A 为例，全部证明如下：
以表述 A 为例，全部证明如下：
首先，根据s-m-n定理，构造一个全可计算函数<math>S(e,y)</math>，使其满足：
首先，根据s-m-n定理，对于任意的编号为<math>a</math>的二元输入可计算函数都等价于一个一元可计算函数：
:<math>
:<math>
\phi_{S(e,y)}(x)=\phi_e(y,x)
\phi_{S(a,y)}(x)=\phi_a(y,x)
</math>
</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>：