s-m-n定理

同義語：s-m-n theorem

概要

前提知識: 万能Turing機械, 計算可能関数, 原始再帰関数

2 変数の計算 $\varphi^{(2)}_e(a,y)$ で最初の引数 $a$ を固定すると、残りの $y$ についての 1 変数の計算が得られる。これも部分計算可能関数なので番号をもつ。s-m-n 定理 は、その番号を $e$ と $a$ から原始再帰関数で求められることを述べる。プログラムの言葉でいえば、「入力の前に $a$ を書き足してから $e$ を実行する」プログラムを、$e$ と $a$ から機械的に書けるということである。名前は、$m$ 個の引数を固定して $n$ 変数の計算の番号を返す関数を $s^m_n$ と書くことに由来する。
この定理は、停止問題からの還元や、計算可能性理論の Rice の定理・Kleene の再帰定理など、番号付けを使う議論で広く使われる。
この記事では、計算可能関数の記事の標準の番号付けについて、「入力の前に定数を書き込む機械」と「与えられた機械」をつないだ機械の番号が原始再帰的に求まることを示して、s-m-n 定理を証明する。

記法と前提

$\mathbb{N}=\{0,1,2,\dots\}$ とし、$\mathbb{Z}$ は整数全体とする。部分関数の値について、$\alpha\simeq\beta$ は「両辺がともに定義されないか、ともに定義されて等しい」ことを表す。機械・様相・初期様相・停止様相は Turing機械の記事の定義「様相と計算」「Turing 機械が計算する関数」に従い、入力 $\vec x$ の初期テープを $\tau_{\vec x}$ と書く。空白記号は $0$ である。
万能Turing機械の記事に従い、自然数の有限列を $\langle a_0,\dots,a_{k-1}\rangle:=\prod_{i< k}p(i)^{a_i+1}$（$p(i)$ は $i$ 番目の素数）で符号化し、$\operatorname{lh}(c)$、$(c)_i$ をその記事の定義「番号から決まる機械」のとおりに定める。番号 $e$ の機械を $M_e$、その初期状態は $(e)_0$、命令は $(e)_j$（$1\le j<\operatorname{lh}(e)$）である。$M_e$ が入力 $x$ から停止し、ヘッドから右へ $1^y$ が書かれてほかが空白のときの $y$ を $\operatorname{out}_{M_e}(x)$ と書き、万能関数は $u(e,x):\simeq\operatorname{out}_{M_e}(x)$ である（同記事の定義「出力関数と万能関数」）。
番号付けは計算可能関数の記事の定義「標準の番号付け」に従う。
$$ \varphi_e(x):\simeq u(e,x),\qquad\varphi^{(k)}_e(x_1,\dots,x_k):\simeq\varphi_e(\langle x_1,\dots,x_k\rangle). $$
遷移の規則． 番号 $e$ と自然数 $q,a$ に対し、$(e)_j$ の成分で $((e)_j)_0=q$、$((e)_j)_1=a$ となる $j$（$1\le j<\operatorname{lh}(e)$）のうち最小のものがあれば、万能Turing機械の記事の定義「番号から決まる機械」の 2 の値を $\delta_e(q,a)$ とし、なければ $\delta_e(q,a)$ は定義しない。$q,a$ が $M_e$ の状態とテープ記号なら、これは $M_e$ の遷移関数である。
平行移動． テープの内容 $\tau$ と $d\in\mathbb{Z}$ に対し、$(T_d\tau)(i):=\tau(i-d)$ とおく。様相 $C=(q,\tau,h)$ と $K\in\mathbb{N}$ に対し $C^{K,d}:=(q+K,\ T_d\tau,\ h+d)$ と書く。
(A) 計算のモデルの一致． Turing 計算可能な部分関数の全体と μ再帰関数の全体は、変数の個数ごとに一致する（Gal15 §7.7.1、p. 355。この記事では証明しない）。主定理の証明で使うのは、原始再帰関数が Turing 計算可能であること（Bil03 Theorem 13.4、p. 89 にもある）だけである。帰結と例では、μ再帰関数が部分計算可能であることと、部分計算可能関数が合成で閉じていることも使う。

定義

番号をつなぐ操作

列の符号 $c,d$ に対し、$c$ の後ろに $d$ の項を並べた列の符号を
$$ c\frown d:=c\cdot\prod_{i<\operatorname{lh}(d)}p\bigl(\operatorname{lh}(c)+i\bigr)^{(d)_i+1} $$
とおく。$c=\langle a_0,\dots,a_{k-1}\rangle$、$d=\langle b_0,\dots,b_{l-1}\rangle$ なら $c\frown d=\langle a_0,\dots,a_{k-1},b_0,\dots,b_{l-1}\rangle$ である。

状態をずらした命令の列と、番号の連結

