3,094
个编辑
更改
→S-m-n 定理（柯里化 / 参数特化）
存在一台"通用机器"：给它输入 <math>(e, x)</math>，它就'''模拟'''编号 <math>e</math> 的程序在输入 <math>x</math> 上的运行。这就是今天的'''解释器 / 虚拟机'''思想，Turing 1936 年的[[通用图灵机]]是它的首个化身。用记号写就是：存在程序<math>i</math> 使得 <math>\phi_i(e, x) = \phi_e(x)</math>。<ref name="rogers1967" />
存在一台"通用机器"：给它输入 <math>(e, x)</math>，它就'''模拟'''编号 <math>e</math> 的程序在输入 <math>x</math> 上的运行。这就是今天的'''解释器 / 虚拟机'''思想，Turing 1936 年的[[通用图灵机]]是它的首个化身。用记号写就是：存在程序<math>i</math> 使得 <math>\phi_i(e, x) = \phi_e(x)</math>。<ref name="rogers1967" />
=== S-m-n 定理（柯里化 / 参数特化） ===
=== s-m-n 定理（柯里化 / 参数特化） ===
'''S-m-n 定理'''说：给定一个双输入程序和它的'''第一个输入'''，可以机械地生成一个"把第一个输入写死在程序里"的新单输入程序。用程序员的话说，就是'''柯里化（currying）或部分应用（partial application）总是可以机械完成的'''：存在可计算的全函数 S，使得
'''[[s-m-n 定理]]'''说：给定一个双输入程序和它的'''第一个输入'''，可以机械地生成一个"把第一个输入写死在程序里"的新单输入程序。用程序员的话说，就是'''柯里化（currying）或部分应用（partial application）总是可以机械完成的'''：存在可计算的全函数 <math>S</math>，使得
: <math>\phi_{S(e, y)}(x) = \phi_e(y, x)</math>
: <math>\phi_{S(e, y)}(x) = \phi_e(y, x)</math>
即"程序 <math>S(e,y)</math>"在输入 <math>x</math> 上的行为 = "程序 <math>e</math>"在输入 <math>(y, x)</math> 上的行为。Kleene 1938 年论文中的 S 函数就是这个工具<ref name="kleene1938" />。'''第二递归定理的证明只需要这一个工具'''，此外什么都不需要——这是它惊人简单的原因。
即"程序 <math>S(e,y)</math>"在输入 <math>x</math> 上的行为 = "程序 <math>e</math>"在输入 <math>(y, x)</math> 上的行为。Kleene 1938 年论文中的 <math>S</math> 函数就是这个工具<ref name="kleene1938" />。'''第二递归定理的证明只需要这一个工具'''，此外什么都不需要——这是它惊人简单的原因。
=== 递归可枚举集（r.e. set） ===
=== 递归可枚举集（r.e. set） ===