万能Turing機械

同義語：万能チューリング機械万能Turingマシンuniversal Turing machine

概要

前提知識: Turing機械, 原始再帰関数, μ再帰関数

Turing機械は 1 台ごとに決まった 1 つの計算しかしない。加法の機械は足し算しかせず、後者関数の機械は $1$ を足すことしかしない。ところが、機械は有限個のデータ（状態・記号・遷移の一覧）で決まるので、それを 1 つの自然数 $e$ に符号化して、入力と並べてテープに書くことができる。万能 Turing 機械 とは、番号 $e$ と入力 $x$ を受け取り、番号 $e$ の機械が入力 $x$ に対して行う計算をそのまま再現して同じ結果を返す 1 台の Turing 機械である。番号 $e$ が「プログラム」、万能機械が「プログラムを読んで実行する計算機」にあたる。
この記事では、Turing 機械の番号付けを具体的に定め、番号 $e$ の機械を入力 $x$ で動かした結果を返す 2 変数の部分関数 $u(e,x)$ が μ再帰関数であることを、計算の 1 ステップが原始再帰関数で書けることから証明する。μ再帰関数が Turing 計算可能であることと合わせて、万能 Turing 機械が存在することが分かる。さらに、$u$ は部分関数であることが避けられず、全域的な計算可能関数に延長できないことを示す。
記法は Turing機械の記事に合わせる。$\mathbb{N}=\{0,1,2,\dots\}$ とし、機械は組 $M=(Q,\Gamma,\sqcup,q_0,\delta)$、様相は $(q,\tau,h)$（状態、テープの内容 $\tau\colon\mathbb{Z}\to\Gamma$、ヘッドの位置）である。$Q$ と $\Gamma$ が $\mathbb{N}$ の有限部分集合で、空白記号が $0$、記号 $1$ が $1$ である機械を 標準の機械 という。部分関数の値について、$\alpha\simeq\beta$ は「両辺がともに定義されないか、ともに定義されて等しい」ことを表す。

定義

番号付け

有限列を自然数に符号化する。$p(i)$ を $i$ 番目の素数（$p(0)=2$、$p(1)=3$、…）とし、自然数の有限列 $(a_0,\dots,a_{k-1})$ に対して
$$ \langle a_0,\dots,a_{k-1}\rangle:=\prod_{i< k}p(i)^{a_i+1} $$
とおく（空の列は $\langle\,\rangle=1$）。指数に $1$ を足しておくのは、値が $0$ の項も素因数として残し、列の長さを読み取れるようにするためである。素因数分解の一意性により、異なる列は異なる数に写る。$\langle a_0,\dots,a_{k-1}\rangle$ の形の数を 列の符号 という。

番号から決まる機械

自然数 $c\ge1$ に対し、$\operatorname{lh}(c)$ を「$p(0),\dots,p(i-1)$ がすべて $c$ を割る」ような最大の $i$ とし、$(c)_i$ を「$p(i)^z$ が $c$ を割る最大の $z$」から $1$ を引いた数（その $z$ が $0$ なら $0$）とする。$c=0$ のときは $\operatorname{lh}(0)=0$、$(0)_i=0$ と約束する。列の符号 $c=\langle a_0,\dots,a_{k-1}\rangle$ では $\operatorname{lh}(c)=k$、$(c)_i=a_i$（$i< k$）である。自然数 $e$ に対し、$t_j:=(e)_j$（$1\le j<\operatorname{lh}(e)$）を命令とよび、その成分を $(t_j)_0,\dots,(t_j)_4$ とする。
番号 $e$ の機械 $M_e$ とは、次の標準の機械である。

初期状態は $(e)_0$。状態の集合は、$(e)_0$ と、命令の成分 $(t_j)_0,(t_j)_2$ 全体。テープ記号の集合は、$0,1$ と命令の成分 $(t_j)_1,(t_j)_3$ 全体。
状態 $q$ で記号 $a$ を読んだとき、$(t_j)_0=q$ かつ $(t_j)_1=a$ となる命令があれば、そのうち $j$ が最小のものをとり、$\delta(q,a):=\bigl((t_j)_2,(t_j)_3,D\bigr)$ とする。ここで向き $D$ は、$(t_j)_4=0$ なら $\mathrm{L}$、$(t_j)_4=1$ なら $\mathrm{R}$、それ以外なら $\mathrm{N}$ である。そのような命令がなければ $\delta(q,a)$ は定義しない。
$e$ を $M_e$ の番号（指数）という。

どの自然数 $e$ も 1 台の機械を定める。$e$ が列の符号でない場合も、上の読み取りで何らかの機械（たとえば命令のない機械）が決まる。番号付けをこのように全射的に作っておくと、「$e$ が正しい符号か」を判定する手間が省ける。

標準の機械はどれも番号をもつ

