Kleeneの再帰定理

同義語：Kleene's recursion theoremクリーネの再帰定理Kleeneの第2再帰定理

概要

前提知識: 計算可能関数, s-m-n定理, 停止問題

停止問題の決定不能性の証明では、番号 $e$ のプログラムに自分の番号 $e$ を入力として与え、矛盾を導いた。Kleene の再帰定理（Kleene's recursion theorem）は、この自己言及が矛盾のためだけのものではないことを示す。どんな部分計算可能関数 $g(x,y)$ を与えても、「入力 $y$ に対して、自分の番号 $e$ を使って $g(e,y)$ を計算する」プログラム $e$ が存在する。プログラムは自分自身の符号を知っているかのように書いてよい、ということである。
この定理から、自分自身を出力するプログラムの存在、任意の計算可能な番号の変換 $f$ に対して $\varphi_e=\varphi_{f(e)}$ となる番号 $e$ の存在（不動点の形）、自分自身を呼び出す定義による部分計算可能関数の構成が得られる。Riceの定理も不動点の形から直ちに従う。この記事では、定理とそのパラメータ付きの形を証明し、不動点が無限個あることと、いくつかの応用を示す。
名前の似た Kleeneの不動点定理は、ω完備半順序集合の上の ω連続写像の最小不動点についての定理で、この記事の定理とは別のものである。自然数の上の再帰的な定義（初期値と規則による写像の定義）を正当化する再帰定理とも別のものである。

記法と前提

$\mathbb{N}=\{0,1,2,\dots\}$ とする。部分関数 $f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ について、$f(\vec x)$ が定義されることを $f(\vec x)\!\downarrow$、されないことを $f(\vec x)\!\uparrow$ と書き、$\alpha\simeq\beta$ は「両辺とも定義されて等しいか、両辺とも定義されない」ことを表す。部分計算可能・計算可能（全域的）・決定可能・半決定可能の意味は計算可能関数の定義「計算可能関数」に従う。部分計算可能関数は合成と μ 作用素で閉じており、合成は内側の値がすべて定義されるときにだけ定義される。
番号付けは計算可能関数の定義「標準の番号付け」の $\varphi^{(k)}_e$（$k$ 変数、$\varphi_e:=\varphi^{(1)}_e$）に固定し、$k\le3$ について次の事実を使う。

(N1)．部分関数 $f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ が部分計算可能であることは、ある $e$ で $f=\varphi^{(k)}_e$ となることと同値である。
(N2)．$(e,\vec x)\mapsto\varphi^{(k)}_e(\vec x)$ は部分計算可能である。
(N3)．1 変数の部分計算可能関数はどれも無限個の番号をもつ。
(N4)．$m,n\ge1$、$m+n\le3$ とする。$m+n$ 変数の部分計算可能関数 $g$ に対し、計算可能関数 $h\colon\mathbb{N}^m\to\mathbb{N}$ があって、すべての $\vec a\in\mathbb{N}^m$、$\vec y\in\mathbb{N}^n$ について $\varphi^{(n)}_{h(\vec a)}(\vec y)\simeq g(\vec a,\vec y)$ が成り立つ。
(N1)・(N2) は計算可能関数の命題「番号付けは部分計算可能関数をすべて並べる」、(N3) はその後の段落、(N4) は s-m-n定理の定理「s-m-n 定理」（$n=1$ の場合は同じ記事の系「引数の取り込み」）である。(N4) は「引数 $\vec a$ を埋め込んだプログラムの番号を、$\vec a$ から計算できる」ことを述べている。
$W_e:=\{y\mid\varphi_e(y)\!\downarrow\}$ とおき、自己停止集合を $K:=\{e\mid\varphi_e(e)\!\downarrow\}$ とする。

主定理

Kleene の再帰定理

任意の 2 変数の部分計算可能関数 $g$ に対し、番号 $e$ があって、すべての $y$ について
$$ \varphi_e(y)\simeq g(e,y) $$
が成り立つ。

対角線の上に対角線を置く