$K\in\mathbb{N}$ と自然数 $t$ に対し $\operatorname{sh}_K(t):=\langle(t)_0+K,\ (t)_1,\ (t)_2+K,\ (t)_3,\ (t)_4\rangle$ とおき、番号 $e$ に対し
$$ \operatorname{sl}(e,K):=\prod_{i<\operatorname{lh}(e)\dot-1}p(i)^{\operatorname{sh}_K((e)_{i+1})+1} $$
とおく。これは $M_e$ の命令の状態の成分に $K$ を足した命令を、同じ順に並べた列の符号である。
自然数 $p,H,K,e$ に対し、$p$ と $e$ の連結を
$$ \operatorname{join}(p,H,K,e):=\Bigl(p\frown\bigl\langle\langle H,0,(e)_0+K,0,2\rangle,\ \langle H,1,(e)_0+K,1,2\rangle\bigr\rangle\Bigr)\frown\operatorname{sl}(e,K) $$
と定める。後ろの 2 つの命令を つなぎの命令 という。

$\operatorname{join}(p,H,K,e)$ の機械は、状態 $H$ で $0$ か $1$ を読むと、テープを変えずに $M_e$ の初期状態を $K$ ずらした状態へ移る。

定数を書き込む機械

前置きの機械

$a\in\mathbb{N}$ に対し、次の $a+5$ 項の列の符号を $w(a)$ とおく。
$$ w(a):=\bigl\langle 0,\ \langle0,0,1,0,0\rangle,\ \langle0,1,1,1,0\rangle,\ \langle1,0,2,0,0\rangle,\ \iota_2,\ \dots,\ \iota_{a+1},\ \langle a+2,0,a+3,0,1\rangle\bigr\rangle, $$
ここで $\iota_i:=\langle i,0,i+1,1,0\rangle$（$2\le i\le a+1$。$a=0$ なら $\iota$ はない）である。$M_{w(a)}$ を 前置きの機械 という。

$M_{w(a)}$ は入力 $1^c$ の前に「$1^a$ と空白 1 マス」を書き足し、その左端で止まる（lem-smn-prefix）。

例

定数 1 を前置きする機械の動き

$a=1$ のとき $w(1)=\langle0,\langle0,0,1,0,0\rangle,\langle0,1,1,1,0\rangle,\langle1,0,2,0,0\rangle,\langle2,0,3,1,0\rangle,\langle3,0,4,0,1\rangle\rangle$ である。入力 $c=2$ での動きを追う。

ステップ	状態	ヘッドの位置	マス $-3,-2,-1,0,1$	使う命令
0	$0$	$0$	$0,0,0,1,1$	$\langle0,1,1,1,0\rangle$（左へ）
1	$1$	$-1$	$0,0,0,1,1$	$\langle1,0,2,0,0\rangle$（左へ）
2	$2$	$-2$	$0,0,0,1,1$	$\langle2,0,3,1,0\rangle$（$1$ を書いて左へ）
3	$3$	$-3$	$0,1,0,1,1$	$\langle3,0,4,0,1\rangle$（右へ）
4	$4$	$-2$	$0,1,0,1,1$	なし（停止）

停止したテープは、入力 $(1,2)$ の初期テープ $1\sqcup11$ を左へ $2$ マスずらした $T_{-2}\tau_{(1,2)}$ で、ヘッドはその左端にある。

連結の小さな例

万能Turing機械の記事の例「後者関数の機械の番号と模倣」の番号 $e_S$ の機械は、状態 $0,1,2$ をもち $S(x)=x+1$ を計算する。$a=0$ とし、$\operatorname{join}(w(0),3,4,e_S)$ の命令を並べると
$$ \langle0,0,1,0,0\rangle,\ \langle0,1,1,1,0\rangle,\ \langle1,0,2,0,0\rangle,\ \langle2,0,3,0,1\rangle,\ \langle3,0,4,0,2\rangle,\ \langle3,1,4,1,2\rangle,\ \langle4,1,4,1,1\rangle,\ \langle4,0,5,1,0\rangle,\ \langle5,1,5,1,0\rangle,\ \langle5,0,6,0,1\rangle $$
となる。最初の 4 つが前置きの機械、次の 2 つがつなぎの命令、残りが後者関数の機械の状態を $4$ ずらしたものである。この機械は入力 $x$ に対して $x+1$ を出力する。

動きを開く

入力 $x$ からこの機械は、前置きの機械で $-1$ 番目のマス（空白）にヘッドを置き、つなぎの命令で状態 $4$ に移る。このときのテープは入力 $(0,x)$ の初期テープ（空白のあとに $1^x$）を左へ $1$ マスずらしたものである。そこから後者関数の機械が動き、$-1$ 番目の空白に $1$ を書いて左へ動き、空白を読んで右へ戻って状態 $6$ で止まる。テープはヘッドから右へ $1^{x+1}$ なので、出力は $x+1$ である。

つまりこの機械は、後者関数の機械に 2 つの入力 $(0,x)$ をテープに並べて与えたときの出力を計算する。これは $\varphi^{(2)}_{e_S}(0,x)\simeq\varphi_{e_S}(\langle0,x\rangle)=\langle0,x\rangle+1=2\cdot3^{x+1}+1$ とは異なる。$\varphi^{(k)}_e$ では引数を列の符号 1 つにまとめるので、テープ $1^a\sqcup1^c$ を符号に書き直す機械を間に挟む。それが thm-smn-rewrite の証明の機械 $M_g$ である。