標準の機械 $M=(Q,\Gamma,0,q_0,\delta)$ の遷移関数が定義されている組を $(q_j,a_j)$、$\delta(q_j,a_j)=(q'_j,b_j,D_j)$（$1\le j\le m$）とし、$D_j=\mathrm{L},\mathrm{R},\mathrm{N}$ を $d_j=0,1,2$ で表す。
$$ e:=\bigl\langle q_0,\ \langle q_1,a_1,q'_1,b_1,d_1\rangle,\ \dots,\ \langle q_m,a_m,q'_m,b_m,d_m\rangle\bigr\rangle $$
とおくと、どの入力の初期様相から始めても、$M_e$ の計算は $M$ の計算と各ステップで一致する。とくに $M$ が部分関数 $f$ を計算するなら $M_e$ も $f$ を計算する。さらに、$f$ を計算する標準の機械の番号は無限個ある。

$M_e$ の初期状態は $q_0$ で、$M_e$ の遷移関数は、$M$ の遷移関数が定義されている組では $M$ と同じ値をとり、それ以外の組では定義されない（命令の $(q_j,a_j)$ は互いに異なるので、最小の $j$ をとる規則は働かない）。$M_e$ の状態の集合 $Q_e$ とテープ記号の集合 $\Gamma_e$ は $Q,\Gamma$ の部分集合である。
計算のステップ数 $s$ についての帰納法で、$M$ の $s$ 番目の様相が「状態が $Q_e$ に、テープの記号がすべて $\Gamma_e$ に属する」ことと、それが $M_e$ の $s$ 番目の様相でもあることを示す。初期様相では状態は $q_0\in Q_e$、テープの記号は $0,1\in\Gamma_e$ である。$s$ 番目の様相 $(q,\tau,h)$ で成り立つとする。$\delta(q,\tau(h))$ が $M$ で定義されているかどうかと、$M_e$ で定義されているかどうかは一致し、定義されているなら値も一致する。次の様相の状態 $q'_j$ と、新しく書かれる記号 $b_j$ は命令の成分なので、それぞれ $Q_e$、$\Gamma_e$ に属する。よって $s+1$ 番目でも成り立つ。停止するかどうかと停止様相も一致するので、計算する部分関数も一致する。
最後の主張：列の符号 $e$ の後ろに、$M$ の状態でない新しい状態 $q^\ast$ についての命令 $\langle q^\ast,0,q^\ast,0,2\rangle$ を $n$ 個（$n=1,2,\dots$）付け加えた符号を $e_n$ とする。$q^\ast$ へ移る命令は、$q^\ast$ から出る付け加えた命令だけなので、$M_{e_n}$ が初期状態から状態 $q^\ast$ に入ることはない。前半と同じ帰納法で $M_{e_n}$ の計算は $M$ の計算と一致する。$e_1< e_2<\cdots$ は相異なる。$\square$

出力と万能関数

Turing 機械が停止しても、テープが「ヘッドから右へ $1$ が並び、ほかは空白」という形になっているとは限らない。そこで、出力の形が正しい場合だけ値をもつ部分関数を考える。

出力関数と万能関数

機械 $M$ と $x\in\mathbb{N}$ について、入力 $x$ の初期様相から $M$ が停止し、停止様相 $(q,\tau,h)$ で $\tau(h+i)=1$（$0\le i< y$）、それ以外の $j$ で $\tau(j)=0$（空白）となっているとき、$\operatorname{out}_M(x):=y$ と定める。そうでないとき（停止しないか、停止したテープがこの形でないとき）$\operatorname{out}_M(x)$ は定義しない。
番号 $e$ と入力 $x$ に対し
$$ u(e,x):\simeq\operatorname{out}_{M_e}(x) $$
で定まる 2 変数の部分関数 $u\colon\mathbb{N}^2\rightharpoonup\mathbb{N}$ を 万能関数 という。

$M$ が部分関数 $f$ を計算するなら、Turing機械の記事の定義「Turing 機械が計算する関数」により $\operatorname{out}_M=f$ である。$f(x)$ が定義されれば $M$ は形の正しいテープ $1^{f(x)}$ で停止し、定義されなければ停止しないからである。lem-utm-every-machine と合わせると、1 変数の Turing 計算可能な部分関数 $f$ にはどれも、すべての $x$ で $f(x)\simeq u(e,x)$ となる番号 $e$ がある。

万能 Turing 機械

2 変数の部分関数 $u$ を（Turing機械の記事の定義「Turing 機械が計算する関数」の意味で）計算する Turing 機械 $U$ を、万能 Turing 機械（universal Turing machine）という。

言い換えると、$U$ は入力 $1^e\sqcup1^x$ から始めて、番号 $e$ の機械が入力 $x$ に対して形の正しい出力 $y$ で停止するときは同じ $y$ を出力して停止し、そうでないときは停止しない。$U$ 自身は 1 台の機械で、状態もテープ記号も有限個しかないが、状態や記号をいくら多くもつ機械でも模倣できる。模倣される機械の状態と記号は、$U$ のテープの上では番号として書かれるからである。
万能性は番号付けを固定して初めて意味をもつ。番号の付け方を変えれば $u$ も変わり、番号から機械の動作を計算で読み取れない付け方では、万能機械が存在しないことがある（後の「仮定を外したときの反例」）。

例

後者関数の機械の番号と模倣

Turing機械の記事の例「後者関数を計算する機械」は、状態 $q_0,q_1,q_2$ を $0,1,2$ とすれば標準の機械であり、lem-utm-every-machine の番号は
$$ e_S=\bigl\langle 0,\ \langle0,1,0,1,1\rangle,\ \langle0,0,1,1,0\rangle,\ \langle1,1,1,1,0\rangle,\ \langle1,0,2,0,1\rangle\bigr\rangle $$
である。最初の命令 $\langle0,1,0,1,1\rangle=2^1\cdot3^2\cdot5^1\cdot7^2\cdot11^2=533610$ がすでに大きく、$e_S$ は $3^{533611}$ を約数にもつ巨大な数になる。番号の大きさは問題にならない。万能関数が使うのは、番号から命令を取り出す操作が機械的に計算できることだけである。
入力 $x=1$ での計算を、後の def-utm-config-code の形（状態、ヘッドより左のマスの列、ヘッドの下の記号、ヘッドより右のマスの列）で追う。左右の列はヘッドに近いマスほど後ろに並べる。

ステップ	状態	左の列	ヘッドの下	右の列	使う命令
0	$0$	$(\,)$	$1$	$(\,)$	$\langle0,1,0,1,1\rangle$（右へ）
1	$0$	$(1)$	$0$	$(\,)$	$\langle0,0,1,1,0\rangle$（左へ）
2	$1$	$(\,)$	$1$	$(1)$	$\langle1,1,1,1,0\rangle$（左へ）
3	$1$	$(\,)$	$0$	$(1,1)$	$\langle1,0,2,0,1\rangle$（右へ）
4	$2$	$(0)$	$1$	$(1)$	なし（停止）

ステップ 4 では、左の列は空白だけで、ヘッドから右へ $1,1$ と読んだあとは空白なので、出力は $u(e_S,1)=2=S(1)$ である。

停止しない番号と形の正しくない出力

$e=\langle0,\langle0,0,0,0,1\rangle,\langle0,1,0,1,1\rangle\rangle$ の機械は、状態 $0$ のまま右へ動き続けて停止しない（Turing機械の記事の例「停止しない機械」）。よってすべての $x$ で $u(e,x)$ は定義されない。
$e'=\langle0,\langle0,1,1,0,2\rangle\rangle$ の機械は、状態 $0$ で $1$ を読むとそれを空白に書き換えて状態 $1$ に移り、そこで停止する。空白を読んだ場合はすぐに停止する。入力 $x=0$ ではテープは空白だけなので $u(e',0)=0$、$x=1$ では唯一の $1$ が消えて $u(e',1)=0$ である。$x\ge2$ では、ヘッドの下が空白でその右に $1^{x-1}$ が残るので出力の形が正しくなく、$u(e',x)$ は定義されない。停止するかどうかと、$u$ の値が定義されるかどうかは一致しない。