$(x,y)\mapsto\varphi^{(2)}_x(x,y)$ は (N2) の関数と代入の合成なので部分計算可能である。(N4)（$m=n=1$）により計算可能関数 $\delta$ で、すべての $x,y$ について
$$ \varphi_{\delta(x)}(y)\simeq\varphi^{(2)}_x(x,y) $$
となるものがある。次に $l(x,y):\simeq g(\delta(x),y)$ は部分計算可能関数の合成なので部分計算可能であり、(N1) により $l=\varphi^{(2)}_d$ となる $d$ がある。$e:=\delta(d)$ とおくと、すべての $y$ について
$$ \varphi_e(y)\simeq\varphi_{\delta(d)}(y)\simeq\varphi^{(2)}_d(d,y)\simeq l(d,y)\simeq g(\delta(d),y)\simeq g(e,y) $$
である。$\square$

$\delta(x)$ は「2 変数のプログラム $x$ の最初の引数に、$x$ 自身を入れたプログラム」の番号であり、対角線論法の対角線に当たる。プログラム $d$ は「受け取った番号 $x$ を $\delta$ で対角線に移し、それを $g$ に渡す」もので、その $d$ をさらに対角線に置いた $\delta(d)$ では、実行されるプログラムと $g$ に渡される番号が一致する。

自分を参照するプログラム

自分の番号を出力するプログラム．$g(x,y):=x$ に thm-krt-main を使うと、すべての $y$ について $\varphi_e(y)=e$ となる $e$ がある。入力を無視して自分自身の符号を出力するプログラムであり、プログラミング言語では「自分自身のソースコードを出力するプログラム」（quine）にあたる。
自分の番号だけで停止するプログラム．$g(x,y):\simeq\mu z\,[\,(y\mathbin{\dot-}x)+(x\mathbin{\dot-}y)=0\,]$ は、$y=x$ なら $0$、$y\neq x$ なら定義されない（μ の条件が $z$ によらず偽）。thm-krt-main の $e$ について $\varphi_e(e)=0$ であり、$W_e=\{e\}$ である。
自分の番号を足すプログラム．$g(x,y):=x+y$ から、すべての $y$ で $\varphi_e(y)=e+y$ となる $e$ がある。

2 から、自己停止集合 $K$ は指数集合（$\varphi_a=\varphi_b$ なら $a,b$ が同時に属するか同時に属さない集合）でないことが分かる。

詳細

2 の $e$ をとる。(N3) により $\varphi_b=\varphi_e$、$b\neq e$ となる $b$ がある。$\varphi_e(e)\!\downarrow$ なので $e\in K$ であり、$\varphi_b(b)=\varphi_e(b)$ は $b\neq e$ なので定義されず、$b\notin K$ である。

不動点の形

番号を番号へ移す計算可能な変換 $f$ を「プログラムの書き換え」とみなすと、どんな書き換えにも、書き換えても計算する関数が変わらないプログラムがある。

不動点の形

任意の計算可能関数 $f\colon\mathbb{N}\to\mathbb{N}$ に対し、$\varphi_e=\varphi_{f(e)}$ となる番号 $e$ がある。

$g(x,y):\simeq\varphi_{f(x)}(y)$ は (N2) の関数と $f$ の合成なので部分計算可能である。thm-krt-main の $e$ について、すべての $y$ で $\varphi_e(y)\simeq g(e,y)\simeq\varphi_{f(e)}(y)$ である。$\square$

逆に、不動点の形から thm-krt-main が出る。2 変数の部分計算可能関数 $g$ に対し、(N4) により $\varphi_{f(x)}(y)\simeq g(x,y)$ となる計算可能関数 $f$ をとり、その不動点 $e$ をとれば $\varphi_e(y)\simeq\varphi_{f(e)}(y)\simeq g(e,y)$ だからである。2 つの形は同じ定理の言い換えである（OLT26 Lemma 30.25）。
等しくなるのは番号ではなく関数である。$f(x):=x+1$ には $e=f(e)$ となる数はないが、cor-krt-fixed-point により $\varphi_e=\varphi_{e+1}$ となる $e$ はある。番号が隣り合う 2 つのプログラムが同じ関数を計算する、ということである。