性質

番号の操作は原始再帰的

$(c,d)\mapsto c\frown d$、$(t,K)\mapsto\operatorname{sh}_K(t)$、$(e,K)\mapsto\operatorname{sl}(e,K)$、$(p,H,K,e)\mapsto\operatorname{join}(p,H,K,e)$、$a\mapsto w(a)$ はどれも原始再帰関数である。

要点：どれも、素数 $p(i)$・冪・積・成分 $(c)_i$・長さ $\operatorname{lh}$ の合成に、上界が原始再帰関数である有界積を施して書ける。

詳しい証明を開く

万能Turing機械の記事の補題「列の操作は原始再帰的」により $(i,c)\mapsto(c)_i$、$c\mapsto\operatorname{lh}(c)$、$\langle x,y,z,w\rangle$ の形の符号は原始再帰的であり、5 項の符号 $\langle x_0,\dots,x_4\rangle=\prod_{i<5}p(i)^{x_i+1}$ も $p$ と冪・積の合成なので原始再帰的である。$p(i)$ と冪は原始再帰関数で（原始再帰関数の記事の命題「素数の判定と $n$ 番目の素数」と例「算術の基本的な関数」）、上界を原始再帰関数とする有界積は原始再帰関数を与える（同記事の命題「有界な和・積・量化・最小化」）。$c\frown d$ は上界 $\operatorname{lh}(d)$ の有界積に $c$ を掛けたもの、$\operatorname{sh}_K(t)$ は 5 項の符号と成分・和の合成、$\operatorname{sl}(e,K)$ は上界 $\operatorname{lh}(e)\dot-1$ の有界積、$\operatorname{join}$ はこれらの合成である。最後に $w(a)=\Bigl(\bigl\langle0,\langle0,0,1,0,0\rangle,\langle0,1,1,1,0\rangle,\langle1,0,2,0,0\rangle\bigr\rangle\frown\prod_{i< a}p(i)^{\langle i+2,0,i+3,1,0\rangle+1}\Bigr)\frown\bigl\langle\langle a+2,0,a+3,0,1\rangle\bigr\rangle$ であり、中央の有界積は $\iota_2,\dots,\iota_{a+1}$ の列の符号である。最初の因子は定数なので、$w$ も原始再帰関数である。$c\frown d$ が列をつなぐことは、素因数分解の一意性から $\operatorname{lh}$ と $(\cdot)_i$ の値を読めば確かめられる。$\square$

前置きの機械の動き

$a,c\in\mathbb{N}$ とする。$M_{w(a)}$ は入力 $c$ の初期様相から $a+3$ ステップで様相
$$ \bigl(a+3,\ T_{-a-1}\tau_{(a,c)},\ -a-1\bigr) $$
に達し、これは停止様相である。それより前の様相はどれも停止様相でなく、状態は $a+2$ 以下である。

要点：入力より左のマスはすべて空白なので、命令を 1 つずつ追えばよい。状態 $0$ で 1 マス左へ、状態 $1$ で空白を残してもう 1 マス左へ、状態 $2,\dots,a+1$ で $1$ を書きながら左へ進み、状態 $a+2$ で 1 マス右へ戻る。

詳しい証明を開く

入力 $c$ の初期テープ $\tau_c$ では $0,\dots,c-1$ 番目が $1$ で、ほかは空白である。とくに負の番号のマスはすべて空白である。

ステップ 1：状態 $0$、位置 $0$ で読む記号は $c\ge1$ なら $1$、$c=0$ なら $0$ である。どちらの場合も命令 $\langle0,0,1,0,0\rangle$ または $\langle0,1,1,1,0\rangle$ が働き、同じ記号を書き戻して左へ動くので、テープは変わらず、状態 $1$、位置 $-1$ になる。

ステップ 2：位置 $-1$ は空白なので、命令 $\langle1,0,2,0,0\rangle$ により、テープを変えずに状態 $2$、位置 $-2$ になる。

ステップ $i+1$（$2\le i\le a+1$）：$i$ についての帰納法で、ステップ $i$ の後は状態 $i$、位置 $-i$ で、テープは $\tau_c$ の $-2,\dots,-(i-1)$ 番目を $1$ に替えたものであることを示す。$i=2$ はステップ 2 の結果である。状態 $i$ で位置 $-i$ の空白を読むと、命令 $\iota_i=\langle i,0,i+1,1,0\rangle$ により $-i$ 番目に $1$ を書き、状態 $i+1$、位置 $-(i+1)$ になる。

最後のステップ：ステップ $a+2$ の後は状態 $a+2$、位置 $-(a+2)$ で、テープは $\tau_c$ の $-2,\dots,-(a+1)$ 番目（$a$ 個のマス）を $1$ に替えたものである（$a=0$ ならステップ 2 の後そのもので、テープは $\tau_c$ のまま）。位置 $-(a+2)$ は空白なので、命令 $\langle a+2,0,a+3,0,1\rangle$ により状態 $a+3$、位置 $-(a+1)$ になる。