性質

計算の 1 ステップは原始再帰的

万能関数を μ再帰関数で書くために、様相を自然数で表し、1 ステップの変化を原始再帰関数で書く。以下の「原始再帰的」は原始再帰関数の記事の定義による。

列の操作は原始再帰的

次の関数はどれも原始再帰関数である。

$(i,c)\mapsto(c)_i$ と $c\mapsto\operatorname{lh}(c)$。
列の後ろに 1 項を付け加える $\operatorname{app}(c,b):=c\cdot p(\operatorname{lh}(c))^{b+1}$、最後の項 $\operatorname{last}(c)$（$\operatorname{lh}(c)\ge1$ なら $(c)_{\operatorname{lh}(c)-1}$、そうでなければ $0$）、最後の項を除く $\operatorname{init}(c):=\prod_{i<\operatorname{lh}(c)\dot-1}p(i)^{(c)_i+1}$。
$\langle x,y,z,w\rangle=2^{x+1}3^{y+1}5^{z+1}7^{w+1}$ と、$1$ を $n$ 個並べた列の符号 $\operatorname{ones}(n):=\prod_{i< n}p(i)^2$。
列の符号 $c=\langle a_0,\dots,a_{k-1}\rangle$ では、$\operatorname{app}(c,b)=\langle a_0,\dots,a_{k-1},b\rangle$、$\operatorname{last}(c)=a_{k-1}$（$k=0$ なら $0$）、$\operatorname{init}(c)=\langle a_0,\dots,a_{k-2}\rangle$（$k\le1$ なら空の列）である。