不動点は無限個ある

任意の計算可能関数 $f\colon\mathbb{N}\to\mathbb{N}$ に対し、$\varphi_e=\varphi_{f(e)}$ となる番号 $e$ は無限個ある。したがって、任意の 2 変数の部分計算可能関数 $g$ に対し、すべての $y$ で $\varphi_e(y)\simeq g(e,y)$ となる $e$ も無限個ある。

有限個の番号を避ける

$N\in\mathbb{N}$ を任意にとり、$e>N$ となる不動点があることを示す。定数関数 $y\mapsto0,\ y\mapsto1,\ \dots,\ y\mapsto N+1$ は互いに異なる $N+2$ 個の部分計算可能関数なので、そのうち少なくとも 1 つは $\varphi_0,\dots,\varphi_N$ のどれとも異なる。その関数の番号を $a$ とし、
$$ f'(x):=\begin{cases}a&(x\le N),\\ f(x)&(x>N)\end{cases} $$
とおく。$f'$ は計算可能なので、cor-krt-fixed-point により $\varphi_e=\varphi_{f'(e)}$ となる $e$ がある。$e\le N$ なら $\varphi_e=\varphi_a$ となるが、$\varphi_a$ は $\varphi_0,\dots,\varphi_N$ のどれとも異なるので矛盾する。よって $e>N$ であり、$\varphi_e=\varphi_{f'(e)}=\varphi_{f(e)}$ である。
後半は、(N4) により $\varphi_{f(x)}(y)\simeq g(x,y)$ となる計算可能関数 $f$ をとり、前半を使えばよい。$\square$

パラメータ付きの形

不動点を、パラメータ $z$ から計算で求めることもできる。

パラメータ付きの再帰定理

任意の 3 変数の部分計算可能関数 $g$ に対し、計算可能関数 $p\colon\mathbb{N}\to\mathbb{N}$ があって、すべての $z,y$ について
$$ \varphi_{p(z)}(y)\simeq g\bigl(p(z),z,y\bigr) $$
が成り立つ。

prf-krt-main の $\delta$（$\varphi_{\delta(x)}(y)\simeq\varphi^{(2)}_x(x,y)$）を使う。$G(z,x,y):\simeq g(\delta(x),z,y)$ は 3 変数の部分計算可能関数なので、(N4)（$m=1$、$n=2$）により計算可能関数 $l$ で、すべての $z,x,y$ について $\varphi^{(2)}_{l(z)}(x,y)\simeq G(z,x,y)$ となるものがある。$p(z):=\delta(l(z))$ とおくと、$p$ は計算可能で、
$$ \varphi_{p(z)}(y)\simeq\varphi^{(2)}_{l(z)}\bigl(l(z),y\bigr)\simeq G\bigl(z,l(z),y\bigr)\simeq g\bigl(\delta(l(z)),z,y\bigr)\simeq g\bigl(p(z),z,y\bigr) $$
である。$\square$

thm-krt-main の証明では $d$ を (N1) で「とった」が、ここではそれを (N4) で $z$ から計算している。そのため不動点 $p(z)$ が $z$ の計算可能関数になる。

応用

自分を呼び出す定義

プログラムの中で自分自身を呼び出して関数を定義することは、再帰定理によって正当化される。

階乗を自己参照で定義する

2 変数の部分計算可能関数 $(x,y)\mapsto1$ と $(x,y)\mapsto y\cdot\varphi_x(y\mathbin{\dot-}1)$ の番号をそれぞれ $c_1,c_2$ とし（(N1)・(N2)）、
$$ j(y):=\begin{cases}c_1&(y=0),\\ c_2&(y\ge1),\end{cases}\qquad g(x,y):\simeq\varphi^{(2)}_{j(y)}(x,y) $$
とおく。$j$ は計算可能なので、$g$ は (N2) の関数と $j$ の合成として部分計算可能であり、$g(x,0)=1$、$y\ge1$ では $g(x,y)\simeq y\cdot\varphi_x(y-1)$ である。thm-krt-main の $e$ をとると
$$ \varphi_e(0)=1,\qquad\varphi_e(y)\simeq y\cdot\varphi_e(y-1)\quad(y\ge1) $$
であり、$y$ についての帰納法で、すべての $y$ について $\varphi_e(y)$ が定義されて $y!$ に等しいことが分かる。

場合分けの両方に部分関数が現れるときは、このように「どちらの番号で計算するか」を計算可能関数 $j$ で選び、(N2) の関数に渡す。分岐しない側の計算が止まらなくても、結果に影響しない。
自己参照の式が関数を 1 つに決めるとは限らない。$g(x,y):\simeq\varphi_x(y)$ では、式 $\varphi_e(y)\simeq\varphi_e(y)$ がどの $e$ でも成り立つ。ex-krt-factorial で関数が決まったのは、式の右辺が $y$ より小さい入力での値だけを使い、帰納法が使えたからである。自己参照による定義の一般の形と例は OLT26 §30.23（pp. 471–472）にある。

番号から性質を読み取れないこと

決定可能な定義域の特性関数は番号から求まらない

部分計算可能関数 $f$ で、「$W_e$ が決定可能なら、$f(e)$ が定義されて $\varphi_{f(e)}$ が $W_e$ の特性関数になる」という性質をもつものはない（OLT26 Theorem 30.27、p. 471）。

詳細

部分計算可能関数 $f$ を任意にとり、$g(x,y):\simeq\mu z\,[\,y+\varphi_{f(x)}(0)=0\,]$ とおく。$g$ は (N2) の関数と $f$ の合成に μ 作用素を施したもので部分計算可能であり、$g(x,y)$ は、$y=0$ かつ $f(x)$ と $\varphi_{f(x)}(0)$ が定義されて $\varphi_{f(x)}(0)=0$ のときに $0$ をとり、それ以外では定義されない（μ の条件が $z$ によらないので、偽なら探索は止まらない）。thm-krt-main の $e$ をとると $W_e\subset\{0\}$ なので、$W_e$ は有限集合で決定可能である。$f(e)$ と $\varphi_{f(e)}(0)$ が定義されて $\varphi_{f(e)}(0)=0$ なら $W_e=\{0\}$ であり、特性関数の $0$ での値は $1$ のはずだが $\varphi_{f(e)}(0)=0$ である。そうでなければ $W_e=\emptyset$ であり、特性関数の $0$ での値は $0$ のはずだが、$f(e)$ か $\varphi_{f(e)}(0)$ が定義されないか、$\varphi_{f(e)}(0)\neq0$ である。どちらの場合も $f$ は性質をもたない。

番号の大小についての問いにも、不動点の形が効く。番号 $e$ が 最小の番号 であるとは、$e'< e$ となるどの $e'$ でも $\varphi_{e'}\neq\varphi_e$ であることとし、最小の番号の全体を $\mathrm{MIN}$ と書く。部分計算可能関数はどれも最小の番号をただ 1 つもち、関数ごとに異なるので、$\mathrm{MIN}$ は無限集合である。

最小の番号の集合

$\mathrm{MIN}$ の無限部分集合で半決定可能なものはない。とくに $\mathrm{MIN}$ は半決定可能でない。

先回りする番号

$A\subset\mathrm{MIN}$ が無限で半決定可能だとする。計算可能関数の定理「無限集合の枚挙」の 1 により、単射な計算可能関数 $a\colon\mathbb{N}\to\mathbb{N}$ で $A=a(\mathbb{N})$ となるものがある。$A$ は無限なので、各 $x$ に対し $a(k)>x$ となる $k$ があり、
$$ f(x):=a\bigl(\mu k\,[\,a(k)>x\,]\bigr) $$
は計算可能関数で、$f(x)>x$ かつ $f(x)\in\mathrm{MIN}$ である。cor-krt-fixed-point により $\varphi_e=\varphi_{f(e)}$ となる $e$ をとると、$e< f(e)$ で $\varphi_e=\varphi_{f(e)}$ なので、$f(e)$ は最小の番号でない。これは $f(e)\in\mathrm{MIN}$ に反する。$\square$

$f$ は「自分より大きい、$A$ に載っている番号へ書き換える」変換である。不動点 $e$ は、自分より大きい最小の番号と同じ関数を計算してしまうので、その番号の最小性を壊す。
同じ考え方で、プログラムの振る舞いについての自明でない性質はどれも決定可能でないこと（Riceの定理）も、cor-krt-fixed-point から導ける。性質を判定できると仮定して「性質をもつなら、もたないプログラムのふりをする」書き換え $f$ を作ると、その不動点で矛盾が起きる。証明は Riceの定理の節「不動点による別証明」にある。

同じ形の対角線の構成

prf-krt-main の構成は、算術の文が自分の Gödel 数について語る文を作る Gödelの不完全性定理の補題「対角化補題」（一般の理論での形は対角化補題）や、任意の項 $F$ に対し $YF$ と $F(YF)$ が $\beta$ 同値になる項 $Y$ を作る λ計算の定理「不動点定理」と同じ形をしている。いずれも「対象 $x$ を受け取って $x$ を $x$ 自身に適用する」操作を、さらにそれ自身に適用している（$\lambda$ 計算との対応は OLT26 pp. 469–470 の説明）。

反例：条件を外すと成り立たない

外す条件	反例	成り立たなくなること
$g$ が部分計算可能（thm-krt-main）	$g(x,y):=0$（$\varphi_x(y)\!\uparrow$）、$g(x,y)$ は定義されない（$\varphi_x(y)\!\downarrow$）	$\varphi_e(y)\simeq g(e,y)$ となる $e$ の存在
$f$ が計算可能（cor-krt-fixed-point）	$\varphi_a$ を定数 $0$、$\varphi_b$ をどこでも定義されない関数とし、$f(x):=a$（$\varphi_x(0)\!\uparrow$）、$f(x):=b$（$\varphi_x(0)\!\downarrow$）	$\varphi_e=\varphi_{f(e)}$ となる $e$ の存在
$f$ が全域的（cor-krt-fixed-point）	どこでも定義されない部分計算可能関数 $f$	$\varphi_e=\varphi_{f(e)}$ となる $e$ の存在

反例の確かめ

どの行も、結論の等式を満たす $e$ があると仮定して矛盾を導く。

詳細

1 行目：$\varphi_e(y)\simeq g(e,y)$ がすべての $y$ で成り立つなら、$\varphi_e(y)\!\downarrow\iff g(e,y)\!\downarrow\iff\varphi_e(y)\!\uparrow$ となって矛盾する。thm-krt-main の対偶により、この $g$ は部分計算可能でない。

2 行目：$f$ は全域的である。$\varphi_e(0)\!\uparrow$ なら $\varphi_{f(e)}=\varphi_a$ は $0$ で定義されるので $\varphi_e\neq\varphi_{f(e)}$ であり、$\varphi_e(0)\!\downarrow$ なら $\varphi_{f(e)}=\varphi_b$ は $0$ で定義されないので $\varphi_e\neq\varphi_{f(e)}$ である。cor-krt-fixed-point の対偶により $f$ は計算可能でない。

3 行目：$f(e)$ がどの $e$ でも定義されないので、$\varphi_{f(e)}$ という関数がない。部分計算可能な $f$ については、「$f(e)$ が定義されるなら $\varphi_e=\varphi_{f(e)}$」という弱い形しか期待できない。

参照箇所

OLT26 Chapter 30：Lemma 30.25（p. 468、2 つの形の同値）、Theorem 30.26（p. 468、再帰定理。証明は pp. 468–469）、その後の説明（pp. 469–470、自分自身を出力するプログラムと $\lambda$ 計算の不動点の項）、§30.22（p. 471、$\varphi_e(y)=e+y$ の例と Theorem 30.27）、§30.23（pp. 471–472、自己参照による関数の定義）。
prop-krt-infinite・thm-krt-param・prop-krt-min は、この記事の証明による。