s-m-n定理

递归论研究中一条应用极广的定理。

设为第e号图灵机所计算的n元函数。任给一个m+n元部分递归函数f(x，…，x，y，…，y)，它必定出现在函数序列

φb，φ，φ2，…(*)

之中，设e是它的一个号码：

f(x，…，xn，y，…，ym)=(x，…，x，y，…，y)。

如果把f看成关于x，…，x的n元函数(y，…，y看作参数)，那末它也必定是函数序列

中的某一个，f在(* *)中的号数自然与e，y，…，y有关。s-m-n定理是说这种关系可以是一个递归全函数。

定理(s-m-n定理)对每个m，n≥1，存在一个m+1元递归全函数(e，y1，…，ym)，使

定理中的m+1元函数(e，y，…，y)不仅存在，而且可以实际构造出计算它的图灵机。s-m-n定理是证明许多重要定理的工具。