要点：どれも、原始再帰関数の記事の命題「素数の判定と $n$ 番目の素数」の $p(i)$ と冪・積に、同じ記事の命題「有界な和・積・量化・最小化」の有界最小化・有界積・場合分けを施して書ける。

詳しい証明を開く

1：$\operatorname{ex}(i,c):=\mu z< c\ \bigl(p(i)^{z+1}\nmid c\bigr)$ とおく。$c\ge1$ で $p(i)^z$ が $c$ を割る最大の $z$ を $z_0$ とすると、$z< z_0$ では $p(i)^{z+1}\mid c$、$z=z_0$ では $p(i)^{z_0+1}\nmid c$ であり、$z_0< 2^{z_0}\le p(i)^{z_0}\le c$ なので $z_0$ は上界 $c$ より小さい。よって $\operatorname{ex}(i,c)=z_0$ で、$(c)_i=\operatorname{ex}(i,c)\dot-1$ である。$c=0$ では上界が $0$ なので値は $0$ で、約束と一致する。同様に $\operatorname{lh}(c)=\mu i< c\ \bigl(p(i)\nmid c\bigr)$ である。$c\ge1$ で $p(0),\dots,p(k-1)$ が $c$ を割り $p(k)$ が割らないとき、$c\ge p(0)\cdots p(k-1)\ge2^k>k$ なので最小の $i$ は $k$ で、上界より小さい。整除関係と冪は原始再帰的なので、有界最小化により 1 の関数は原始再帰関数である。

2・3：$\operatorname{app}$ と $\langle x,y,z,w\rangle$ は 1 の関数・$p$・冪・積の合成、$\operatorname{init}$ と $\operatorname{ones}$ は有界積に上界 $\operatorname{lh}(c)\dot-1$、$n$ を合成したもの、$\operatorname{last}$ は条件 $\operatorname{lh}(c)\ge1$ による場合分けである。列の符号についての等式は、素因数分解の一意性から $\operatorname{lh}$ と $(c)_i$ の値を読めば確かめられる。$\square$

様相の符号

様相 $C=(q,\tau,h)$ に対し、自然数 $k$ が $C$ を表すとは、ある $m,m'\ge0$ について
$$ k=\bigl\langle q,\ \langle\tau(h-m),\dots,\tau(h-1)\rangle,\ \tau(h),\ \langle\tau(h+m'),\dots,\tau(h+1)\rangle\bigr\rangle $$
であり、$i< h-m$ と $i>h+m'$ ではすべて $\tau(i)=0$（空白）となることをいう。左右の列はどちらも、ヘッドに近いマスほど後ろに並ぶ。

テープの内容は有限個のマスを除いて空白なので、どの様相にもそれを表す数がある（$m,m'$ を大きくとれば、表す数は 1 つに限らない）。

1 ステップの関数

番号 $e$ と自然数 $q,a$ に対し、$J(e,q,a):=\mu j<\operatorname{lh}(e)\ \bigl(j\ge1\land((e)_j)_0=q\land((e)_j)_1=a\bigr)$ とおく。条件を満たす $j$ がなければ $J(e,q,a)=\operatorname{lh}(e)$ である。
$k$ に対し $q=(k)_0$、$\ell=(k)_1$、$a=(k)_2$、$r=(k)_3$、$j=J(e,q,a)$ とおく。$j=\operatorname{lh}(e)$ なら $\operatorname{step}(e,k):=k$ とする。$j<\operatorname{lh}(e)$ なら $t=(e)_j$、$q'=(t)_2$、$b=(t)_3$、$d=(t)_4$ として
$$ \operatorname{step}(e,k):=\begin{cases} \bigl\langle q',\ \operatorname{init}(\ell),\ \operatorname{last}(\ell),\ \operatorname{app}(r,b)\bigr\rangle&(d=0),\ \bigl\langle q',\ \operatorname{app}(\ell,b),\ \operatorname{last}(r),\ \operatorname{init}(r)\bigr\rangle&(d=1),\ \langle q',\ \ell,\ b,\ r\rangle&(d\ge2) \end{cases} $$
と定める。さらに $\operatorname{Hlt}(e,k)$ を関係「$J(e,(k)_0,(k)_2)=\operatorname{lh}(e)$」とする。

$d=0$ の場合を読むと、ヘッドが 1 マス左へ動くので、左の列の最後の記号が新しくヘッドの下に来て左の列から外れ、いま書いた記号 $b$ が右の列のいちばん後ろ（ヘッドのすぐ右）に入る。$d=1$ はその左右を入れ替えたものである。

1 ステップの関数の正しさ

$\operatorname{step}$ は原始再帰関数、$\operatorname{Hlt}$ は原始再帰的な関係である。$k$ が $M_e$ の様相 $C$ を表すとき、$\operatorname{Hlt}(e,k)$ は $C$ が停止様相であることと同値である。$C$ が停止様相でなければ $\operatorname{step}(e,k)$ は $C$ の次の様相を表し、停止様相なら $\operatorname{step}(e,k)=k$ である。

$J$ は lem-utm-sequence-ops の関数への有界最小化、$\operatorname{step}$ は条件 $j=\operatorname{lh}(e)$ と $d=0$、$d=1$ による場合分けなので、原始再帰関数の記事の命題「有界な和・積・量化・最小化」の 4・5 により原始再帰的である。
$k$ が $C=(q,\tau,h)$ を表すとき $(k)_0=q$、$(k)_2=\tau(h)$ なので、$J(e,q,\tau(h))<\operatorname{lh}(e)$ であることは $(q,\tau(h))$ に合う命令があること、すなわち def-utm-index の 2 により $\delta(q,\tau(h))$ が定義されることと同値である。よって $\operatorname{Hlt}(e,k)$ は $C$ が停止様相であることと同値で、そのとき定義により $\operatorname{step}(e,k)=k$ である。
停止様相でないとき：$d=0$（左へ動く）なら、左の列の最後の記号が新しいヘッドの下の記号になり、書いた記号 $b$ が右の列の最後に入るので、$\operatorname{step}(e,k)$ は次の様相を表す。$d=1$ は左右を入れ替えた同じ議論であり、$d\ge2$ ではヘッドが動かず、ヘッドの下の記号が $b$ に替わるだけである。

$d=0$ の場合の詳細を開く

停止様相でないとし、使う命令の成分を $q',b,d$ とする。$d=0$（左へ動く）の場合を示す。次の様相は $(q',\tau',h-1)$ で、$\tau'(h)=b$、それ以外では $\tau'=\tau$ である。$\ell=\langle\tau(h-m),\dots,\tau(h-1)\rangle$、$r=\langle\tau(h+m'),\dots,\tau(h+1)\rangle$ とする。