この時点のテープは、$-(a+1),\dots,-2$ 番目が $1$、$-1$ 番目が空白、$0,\dots,c-1$ 番目が $1$ で、ほかは空白である。$\tau_{(a,c)}$ は $0,\dots,a-1$ 番目が $1$、$a$ 番目が空白、$a+1,\dots,a+c$ 番目が $1$ のテープなので、これは $T_{-a-1}\tau_{(a,c)}$ に等しい。$w(a)$ の命令で状態が $a+3$ のものはないので、この様相は停止様相である。途中の様相では、いま使った命令が働いたので停止様相でなく、状態は $0,\dots,a+2$ である。$\square$

連結した機械の動き

$p,H,K\in\mathbb{N}$ が次を満たすとする。

(i) $p$ は列の符号で $\operatorname{lh}(p)\ge1$ であり、$H< K$、$(p)_0< K$、かつ $1\le j<\operatorname{lh}(p)$ のすべての $j$ で $((p)_j)_0< K$、$((p)_j)_2< K$ である。
(ii) $((p)_j)_0=H$ となる $j$（$1\le j<\operatorname{lh}(p)$）はない。
$e\in\mathbb{N}$ とし、$D:=M_{\operatorname{join}(p,H,K,e)}$ とおく。このとき次が成り立つ。

$D$ の初期状態は $(p)_0$ である。$q< K$、$q\neq H$ なら、すべての $a$ で $\delta_D(q,a)\simeq\delta_p(q,a)$ である。
$b\in\{0,1\}$ なら $\delta_D(H,b)=\bigl((e)_0+K,\ b,\ \mathrm{N}\bigr)$ である。
すべての $q,a$ について、$\delta_D(q+K,a)$ が定義されることと $\delta_e(q,a)$ が定義されることは同値であり、$\delta_e(q,a)=(q',b,X)$ なら $\delta_D(q+K,a)=(q'+K,b,X)$ である。
$M_p$ が様相 $C_0$ から $n$ ステップで状態 $H$ の様相 $C$ に達するなら、$D$ も $C_0$ から $n$ ステップで $C$ に達する。
$M_e$ の様相 $C$ と $d\in\mathbb{Z}$ について、$C^{K,d}$ が $D$ の停止様相であることと $C$ が $M_e$ の停止様相であることは同値であり、停止様相でなければ、$D$ での $C^{K,d}$ の次の様相は、$M_e$ での $C$ の次の様相 $C'$ について $C'^{K,d}$ である。

要点：連結の命令は「$M_p$ の命令（状態の成分は $K$ 未満で $H$ でない）」「つなぎの命令（状態の成分は $H$）」「$M_e$ の命令を $K$ ずらしたもの（状態の成分は $K$ 以上）」の順に並ぶので、状態ごとに最初に合う命令はそれぞれの部分の中で決まる。4 は 1 の繰り返し、5 は 3 と、ヘッドの下の記号が平行移動で変わらないことによる。

詳しい証明を開く

$\operatorname{join}(p,H,K,e)$ の命令は、$M_p$ の命令（状態の成分は (i) により $K$ 未満で、(ii) により $H$ でない）、つなぎの命令 2 つ（状態の成分は $H$）、$\operatorname{sh}_K((e)_j)$（状態の成分は $((e)_j)_0+K\ge K$）の順に並んでいる。$\delta_D(q,a)$ は、状態の成分が $q$、記号の成分が $a$ である最初の命令で決まる。

1：初期状態は列の最初の項 $(p)_0$ である。$q< K$、$q\neq H$ なら、状態の成分が $q$ になりうるのは $M_p$ の命令だけで、それらは $M_p$ と同じ順に並んでいるので、最初に合う命令は $M_p$ と $D$ で同じである（合う命令がないことも一致する）。

2：(ii) により $M_p$ の命令の状態の成分は $H$ でなく、(i) の $H< K$ により $\operatorname{sh}_K$ の命令も合わない。よって状態 $H$、記号 $b\in\{0,1\}$ で最初に合うのはつなぎの命令 $\langle H,b,(e)_0+K,b,2\rangle$ で、向きの成分 $2$ は $\mathrm{N}$ を表す。