$m\ge1$ のとき：lem-utm-sequence-ops により $\operatorname{last}(\ell)=\tau(h-1)=\tau'(h-1)$、$\operatorname{init}(\ell)=\langle\tau'(h-1-(m-1)),\dots,\tau'(h-2)\rangle$ である。$m=0$ のとき：$\operatorname{last}(\ell)=0$、$\operatorname{init}(\ell)=\langle\,\rangle$ であり、$i< h$ で $\tau(i)=0$ なので $\tau'(h-1)=0$ で、$i< h-1$ でも $\tau'(i)=0$ である。どちらの場合も、新しいヘッドの位置 $h-1$ から見た左の列とヘッドの下の記号が正しい。
$\operatorname{app}(r,b)=\langle\tau'(h+m'),\dots,\tau'(h+1),\tau'(h)\rangle$ は、位置 $h-1$ から見て右の $m'+1$ マスを、遠い順に並べたものである。

$i<(h-1)-(m-1)=h-m$ と $i>(h-1)+(m'+1)$ で $\tau'(i)=0$ なので（$m=0$ の場合は $i< h-1$ で $0$）、$\operatorname{step}(e,k)$ は次の様相を表す。$\square$

万能関数は μ再帰関数である

計算を $s$ ステップ進めた様相の符号を、原始再帰で定める。
$$ \operatorname{conf}(e,x,0):=\bigl\langle(e)_0,\ \langle\,\rangle,\ \operatorname{sg}(x),\ \operatorname{ones}(x\dot-1)\bigr\rangle,\qquad \operatorname{conf}(e,x,s+1):=\operatorname{step}\bigl(e,\operatorname{conf}(e,x,s)\bigr). $$
$\operatorname{conf}(e,x,0)$ は入力 $x$ の初期様相を表す。$x=0$ ならテープはすべて空白で、ヘッドの下は $\operatorname{sg}(0)=0$、右の列は空である。$x\ge1$ ならヘッドの下（$0$ 番目のマス）は $1$、その右に $1$ が $x-1$ 個並び、ほかは空白である。
停止したときのテープの形と出力も、符号から読み取れる。$k$ に対し $\ell=(k)_1$、$r=(k)_3$、$n=\operatorname{lh}(r)$ とし、ヘッドから右へ読んだ記号の列を $w(k,0):=(k)_2$、$w(k,i):=(r)_{n-i}$（$1\le i\le n$）とおく。

$\operatorname{W}(k)$：「$\ell$ の項がすべて $0$ であり、$w(k,0),\dots,w(k,n)$ がすべて $0$ か $1$ で、$i< i'\le n$ かつ $w(k,i)=0$ なら $w(k,i')=0$」という関係。
$\operatorname{Out}(k):=\sum_{i\le n}w(k,i)$。
$k$ が様相 $(q,\tau,h)$ を表すとき、$\operatorname{W}(k)$ は「ある $y$ で $\tau(h+i)=1$（$0\le i< y$）、それ以外では空白」と同値であり、そのとき $y=\operatorname{Out}(k)$ である。左の列より左と右の列より右は空白なので、テープの形は左の列と $w(k,0),\dots,w(k,n)$ だけで決まるからである。$w$ と $\operatorname{Out}$ は lem-utm-sequence-ops の関数の合成と有界和、$\operatorname{W}$ は有界量化で書けるので、どれも原始再帰的である。

万能関数の標準形

$T(e,x,s)$ を関係「$\operatorname{Hlt}(e,\operatorname{conf}(e,x,s))$ かつ $\operatorname{W}(\operatorname{conf}(e,x,s))$」とする。$T$ は原始再帰的な関係で、すべての $e,x$ について
$$ u(e,x)\simeq\operatorname{Out}\Bigl(\operatorname{conf}\bigl(e,x,\ \mu s\,T(e,x,s)\bigr)\Bigr) $$
が成り立つ。とくに万能関数 $u$ は μ再帰関数である。

$\operatorname{conf}$ は lem-utm-sequence-ops の関数と $\operatorname{sg}$ の合成を初期値とし、lem-utm-step の原始再帰関数 $\operatorname{step}$ による原始再帰で定まるので原始再帰関数であり、$T$ は原始再帰的な関係である。
段 1（$\operatorname{conf}$ は計算をなぞる）． $e,x$ を固定し、$M_e$ の入力 $x$ からの計算を $C_0,C_1,\dots$ とする（Turing機械の記事の命題「計算の一意性」により、ただ 1 通りに定まる）。$s$ についての帰納法で次を示す：$C_s$ が存在するなら $\operatorname{conf}(e,x,s)$ は $C_s$ を表し、計算が $C_n$（$n< s$）で停止するなら $\operatorname{conf}(e,x,s)=\operatorname{conf}(e,x,n)$ である。$s=0$ は上で確かめた。$s$ で成り立つとする。$C_s$ が存在して停止様相でないなら、lem-utm-step により $\operatorname{conf}(e,x,s+1)$ は次の様相 $C_{s+1}$ を表す。$C_s$ が停止様相なら、lem-utm-step により $\operatorname{conf}(e,x,s+1)=\operatorname{conf}(e,x,s)$ である。すでに $C_n$（$n< s$）で停止しているなら、帰納法の仮定の $\operatorname{conf}(e,x,s)=\operatorname{conf}(e,x,n)$ は停止様相 $C_n$ を表すので、同じく $\operatorname{conf}(e,x,s+1)=\operatorname{conf}(e,x,n)$ である。
段 2（場合分け）． 3 つの場合に分ける。

$M_e$ が $C_n$ で停止し、そのテープが形の正しい $1^y$ のとき：$s< n$ では $C_s$ は停止様相でないので、lem-utm-step により $\operatorname{Hlt}(e,\operatorname{conf}(e,x,s))$ は成り立たない。$s=n$ では $\operatorname{Hlt}$ と $\operatorname{W}$ がともに成り立つ。よって $\mu s\,T(e,x,s)=n$ であり、右辺の値は $\operatorname{Out}(\operatorname{conf}(e,x,n))=y=u(e,x)$ である。
$M_e$ が $C_n$ で停止するが、テープの形が正しくないとき：$s< n$ では $\operatorname{Hlt}$ が成り立たず、$s\ge n$ では段 1 により $\operatorname{conf}(e,x,s)$ は $C_n$ を表すので $\operatorname{W}$ が成り立たない。よって $T(e,x,s)$ となる $s$ はなく、右辺は定義されない。左辺 $u(e,x)$ も定義されない。
$M_e$ が停止しないとき：どの $s$ でも $C_s$ は停止様相でないので $T(e,x,s)$ は成り立たず、両辺とも定義されない。
μ 作用素を施す $1\mathbin{\dot-}\chi_T$ は全域的なので、$\mu s\,T(e,x,s)$ は μ再帰関数の記事の定義「部分関数の合成・原始再帰・μ 作用素」の μ 作用素で得られる。右辺は原始再帰関数への μ 作用素と合成で作られるので、$u$ は μ再帰関数である。$\square$

この定理は、μ再帰関数の記事の定理「Kleene の標準形定理」を、Turing 機械の番号付けについて具体的に実行したものにあたる。上界のない探索 $\mu s$ は 1 回だけで、その中身はすべて原始再帰的である。「正しく停止した計算の段数を探し、見つかったらその時点のテープを読む」ことが、計算の全体をなぞる唯一の部分である。