3：状態の成分が $q+K\ge K$ になりうるのは $\operatorname{sh}_K((e)_j)$ だけである。$\operatorname{sh}_K((e)_j)$ が $(q+K,a)$ に合うことは、$((e)_j)_0=q$ かつ $((e)_j)_1=a$、すなわち $(e)_j$ が $(q,a)$ に合うことと同値で、並ぶ順も同じなので、最初に合う命令は対応する。$\operatorname{sh}_K$ は次の状態の成分に $K$ を足し、書く記号と向きの成分を変えないので、値は $(q'+K,b,X)$ である。

4：$M_p$ では状態 $H$ の命令がないので、状態 $H$ の様相はどれも停止様相である。よって $C_0$ から $C$ に至る途中の様相の状態は $H$ でなく、$M_p$ の状態なので (i) により $K$ 未満である。1 により $D$ は途中の各様相で $M_p$ と同じ遷移をするので、$n$ についての帰納法で $D$ も $n$ ステップで $C$ に達する。

5：$C=(q,\tau,h)$ とする。$C^{K,d}=(q+K,T_d\tau,h+d)$ でヘッドの下の記号は $(T_d\tau)(h+d)=\tau(h)$ なので、3 により前半が成り立つ。$\delta_e(q,\tau(h))=(q',b,X)$ とし、$X$ に応じた移動を $\epsilon\in\{-1,1,0\}$ とする。$C'=(q',\tau',h+\epsilon)$ で、$\tau'$ は $\tau$ の $h$ 番目を $b$ に替えたものである。$D$ では $C^{K,d}$ から、3 により $T_d\tau$ の $h+d$ 番目を $b$ に替えて状態 $q'+K$、位置 $h+d+\epsilon$ に移る。$T_d\tau$ の $h+d$ 番目を $b$ に替えたテープは $T_d\tau'$ なので、次の様相は $C'^{K,d}$ である。$\square$

5 を繰り返すと、$C^{K,d}$ から始まる $D$ の計算は、$C$ から始まる $M_e$ の計算を $K,d$ でずらしたものであり、停止するかどうかも、ヘッドの位置から見たテープの形（出力の形）も一致する。

入力を書き換えてから計算する番号

入力の書き換え

$G\colon\mathbb{N}^2\to\mathbb{N}$ を全域的な Turing 計算可能関数とする。原始再帰関数 $t_G\colon\mathbb{N}^2\to\mathbb{N}$ があって、すべての $e,a,c$ について
$$ \varphi_{t_G(e,a)}(c)\simeq\varphi_e\bigl(G(a,c)\bigr) $$
が成り立つ。

段 1（$G$ を計算する機械を整える）． $G$ を計算する Turing 機械を、名前の付け替えで標準の機械 $M=(Q,\Gamma,0,q_0,\delta)$ に移す（Turing機械の記事の節「計算できない関数の存在」の名前の付け替え）。$H_G:=1+\max Q$ とし、$q\in Q$、$b\in\{0,1\}$ で $\delta(q,b)$ が定義されないすべての組に $\delta'(q,b):=(H_G,b,\mathrm{N})$ を付け加えた遷移関数 $\delta'$ の機械を $M'$ とする（$M'$ の状態は $Q\cup\{H_G\}$）。万能Turing機械の記事の補題「標準の機械はどれも番号をもつ」の番号を $g$ とすると、$M_g$ の計算は $M'$ の計算と各ステップで一致し、$g$ は列の符号で、状態の成分はすべて $H_G$ 以下、状態の成分が $H_G$ の命令はない。$K_G:=H_G+1$ とおく。
$a,c\in\mathbb{N}$ とする。$M$ は $G(a,c)$ を計算するので、入力 $(a,c)$ の初期様相から停止し、停止様相 $(q,\tau,h)$ ではヘッドから右へ $1^{G(a,c)}$、ほかは空白である。とくに $\tau(h)\in\{0,1\}$ で $\delta(q,\tau(h))$ は定義されない。$\delta'$ は $\delta$ を定義されていない組にだけ延ばしたものなので、$M'$ はそこまで $M$ と同じに動き、次の 1 ステップで $(H_G,\tau,h)$ に移って停止する。よって次が成り立つ。
(∗) $M_g$ は入力 $(a,c)$ の初期様相から、状態 $H_G$ の様相 $(H_G,\tau,h)$ に達し、$\tau(h+i)=1$（$0\le i< G(a,c)$）、それ以外では $\tau=0$ である。
段 2（番号の定義）．
$$ t_G(e,a):=\operatorname{join}\Bigl(\operatorname{join}\bigl(w(a),\ a+3,\ a+4,\ g\bigr),\ H_G+a+4,\ K_G+a+4,\ e\Bigr) $$
とおく。$g,H_G,K_G$ は定数なので、lem-smn-pr により $t_G$ は原始再帰関数である。$p_a:=\operatorname{join}(w(a),a+3,a+4,g)$、$D_1:=M_{p_a}$、$D_2:=M_{t_G(e,a)}$ と書く。
段 3（$D_1$ の動き）． $w(a)$ の状態の成分は $a+3$ 以下で、状態 $a+3$ の命令はないので、$p=w(a)$、$H=a+3$、$K=a+4$ は lem-smn-join の (i)(ii) を満たす。入力 $c$ から次のように進む。

lem-smn-prefix と lem-smn-join の 4 により、$D_1$ は $\bigl(a+3,\ T_{-a-1}\tau_{(a,c)},\ -a-1\bigr)$ に達する。
ヘッドの下の記号は $\tau_{(a,c)}(0)\in\{0,1\}$ なので、lem-smn-join の 2 により次の様相は $\bigl((g)_0+a+4,\ T_{-a-1}\tau_{(a,c)},\ -a-1\bigr)$ である。これは入力 $(a,c)$ の初期様相 $C_0=((g)_0,\tau_{(a,c)},0)$ について $C_0^{a+4,-a-1}$ である。
lem-smn-join の 5 と (∗) により、$D_1$ はその後 $M_g$ の計算をずらしてたどり、様相 $(H_G+a+4,\ T_{-a-1}\tau,\ h-a-1)$ に達する。

段 4（$D_2$ の動き）． $p_a$ の状態の成分は $a+3$ 以下か、$g$ の状態の成分に $a+4$ を足したものなので、すべて $H_G+a+4$ 以下であり、$g$ に状態 $H_G$ の命令がないので、状態の成分が $H_G+a+4$ の命令はない。よって $p=p_a$、$H=H_G+a+4$、$K=K_G+a+4$ は (i)(ii) を満たす。
段 3 の計算は $p_a$ の機械 $D_1$ の計算であり、最後の様相の状態は $H_G+a+4$ である。lem-smn-join の 4 により、$D_2$ も入力 $c$ から同じ様相 $(H_G+a+4,\ T_{-a-1}\tau,\ h-a-1)$ に達する。$z:=G(a,c)$ とおくと、(∗) によりこのテープは入力 $z$ の初期テープ $\tau_z$ を $h-a-1$ だけずらした $T_{h-a-1}\tau_z$ に等しく、ヘッドの下の記号は $0$ か $1$ である。lem-smn-join の 2 により、次の様相は $\bigl((e)_0+K_G+a+4,\ T_{h-a-1}\tau_z,\ h-a-1\bigr)$、すなわち $M_e$ の入力 $z$ の初期様相 $C_z$ について $C_z^{K_G+a+4,\ h-a-1}$ である。
段 5（出力）． lem-smn-join の 5 とその後の注意により、ここから先の $D_2$ の計算は $M_e$ の入力 $z$ からの計算をずらしたものであり、$D_2$ が停止するのは $M_e$ が停止するときちょうどで、停止したときのテープの形も同じである。それまでの $D_2$ の様相は停止様相でない（段 3・4 で各ステップに働く命令があった）。よって
$$ \varphi_{t_G(e,a)}(c)\simeq\operatorname{out}_{D_2}(c)\simeq\operatorname{out}_{M_e}(z)\simeq u(e,z)\simeq\varphi_e\bigl(G(a,c)\bigr) $$
である。$\square$

$t_G(e,a)$ の機械は、「入力の前に $1^a$ と空白を書く」「$1^a\sqcup1^c$ を $1^{G(a,c)}$ に書き直す」「$M_e$ を動かす」をつないだものである。つなぎ目では、状態をずらすことと、前の機械が形の正しいテープで止まることが要る（下の反例の表の 1・2 行目）。

s-m-n 定理

$m\ge1$ とする。

原始再帰関数 $s^m_1\colon\mathbb{N}^{1+m}\to\mathbb{N}$ があって、すべての $e,a_1,\dots,a_m,y$ について
$$ \varphi_{s^m_1(e,a_1,\dots,a_m)}(y)\simeq\varphi^{(m+1)}_e(a_1,\dots,a_m,y) $$
が成り立つ。
$n\ge2$ とする。原始再帰関数 $s^m_n\colon\mathbb{N}^{1+m}\to\mathbb{N}$ があって、すべての $e,a_1,\dots,a_m,y_1,\dots,y_n$ について
$$ \varphi^{(n)}_{s^m_n(e,a_1,\dots,a_m)}(y_1,\dots,y_n)\simeq\varphi^{(m+n)}_e(a_1,\dots,a_m,y_1,\dots,y_n) $$
が成り立つ。

$n\ge1$ に対し、2 変数の関数 $G_{m,n}$ を
$$ G_{m,n}(a,c):=\prod_{i< m}p(i)^{(a)_i+1}\cdot R_n(c),\qquad R_n(c):=\begin{cases}p(m)^{c+1}&(n=1),\\ \prod_{j< n}p(m+j)^{(c)_j+1}&(n\ge2)\end{cases} $$
で定める。$m,n$ は固定されているので、$G_{m,n}$ は $p$・冪・成分 $(\cdot)_i$ の有限個の合成と積であり、原始再帰関数であり、とくに全域的な Turing 計算可能関数である（(A)）。
$\vec a=(a_1,\dots,a_m)$ に対し $a:=\langle a_1,\dots,a_m\rangle$ とおくと $(a)_i=a_{i+1}$（$i< m$）である。$n=1$ なら $G_{m,1}(a,y)=\prod_{i< m}p(i)^{a_{i+1}+1}\cdot p(m)^{y+1}=\langle a_1,\dots,a_m,y\rangle$ である。$n\ge2$ で $c:=\langle y_1,\dots,y_n\rangle$ なら $(c)_j=y_{j+1}$ なので $G_{m,n}(a,c)=\langle a_1,\dots,a_m,y_1,\dots,y_n\rangle$ である。
thm-smn-rewrite を $G=G_{m,n}$ に使い、
$$ s^m_n(e,a_1,\dots,a_m):=t_{G_{m,n}}\bigl(e,\langle a_1,\dots,a_m\rangle\bigr) $$
とおく。原始再帰関数の合成なので $s^m_n$ は原始再帰関数である。$n=1$ では
$$ \varphi_{s^m_1(e,\vec a)}(y)\simeq\varphi_e\bigl(G_{m,1}(a,y)\bigr)=\varphi_e(\langle\vec a,y\rangle)\simeq\varphi^{(m+1)}_e(\vec a,y) $$
であり、$n\ge2$ では
$$ \varphi^{(n)}_{s^m_n(e,\vec a)}(\vec y)\simeq\varphi_{s^m_n(e,\vec a)}(\langle\vec y\rangle)\simeq\varphi_e\bigl(G_{m,n}(a,\langle\vec y\rangle)\bigr)=\varphi_e(\langle\vec a,\vec y\rangle)\simeq\varphi^{(m+n)}_e(\vec a,\vec y) $$
である。$\square$

1 で $m=1$ とした $\sigma:=s^1_1$ は、すべての $e,a,y$ で $\varphi_{\sigma(e,a)}(y)\simeq\varphi^{(2)}_e(a,y)$ を満たす。計算可能性理論の記事で番号付けに課している s-m-n 定理 (N4) の形はこれである。原始再帰関数は計算可能関数なので（(A)）、標準の番号付けは (N4) を満たし、(N1)〜(N3) と合わせて同記事の 4 条件をすべて満たす。1 変数でも入力を $\langle y\rangle$ と符号にする流儀なら、$R_1(c):=p(m)^{(c)_0+1}$ とおけば同じ証明が通る。
OLT26 Theorem 30.3（p. 450）は同じ主張を標準形で定めた番号付けについて述べ、p. 451 で、Turing 機械の番号に対しては入力の前に引数を書き足してから $e$ を動かす機械の符号を求める関数として $s^m_n$ を説明している。

帰結

引数の取り込み

$m\ge1$ とし、$g\colon\mathbb{N}^{m+1}\rightharpoonup\mathbb{N}$ を部分計算可能関数とする。原始再帰関数 $h\colon\mathbb{N}^m\to\mathbb{N}$ があって、すべての $\vec a,y$ について $\varphi_{h(\vec a)}(y)\simeq g(\vec a,y)$ が成り立つ。

計算可能関数の記事の命題「番号付けは部分計算可能関数をすべて並べる」により $g=\varphi^{(m+1)}_c$ となる $c$ がある。$h(\vec a):=s^m_1(c,\vec a)$ は $c$ を定数とした原始再帰関数で、thm-smn-main の 1 により $\varphi_{h(\vec a)}(y)\simeq\varphi^{(m+1)}_c(\vec a,y)\simeq g(\vec a,y)$ である。$\square$

合成の番号

原始再帰関数 $\kappa\colon\mathbb{N}^2\to\mathbb{N}$ があって、すべての $e,f,x$ について $\varphi_{\kappa(e,f)}(x)\simeq\varphi_e\bigl(\varphi_f(x)\bigr)$ が成り立つ。

$\psi(e,f,x):\simeq\varphi_e(\varphi_f(x))$ とおく。$(e,x)\mapsto\varphi_e(x)$ は部分計算可能であり（計算可能関数の記事の命題「番号付けは部分計算可能関数をすべて並べる」）、部分計算可能関数は合成で閉じているので（(A)）、$\psi$ は 3 変数の部分計算可能関数である。cor-smn-param を $m=2$ で使えば、原始再帰関数 $\kappa$ で $\varphi_{\kappa(e,f)}(x)\simeq\psi(e,f,x)$ となるものがある。$\square$

全域性と入力 0 での停止は決定できない

$\mathrm{Tot}:=\{e\mid\varphi_e\text{ は全域的}\}$、$K_0:=\{e\mid\varphi_e(0)\!\downarrow\}$ とおく。どちらも決定可能でない。
停止問題の記事の定理「停止集合は半決定可能」の証明の μ再帰関数 $h$（(A) により部分計算可能）について、$h(x,x)$ が定義されるのは $x$ が同記事の自己停止集合 $K$（$M_x$ が入力 $x$ で停止する $x$ の集合）に属するときちょうどである。$\ell(x,y):\simeq Z\bigl(h(x,x)\bigr)$（$Z$ はゼロ関数）は部分計算可能なので、cor-smn-param により原始再帰関数 $r$ で $\varphi_{r(x)}(y)\simeq\ell(x,y)$ となるものがある。$x\in K$ なら $\varphi_{r(x)}$ は定数 $0$ の関数、$x\notin K$ ならどこでも定義されない関数である。よって
$$ x\in K\iff r(x)\in\mathrm{Tot}\iff r(x)\in K_0 $$
である。$\mathrm{Tot}$ が決定可能なら $\chi_K=\chi_{\mathrm{Tot}}\circ r$ は計算可能関数の合成なので計算可能になり、停止問題の記事の定理「停止問題の決定不能性」に反する。$K_0$ も同じである。還元は OLT26 Proposition 30.22（pp. 464–465）と同じ形で、計算可能性理論の記事の定理「全域性の集合とその補集合はどちらも半決定可能でない」はさらに強い主張である。

仮定を外したときの反例

外す条件	反例	成り立たなくなること
lem-smn-join の (i)：前の機械の状態と $H$ が $K$ 未満	$\operatorname{join}(w(0),3,0,e_S)$（状態をずらさずにつなぐ）	つないだ後に $M_{e_S}$ の計算をたどること
thm-smn-rewrite の証明の (∗)：前の機械が形の正しいテープで止まる	1 マス右へ動いて止まる機械と、1 マス左へ動いて止まる機械の連結	つないだ機械が $\varphi_e\circ\varphi_p$ を計算すること
$s$ を機械の書き換えとして構成すること	等式を満たす番号のうち最小のものを返す $s_{\min}$	$s$ が計算可能であること

反例の確かめ

1・2 行目はつなぎ目の条件を 1 つずつ外した例で、3 行目は等式を満たす番号の選び方を変えた例である。

詳しい確かめを開く

1 行目：$K=0$ では $\operatorname{sh}_0$ は何もしないので、命令は $w(0)$ の 4 つ、つなぎの命令 $\langle3,0,0,0,2\rangle$・$\langle3,1,0,1,2\rangle$、$e_S$ の命令 $\langle0,1,0,1,1\rangle$・$\langle0,0,1,1,0\rangle$・$\langle1,1,1,1,0\rangle$・$\langle1,0,2,0,1\rangle$ の順に並ぶ。(ii) は満たされるが、$H=3$ も $M_{w(0)}$ の状態 $0,1,2$ も $K=0$ 未満でなく、状態 $0,1,2$ は $e_S$ の状態と重なっている。入力 $x$ から、lem-smn-prefix のとおり 3 ステップで状態 $3$、位置 $-1$ に達し、つなぎの命令で状態 $0$ に移る。ここで $M_{e_S}$ なら空白に $1$ を書く（ex-smn-join-small）が、状態 $0$ で空白を読んで最初に合う命令は前置きの機械の $\langle0,0,1,0,0\rangle$ である。以後、位置 $h$ の状態 $0$ から、テープを変えずに位置 $h-1$（状態 $1$）、$h-2$（状態 $2$）、$h-1$（状態 $3$）、$h-1$（状態 $0$）と進む動きが、空白だけの左側で限りなく繰り返され、機械は停止しない。一方 $M_{e_S}$ はずらした初期様相からすぐに停止する。

2 行目：$p:=\langle0,\langle0,0,1,0,1\rangle,\langle0,1,1,1,1\rangle\rangle$（1 マス右へ動いて状態 $1$ で止まる）、$e:=\langle0,\langle0,0,1,0,0\rangle,\langle0,1,1,1,0\rangle\rangle$（1 マス左へ動いて状態 $1$ で止まる）とし、$H=1$、$K=2$ とする。(i)(ii) は満たされる。入力 $2$（$0,1$ 番目が $1$）では、$M_p$ は位置 $1$ で止まり、左の $0$ 番目に $1$ が残るので出力の形が正しくなく、$\varphi_p(2)$ は定義されない。したがって $\varphi_e(\varphi_p(2))$ も定義されない。ところが $\operatorname{join}(p,1,2,e)$ の機械は、位置 $1$ でつなぎの命令により状態 $2$ に移り、ずらした $e$ の命令で位置 $0$ へ戻って状態 $3$ で止まる。テープはヘッドから右へ $11$ なので出力は $2$ である。

3 行目：thm-smn-main により、各 $(e,a)$ に $\varphi_d=\varphi^{(2)}_e(a,\cdot)$ となる $d$ があるので、その最小値 $s_{\min}(e,a)$ が定まる。$s_{\min}$ が計算可能だとする。ex-smn-tot の $\ell$ について $\ell=\varphi^{(2)}_c$ となる $c$ をとり、定数 $0$ の関数とどこでも定義されない関数の最小の番号を $d_0,d_1$ とする（どちらも部分計算可能なので番号をもち、関数が異なるので $d_0\neq d_1$）。$x\in K$ なら $s_{\min}(c,x)=d_0$、$x\notin K$ なら $s_{\min}(c,x)=d_1$ なので、$\chi_K(x)=\overline{\mathrm{sg}}\bigl(\lvert s_{\min}(c,x)-d_0\rvert\bigr)$ は計算可能になり、停止問題の記事の定理「停止問題の決定不能性」に反する。

3 行目が示すように、s-m-n 定理の中身は、等式を満たす番号があること（番号付けがすべての部分計算可能関数を並べることから分かる）ではなく、その番号を計算で求められることにある。

補足

番号付けを使う議論での役割． 計算可能性理論の記事の自己停止集合の完全性、Rice の定理、Kleene の再帰定理の証明は cor-smn-param の形で s-m-n 定理を使う。
Church–Turing のテーゼとの関係． この記事の証明はテーゼを使わず、外部の事実としては (A) だけを使う（Church–Turingのテーゼ）。