万能 Turing 機械の存在

万能 Turing 機械が存在する。すなわち、すべての $e,x$ について、入力 $(e,x)$ から始めて $u(e,x)$ が定義されれば値 $u(e,x)$ を出力して停止し、定義されなければ停止しない Turing 機械 $U$ がある。とくに、1 変数の Turing 計算可能な部分関数 $f$ には、すべての $x$ で $f(x)\simeq u(e,x)$ となる番号 $e$ があり、$U$ は入力 $(e,x)$ に対して $f(x)$ を計算する。

thm-utm-normal-form により $u$ は 2 変数の μ再帰関数である。ここで次の事実を使う：Turing 計算可能な部分関数の全体と μ再帰関数（部分関数を含む）の全体は一致する。両向きとも成り立ち、変数の個数は任意である（Gal15 §7.7.1、p. 355。全域関数については Bil03 Theorem 13.14（p. 92）、Theorem 14.8・Corollary 14.9（p. 97）。Turing機械の記事の節「変種と頑健性」にも挙げてある。この記事では証明しない）。この一致の「μ再帰関数は Turing 計算可能である」向きにより、$u$ を計算する機械 $U$ がある。後半は lem-utm-every-machine と、def-utm-universal-function の後の注意（$M$ が $f$ を計算するなら $\operatorname{out}_M=f$）による。$\square$

$U$ を実際に状態と遷移の表として書き下すこともできる。そのような機械は、テープ上の番号を読み、模倣している機械の状態・左右の列・ヘッドの下の記号をテープの別の場所に記録し、def-utm-step の場合分けを 1 回ずつ実行する動きをする。上の証明は、この動きを原始再帰関数の言葉で書き、関数と機械の一致に委ねたものである。書き下し方の概略は OLT26 Theorem 32.3（pp. 499–501）にあり、同書はそこで Church–Turing のテーゼを使っている。番号付けと 1 ステップの関数が原始再帰的であることから万能機械を得る上の道筋は、Bil03 第 14 章の Problem 14.10・14.11、Proposition 14.12、Corollary 14.13（pp. 97–98）と同じ考え方である。
thm-utm-existence と thm-utm-normal-form から、1 変数の Turing 計算可能な部分関数の全体は $\{u(e,\cdot)\mid e\in\mathbb{N}\}$ に一致する。各 $u(e,\cdot)$ は、$e$ を定数として代入した μ再帰関数なので、thm-utm-existence の証明で引いた一致（μ再帰関数は Turing 計算可能である向き）により Turing 計算可能だからである。また lem-utm-every-machine により、どの関数も無限個の番号 $e$ で現れる。

万能関数は全域的に延長できない

万能機械 $U$ は、模倣する機械が停止しなければ自分も停止しない。これは作り方の不備ではなく、避けられない。

万能関数の全域的な延長の不存在

2 変数の全域的な Turing 計算可能関数 $g\colon\mathbb{N}^2\to\mathbb{N}$ で、$u(e,x)$ が定義されるすべての $(e,x)$ について $g(e,x)=u(e,x)$ となるものは存在しない。

そのような $g$ があったとし、$d(x):=g(x,x)+1$ とおく。$g$ は Turing 計算可能なので μ再帰関数である（thm-utm-existence の証明で引いた一致の逆向き、Turing 計算可能な関数は μ再帰関数であるという向きによる。この記事では証明しない）。$d$ は $g$ と後者関数の合成なので全域的な μ再帰関数であり、同じ一致の「μ再帰関数は Turing 計算可能である」向きにより Turing 計算可能である。thm-utm-existence の後半により、すべての $x$ で $d(x)\simeq u(e,x)$ となる番号 $e$ がある。$d$ は全域的なので $u(e,e)=d(e)$ は定義され、$g$ が $u$ の延長であることから $g(e,e)=u(e,e)=d(e)=g(e,e)+1$ となって矛盾する。$\square$

$u(e,x)$ そのもの（部分関数）では同じ議論は矛盾しない。$d(x):\simeq u(x,x)+1$ は μ再帰関数で、ある番号 $e$ で $d=u(e,\cdot)$ となるが、$d(e)\simeq u(e,e)+1\simeq d(e)+1$ は、$d(e)$ が定義されないことを示すだけである（μ再帰関数の記事の定理「全域再帰関数の普遍関数の不存在」の後の注意と同じ現象）。
この定理から、「$U$ が入力 $(e,x)$ で停止するかどうか」を判定する Turing 機械はないことが分かる。判定できれば、停止しないところでは $0$ を返し、停止するところでは $U$ を最後まで動かして出力を返す全域的な延長が計算できてしまうからである。式で書けば、停止するとき $1$、しないとき $0$ をとる関数 $H$ が Turing 計算可能なら、$H$ は μ再帰関数であり（thm-utm-existence の証明で引いた一致の逆向き。この記事では証明しない）、$g(e,x):=H(e,x)\cdot\operatorname{Out}\bigl(\operatorname{conf}(e,x,\ \mu s\,[\,T(e,x,s)\lor H(e,x)=0\,])\bigr)$ は全域的な μ再帰関数で $u$ を延長し、一致の「μ再帰関数は Turing 計算可能である」向きにより Turing 計算可能になって thm-utm-no-total-extension に反する。これが停止問題の決定不能性の一つの形である（OLT26 Lemma 32.7・Theorem 32.8、pp. 501–502 は別の形で述べている）。

仮定を外したときの反例

外す条件	反例	成り立たなくなること
万能関数が部分関数であること	$u$ の全域的な延長 $g$	計算可能であること（thm-utm-no-total-extension）
上界のない探索 $\mu s$ を使うこと	原始再帰関数だけで作った 2 変数関数 $v$	1 変数の原始再帰関数をすべて $v(e,\cdot)$ として並べること
番号から機械の動作を計算で読み取れること	計算できない集合 $S$ を埋め込んだ番号付け $\nu_S$	万能 Turing 機械の存在

反例の確かめ

1 行目は thm-utm-no-total-extension そのものである。
2 行目：2 変数の原始再帰関数 $v$ で、どの 1 変数の原始再帰関数 $f$ にもすべての $x$ で $f(x)=v(e,x)$ となる $e$ があるものは存在しない。実際、$d(x):=v(x,x)+1$ は原始再帰関数なので $d=v(e,\cdot)$ となる $e$ があり、$v(e,e)+1=d(e)=v(e,e)$ となって矛盾する。原始再帰関数は全域的なので、部分関数の場合のように矛盾が「値をもたない」ことに吸収されない。すべての原始再帰関数を番号付けて計算する関数は、計算できるとしても原始再帰関数の外にある。
3 行目：Turing 計算可能な 1 変数関数は可算個しかない（Turing機械の記事の定理「Turing 計算可能でない関数の存在」の 1）ので、特性関数 $\chi_S$ が Turing 計算可能でない集合 $S\subset\mathbb{N}$ がある。$c_0,c_1$ を定数関数 $0,1$ を計算する機械の番号とし、機械の番号付け $\nu_S$ を $\nu_S(2n):=M_{c_0}$（$n\in S$ のとき）、$\nu_S(2n):=M_{c_1}$（$n\notin S$ のとき）、$\nu_S(2n+1):=M_n$ と定める。どの機械も $\nu_S$ のどこかに現れる。この番号付けでの万能関数 $u_S(m,x):\simeq\operatorname{out}_{\nu_S(m)}(x)$ を計算する機械があったとすると、$u_S$ は μ再帰関数であり（thm-utm-existence の証明で引いた一致の逆向き、Turing 計算可能な部分関数は μ再帰関数であるという向きによる。この記事では証明しない）、$n\mapsto1\mathbin{\dot-}u_S(2n,0)=\chi_S(n)$ は $u_S$ と原始再帰関数の合成なので全域的な μ再帰関数になり、同じ一致の「μ再帰関数は Turing 計算可能である」向きにより Turing 計算可能になって $S$ の選び方に反する。

3 行目が示すように、万能機械に必要なのは「番号から命令を取り出し、1 ステップを実行する」操作が計算できることである。def-utm-index の番号付けでは、この操作が原始再帰関数で書けた（lem-utm-step）。逆に、別の番号付け $\nu$ について、各 $m$ に「$\nu(m)$ と同じ出力関数をもつ機械の、def-utm-index での番号 $t(m)$」を対応させる全域的な Turing 計算可能関数 $t$ があれば、$t$ は μ再帰関数であり（thm-utm-existence の証明で引いた一致の逆向き。この記事では証明しない）、$(m,x)\mapsto u(t(m),x)$ は μ再帰関数の合成なので、一致の「μ再帰関数は Turing 計算可能である」向きにより $\nu$ についても万能機械が存在する。

補足

プログラム内蔵の考え方. 番号 $e$ をテープに書き込めば同じ機械 $U$ が別の計算をするという性質は、プログラムをデータとして記憶装置に置く計算機の考え方にあたる。Bil03 第 14 章（p. 95）も、万能機械を「ほかの機械をソフトウェアとして扱う 1 台のハードウェア」と説明している。
Church–Turing のテーゼとの関係. thm-utm-existence の証明はテーゼを使わず、μ再帰関数と Turing 計算可能関数の一致（定理）を使っている。テーゼは「直観的に計算できる」という定義されていない概念を含むので、証明の中では使わない（Church–Turingのテーゼ）。