計算可能性理論

同義語：computability theory再帰理論recursion theory

概要

前提知識: 計算可能関数, 停止問題, Turing機械

計算可能性理論（computability theory）は、機械的な手順で計算できる関数・判定できる集合はどれかを問い、計算できないものどうしの難しさを比べる、数理論理学の一分野である。再帰理論（recursion theory）ともよばれる。出発点は 1930 年代に「計算できる」ことの定義が与えられたことであり、Turing機械と μ再帰関数が同じ関数の全体を定めることによって、計算可能な部分関数の全体が数学の対象として確定した（Church–Turingのテーゼ）。その上で停止問題のように、答えは明確に決まっているのに計算では答えられない問題が見つかり、どの問題をどの問題に帰着できるかという比較が理論の中心になった。
この記事は分野の入口として、個々の項目の記事の役割を整理し、分野の柱になる定理を共通の枠組みで証明する。部分計算可能関数の番号付け $\varphi_0,\varphi_1,\dots$ を道具として固定し、次のことを示す。自己停止集合 $K$ は決定可能でなく、しかもすべての計算可能枚挙集合を多対一還元で受け止める完全集合である。部分計算可能関数の性質についての問いは、自明なものを除いてどれも決定できない（Rice の定理）。プログラムは自分自身の番号を使って計算できる（Kleene の再帰定理）。全域的な関数の番号の集合は、計算可能枚挙でもなく、補集合も計算可能枚挙でない。

分野の見取り図

計算可能性理論の基本事項は、次の記事に分けて置かれている。

記事	扱う内容
Turing機械	計算のモデルの定義、加法を計算する機械、計算できない関数の存在
原始再帰関数・μ再帰関数	関数の組み立てによる計算可能性の定義、Ackermann 関数
万能Turing機械	機械の番号付け、万能関数とその標準形
Church–Turingのテーゼ	計算のモデルの一致（レジスタ機械と μ再帰関数）、テーゼの主張
計算可能関数	計算可能関数と番号付け、グラフと枚挙による特徴づけ
停止問題	停止問題の決定不能性、決定可能性と半決定可能性の関係
帰納的言語	文字列の言語としての決定可能性、Chomsky 階層との関係
決定可能な理論	数学の理論が決定可能かどうか

この記事は問題どうしの関係を扱う。中心になる問いは 3 つある。どの集合が決定可能か、あるいは計算可能枚挙か。決定できない集合どうしの難しさを、還元によってどう比べるか。数学に現れる具体的な問題（論理式の妥当性、整数係数の方程式の解の存在など）は、この比較のどこに位置するか。

記法と前提

$\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$ と書き、$e_1\simeq e_2$ は「両辺とも定義されて等しいか、両辺とも定義されない」ことを表す。部分計算可能・計算可能（全域的）・決定可能・半決定可能（計算可能枚挙）の意味は計算可能関数の記事の定義「計算可能関数」に従う。
(A) 計算のモデルの一致．Turing 計算可能な部分関数と μ再帰関数は一致する（計算可能関数の記事の「記法と前提」の (A) と同じ事実で、この記事では証明しない）。したがって部分計算可能関数は、合成・原始再帰・μ 作用素で閉じている。合成 $f(g_1(\vec x),\dots,g_m(\vec x))$ は、すべての $g_i(\vec x)$ が定義されて $f$ がその値で定義されるときにだけ定義される（μ再帰関数の記事の定義「部分関数の合成・原始再帰・μ 作用素」）。
部分計算可能関数の番号付け、すなわち $e\in\mathbb{N}$ ごとの 1 変数の部分関数 $\varphi_e$ と 2 変数の部分関数 $\varphi^{(2)}_e$ の列で、次の 4 つを満たすものを 1 つ固定する。

(N1) 列挙．$k=1,2$ について、部分関数 $f\colon\mathbb{N}^k\rightharpoonup\mathbb{N}$ が部分計算可能であることは、ある $e$ で $f=\varphi^{(k)}_e$ となることと同値である（$\varphi^{(1)}_e:=\varphi_e$）。
(N2) 万能性．$(e,x)\mapsto\varphi_e(x)$ と $(e,x,y)\mapsto\varphi^{(2)}_e(x,y)$ は部分計算可能である。
(N3) 段数の関係．原始再帰的な関係 $T(e,x,s)$ があって、$\varphi_e(x)\!\downarrow\iff\exists s\ T(e,x,s)$ が成り立つ。
(N4) s-m-n 定理．計算可能関数 $\sigma\colon\mathbb{N}^2\to\mathbb{N}$ があって、すべての $e,a,y$ について $\varphi_{\sigma(e,a)}(y)\simeq\varphi^{(2)}_e(a,y)$ が成り立つ。
計算可能関数の記事の定義「標準の番号付け」は (N1)〜(N3) を満たす（同記事の命題「番号付けは部分計算可能関数をすべて並べる」と、その定義の直後の標準形の段落）。標準形 $\varphi_e(x)\simeq U(\mu s\,T(e,x,s))$ で定めた番号付けが (N1)〜(N4) を満たすことは OLT26 Theorem 30.1・30.3・30.4 にある。(N4) は、番号 $e$ と引数 $a$ から「入力の前に $a$ を書き足して番号 $e$ の計算を行う」計算の番号が計算できることを述べる。この記事では (N4) を証明しない（s-m-n 定理の証明は s-m-n定理の記事で扱う）。以下の定理のうち、prop-ct-reduction と thm-ct-k は (N1)〜(N3) だけで示され、thm-ct-k-complete、lem-ct-rice-reduction とそれを使う thm-ct-rice・cor-ct-rice-ce・thm-ct-tot、thm-ct-recursion とその系は (N4) を使う。
$W_e:=\operatorname{dom}\varphi_e=\{x\mid\varphi_e(x)\!\downarrow\}$ とおく。(N1) により、半決定可能な集合 $A\subset\mathbb{N}$ はちょうど $W_e$ の形の集合である。

定義

自己停止集合と全域性の集合

$$ K:=\{e\in\mathbb{N}\mid\varphi_e(e)\!\downarrow\},\qquad\mathrm{Tot}:=\{e\in\mathbb{N}\mid\text{すべての }y\text{ で }\varphi_e(y)\!\downarrow\} $$
とおく。$K$ を 自己停止集合、$\mathrm{Tot}$ を全域的な関数の番号の集合という。

停止問題の記事の $K$ は Turing 機械の番号による自己停止集合であり、ここでの $K$ とは番号付けが異なる。この記事の $K$ は OLT26 Theorem 30.12 の $K$ と同じ形である。

多対一還元

$A,B\subset\mathbb{N}$ とする。計算可能関数 $f\colon\mathbb{N}\to\mathbb{N}$ で、すべての $x$ について
$$ x\in A\iff f(x)\in B $$
となるものを $A$ から $B$ への 多対一還元（many-one reduction）という。そのような $f$ があるとき $A\le_{\mathrm m}B$ と書き、$A$ は $B$ に 多対一還元可能 であるという。$A\le_{\mathrm m}B$ かつ $B\le_{\mathrm m}A$ のとき $A\equiv_{\mathrm m}B$ と書く。

$A\le_{\mathrm m}B$ は「$B$ の所属を判定できれば $A$ の所属も判定できる」こと、つまり $A$ は $B$ より難しくないことを表す（OLT26 Definition 30.16）。

完全な計算可能枚挙集合

半決定可能な集合 $C\subset\mathbb{N}$ で、すべての半決定可能な集合 $B$ について $B\le_{\mathrm m}C$ となるものを、多対一還元に関して完全な計算可能枚挙集合という（OLT26 Definition 30.19）。

指数集合

$A\subset\mathbb{N}$ が、$\varphi_a=\varphi_b$ かつ $a\in A$ ならば $b\in A$ を満たすとき、$A$ を 指数集合（index set）という。部分計算可能関数の集まり $\mathcal{C}$ について
$$ I_{\mathcal{C}}:=\{e\in\mathbb{N}\mid\varphi_e\in\mathcal{C}\} $$
は指数集合である。逆に指数集合 $A$ は、$\mathcal{C}:=\{\varphi_a\mid a\in A\}$ として $A=I_{\mathcal{C}}$ と書ける。

指数集合は、番号（プログラム）の書き方ではなく、番号が計算する関数（プログラムの振る舞い）だけで決まる性質を表す。

例

還元の例

$H:=\{\langle e,x\rangle\mid\varphi_e(x)\!\downarrow\}$（$\langle\cdot,\cdot\rangle$ は計算可能な全単射 $\mathbb{N}^2\to\mathbb{N}$）とすると、$x\mapsto\langle x,x\rangle$ は $K$ から $H$ への多対一還元である。
$B$ を決定可能な集合、$A$ を $\emptyset$ でも $\mathbb{N}$ でもない集合とする。$a\in A$、$b\notin A$ をとり、$f(x):=a$（$x\in B$）、$f(x):=b$（$x\notin B$）とおくと、$f$ は計算可能で $B\le_{\mathrm m}A$ である。したがって、$\emptyset$ と $\mathbb{N}$ 以外の決定可能な集合はすべて互いに $\equiv_{\mathrm m}$ である。

指数集合の例

$\mathrm{Tot}$、$\{e\mid W_e=\emptyset\}$、$\{e\mid\varphi_e(0)=7\}$、$\{e\mid W_e\text{ は有限集合}\}$ は指数集合である。どれも $\varphi_e$ だけで決まる条件だからである。
$\{e\mid e\le 10\}$ は決定可能だが、計算可能関数の記事の番号付けや標準形で定めた番号付けでは指数集合でない。部分計算可能関数はどれも無限個の番号をもつ（OLT26 Theorem 30.2、計算可能関数の記事の命題「番号付けは部分計算可能関数をすべて並べる」の後の段落）ので、$\varphi_0$ には $10$ より大きい番号 $b$ もあり、$0$ は属するが $b$ は属さないからである。

柱になる定理

還元の基本性質

$A,B,C\subset\mathbb{N}$ とする。

$A\le_{\mathrm m}A$ であり、$A\le_{\mathrm m}B$ かつ $B\le_{\mathrm m}C$ なら $A\le_{\mathrm m}C$ である。
$A\le_{\mathrm m}B$ なら $\mathbb{N}\setminus A\le_{\mathrm m}\mathbb{N}\setminus B$ である。
$A\le_{\mathrm m}B$ で $B$ が決定可能なら、$A$ も決定可能である。
$A\le_{\mathrm m}B$ で $B$ が半決定可能なら、$A$ も半決定可能である。

還元の合成は還元であり、$\chi_A=\chi_B\circ f$、$A=\operatorname{dom}(\psi\circ f)$（$B=\operatorname{dom}\psi$）と書けることによる。

詳細

1. 恒等写像は $A$ から $A$ への還元である。$f$ が $A$ から $B$ への、$g$ が $B$ から $C$ への還元なら、$g\circ f$ は計算可能で、$x\in A\iff f(x)\in B\iff g(f(x))\in C$ である。

2. 同じ $f$ について $x\notin A\iff f(x)\notin B$ である。

3. $\chi_A=\chi_B\circ f$ は計算可能関数の合成である。

4. $B=\operatorname{dom}\psi$（$\psi$ は部分計算可能）とすると、$\psi\circ f$ は部分計算可能で、$x\in A\iff f(x)\in B\iff\psi(f(x))\!\downarrow$ なので $A=\operatorname{dom}(\psi\circ f)$ である。$\square$

3 と 4 の対偶が、決定不能性・半決定不能性を示す基本の道具になる。$A$ が決定可能でないと分かっていて $A\le_{\mathrm m}B$ を示せば、$B$ も決定可能でない。

自己停止集合の完全性

自己停止集合の決定不能性

$K$ は半決定可能だが決定可能でない。$\mathbb{N}\setminus K$ は半決定可能でない。

$x\mapsto\varphi_x(x)$ は (N2) の関数と $x\mapsto(x,x)$ の合成なので部分計算可能であり、その定義域が $K$ である。よって $K$ は半決定可能である。
$K$ が決定可能だとする。$\chi_K$ は計算可能なので、$d(x):\simeq\mu s\,[\,\chi_K(x)=0\,]$ は部分計算可能であり、$x\notin K$ のとき $d(x)=0$、$x\in K$ のとき $d(x)\!\uparrow$ である。(N1) により $d=\varphi_e$ となる $e$ がある。すると
$$ e\in K\iff\varphi_e(e)\!\downarrow\iff d(e)\!\downarrow\iff e\notin K $$
となり、矛盾する。
$\mathbb{N}\setminus K$ が半決定可能なら、$K$ と補集合がともに半決定可能になり、停止問題の記事の定理「決定可能性と半決定可能性」により $K$ は決定可能になって、前半に反する。$\square$

自己停止集合の完全性

$K$ は多対一還元に関して完全な計算可能枚挙集合である。すなわち、半決定可能なすべての $B\subset\mathbb{N}$ について $B\le_{\mathrm m}K$ である。

$K$ が半決定可能であることは thm-ct-k で示した。$B$ を半決定可能とし、$B=W_e$ となる $e$ をとる。$h(x,y):\simeq\varphi_e(x)$（$y$ を使わない）は (N2) により部分計算可能なので、(N1) により $h=\varphi^{(2)}_c$ となる $c$ がある。$f(x):=\sigma(c,x)$ とおくと、(N4) により $f$ は計算可能関数で、すべての $y$ について
$$ \varphi_{f(x)}(y)\simeq\varphi^{(2)}_c(x,y)\simeq\varphi_e(x) $$
である。$x\in B$ なら $\varphi_e(x)\!\downarrow$ なので $\varphi_{f(x)}$ は全域的であり、とくに $\varphi_{f(x)}(f(x))\!\downarrow$、すなわち $f(x)\in K$ である。$x\notin B$ なら $\varphi_{f(x)}$ はどこでも定義されず、$f(x)\notin K$ である。よって $f$ は $B$ から $K$ への多対一還元である。$\square$

$f(x)$ は「入力を無視して $\varphi_e(x)$ を計算する」番号なので、自分の番号で停止するかどうかは $x\in B$ かどうかだけで決まる。prop-ct-reduction の 1 により、$K\le_{\mathrm m}B$ となる半決定可能な $B$ は $K$ と同じく完全であり、決定可能でない。

Rice の定理

thm-ct-k-complete の証明の「入力を無視する番号」を少し変えると、関数の性質の判定に停止問題を持ち込める。

Rice の還元

$\mathcal{C}$ を部分計算可能関数の集まりとし、どこでも定義されない部分関数（グラフが空集合なので $\emptyset$ と書く）は $\mathcal{C}$ に属さず、$\mathcal{C}$ は空でないとする。このとき $K\le_{\mathrm m}I_{\mathcal{C}}$ である。

$g\in\mathcal{C}$ をとる。射影 $\pi(z_0,z_1):=z_0$ を使って
$$ h(x,y):\simeq\pi\bigl(g(y),\ \varphi_x(x)\bigr) $$
とおく。$h$ は部分計算可能関数の合成なので部分計算可能であり、$h(x,y)$ は $g(y)$ と $\varphi_x(x)$ がともに定義されるときにだけ定義されて値 $g(y)$ をとる。(N1) により $h=\varphi^{(2)}_c$ となる $c$ をとり、$f(x):=\sigma(c,x)$ とおくと、(N4) により $f$ は計算可能関数で $\varphi_{f(x)}(y)\simeq h(x,y)$ である。
$x\in K$ なら、すべての $y$ で $h(x,y)\simeq g(y)$ なので $\varphi_{f(x)}=g\in\mathcal{C}$、すなわち $f(x)\in I_{\mathcal{C}}$ である。$x\notin K$ なら $h(x,y)$ はどの $y$ でも定義されないので $\varphi_{f(x)}=\emptyset\notin\mathcal{C}$、すなわち $f(x)\notin I_{\mathcal{C}}$ である。$\square$

Rice の定理

$\mathcal{C}$ を部分計算可能関数の集まりとする。$I_{\mathcal{C}}=\{e\mid\varphi_e\in\mathcal{C}\}$ が決定可能なら、$\mathcal{C}$ は空であるか、部分計算可能関数の全体である。言い換えると、$\emptyset$ でも $\mathbb{N}$ でもない指数集合は決定可能でない。

$\mathcal{C}$ が空でも全体でもないとして、$I_{\mathcal{C}}$ が決定可能でないことを示す。
$\emptyset\notin\mathcal{C}$ の場合：lem-ct-rice-reduction により $K\le_{\mathrm m}I_{\mathcal{C}}$ である。$I_{\mathcal{C}}$ が決定可能なら、prop-ct-reduction の 3 により $K$ も決定可能になり、thm-ct-k に反する。
$\emptyset\in\mathcal{C}$ の場合：$\mathcal{C}$ に属さない部分計算可能関数の集まりを $\mathcal{C}'$ とする。$\mathcal{C}$ は全体でないので $\mathcal{C}'$ は空でなく、$\emptyset\notin\mathcal{C}'$ である。lem-ct-rice-reduction により $K\le_{\mathrm m}I_{\mathcal{C}'}=\mathbb{N}\setminus I_{\mathcal{C}}$ である。$I_{\mathcal{C}}$ が決定可能なら $\mathbb{N}\setminus I_{\mathcal{C}}$ も決定可能であり、同じく矛盾する。$\square$

Rice の定理は、プログラムの書き方（何文字か、ある命令を含むか）についての問いと、プログラムの振る舞い（入力 $0$ で停止するか、値が $7$ になることがあるか、全域的か）についての問いを分ける（OLT26 Theorem 30.23 とその後の説明）。前者は決定可能なことが多いが、後者は自明な場合を除いて決定できない。証明の後半から次が分かる。

振る舞いの否定的な性質

$\mathcal{C}$ が $\emptyset$ を含み、部分計算可能関数の全体でないなら、$I_{\mathcal{C}}$ は半決定可能でない。とくに $\{e\mid W_e=\emptyset\}$ は半決定可能でない。

prf-ct-rice の後半の還元を補集合に移すと $\mathbb{N}\setminus K\le_{\mathrm m}I_{\mathcal{C}}$ となり、$\mathbb{N}\setminus K$ が半決定可能でないことに帰着する。

詳細

prf-ct-rice の後半により $K\le_{\mathrm m}\mathbb{N}\setminus I_{\mathcal{C}}$ であり、prop-ct-reduction の 2 により $\mathbb{N}\setminus K\le_{\mathrm m}I_{\mathcal{C}}$ である。$I_{\mathcal{C}}$ が半決定可能なら、同じ命題の 4 により $\mathbb{N}\setminus K$ も半決定可能になり、thm-ct-k に反する。$\{e\mid W_e=\emptyset\}=I_{\{\emptyset\}}$ に当てはめればよい。$\square$

全域性の判定

$\mathrm{Tot}$ は $\emptyset$ を含まない集まりの指数集合なので、lem-ct-rice-reduction により $K\le_{\mathrm m}\mathrm{Tot}$ であり、決定可能でない（OLT26 Proposition 30.22）。実際にはさらに難しい。

全域性の集合とその補集合はどちらも半決定可能でない

$\mathrm{Tot}$ も $\mathbb{N}\setminus\mathrm{Tot}$ も半決定可能でない。

$\mathbb{N}\setminus\mathrm{Tot}$ について． 恒等的に $0$ の関数を $g$ として lem-ct-rice-reduction を $\mathcal{C}=\{$全域的な部分計算可能関数$\}$ に使うと $K\le_{\mathrm m}\mathrm{Tot}$ であり、prop-ct-reduction の 2 により $\mathbb{N}\setminus K\le_{\mathrm m}\mathbb{N}\setminus\mathrm{Tot}$ である。$\mathbb{N}\setminus\mathrm{Tot}$ が半決定可能なら、同じ命題の 4 により $\mathbb{N}\setminus K$ も半決定可能になり、thm-ct-k に反する。
$\mathrm{Tot}$ について． $\mathbb{N}\setminus K\le_{\mathrm m}\mathrm{Tot}$ を示す。(N3) の $T$ を使い、
$$ r(x,y):=\begin{cases}1&(T(x,x,s)\text{ となる }s\le y\text{ がある})\\0&(\text{ない})\end{cases} $$
とおく。$r$ は原始再帰的な関係の有界量化なので原始再帰的であり（原始再帰関数の記事の命題「有界な和・積・量化・最小化」）、とくに計算可能である。$h(x,y):\simeq\mu z\,[\,r(x,y)=0\,]$ とおくと、$h$ は部分計算可能で、$r(x,y)=0$ なら $h(x,y)=0$、$r(x,y)=1$ なら $h(x,y)\!\uparrow$ である。$h=\varphi^{(2)}_c$ となる $c$ をとり、$t(x):=\sigma(c,x)$ とおくと、$t$ は計算可能関数で $\varphi_{t(x)}(y)\simeq h(x,y)$ である。
$x\notin K$ なら、(N3) により $T(x,x,s)$ となる $s$ はなく、すべての $y$ で $r(x,y)=0$ なので $\varphi_{t(x)}$ は全域的であり、$t(x)\in\mathrm{Tot}$ である。$x\in K$ なら $T(x,x,s_0)$ となる $s_0$ があり、$y\ge s_0$ で $r(x,y)=1$ なので $\varphi_{t(x)}(s_0)\!\uparrow$、すなわち $t(x)\notin\mathrm{Tot}$ である。よって $t$ は $\mathbb{N}\setminus K$ から $\mathrm{Tot}$ への還元である。$\mathrm{Tot}$ が半決定可能なら $\mathbb{N}\setminus K$ も半決定可能になり、thm-ct-k に反する。$\square$

2 つ目の還元 $t(x)$ は「入力 $y$ を、自己停止の計算を $y$ 段まで見張る時間とみなし、それまでに停止しなければ $0$ を返す」番号である。$x\notin K$ のときだけ見張りが永久に続き、関数が全域的になる。
この違いは、定義に現れる量化記号の形（算術的階層）で整理できる。$K$ は $\exists$ が 1 つ、$\mathrm{Tot}$ は $\forall\exists$ の形である。

詳細

(N3) により $K=\{e\mid\exists s\ T(e,e,s)\}$ は決定可能な関係に $\exists$ を 1 つ付けた形であり、$\mathrm{Tot}=\{e\mid\forall y\ \exists s\ T(e,y,s)\}$ は $\forall\exists$ の形である。決定可能な関係に、$\exists$ から始まって交互に $n$ 個の量化記号を付けた形で書ける集合を $\Sigma_n$、$\forall$ から始まるものを $\Pi_n$ という。この分類を 算術的階層（arithmetical hierarchy）という。$\Sigma_1$ の集合は半決定可能である（$\exists s\,R(x,s)$ に対し $\mu s\,[\,1\mathbin{\dot-}\chi_R(x,s)=0\,]$ の定義域）。逆に半決定可能な集合は $W_e=\{x\mid\exists s\ T(e,x,s)\}$ なので $\Sigma_1$ であり、$\Sigma_1$ はちょうど半決定可能な集合、$\Pi_1$ はその補集合である。thm-ct-tot は、$\Pi_2$ の集合 $\mathrm{Tot}$ が $\Sigma_1$ にも $\Pi_1$ にも属さないことを示している（OLT26 §30.19 は Tot が算術的階層のより上にあると述べている）。

Kleene の再帰定理

停止問題の決定不能性の証明では、番号 $e$ の計算に自分の番号 $e$ を入力として与えた。再帰定理は、この自己言及が矛盾のためだけでなく、計算の構成に一般に使えることを述べる。

Kleene の再帰定理

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

$k(x,y):\simeq\varphi^{(2)}_x(x,y)$ は (N2) の関数と代入の合成なので部分計算可能であり、(N1) により $k=\varphi^{(2)}_c$ となる $c$ がある。$\delta(x):=\sigma(c,x)$ とおくと、(N4) により $\delta$ は計算可能関数で
$$ \varphi_{\delta(x)}(y)\simeq\varphi^{(2)}_x(x,y) $$
である。次に $l(x,y):\simeq g(\delta(x),y)$ は部分計算可能なので、$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$ 自身を入れた計算」の番号であり、対角線論法の対角線に当たる。$g$ を $\delta$ の後ろに合成した計算 $d$ を、さらにその対角線に置くと、計算の番号と計算の中で参照される番号が一致する（OLT26 Lemma 30.25・Theorem 30.26 とその後の説明）。

再帰定理の帰結

番号 $e$ で、すべての $y$ について $\varphi_e(y)=e$ となるものがある。
任意の計算可能関数 $f\colon\mathbb{N}\to\mathbb{N}$ に対し、$\varphi_e=\varphi_{f(e)}$ となる番号 $e$ がある（不動点定理）。

1 は $g(x,y):=x$、2 は $g(x,y):\simeq\varphi_{f(x)}(y)$ に thm-ct-recursion を使う。

詳細

1. $g(x,y):=x$ に thm-ct-recursion を使う。

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

1 は、入力を無視して自分自身の番号（プログラムの符号）を出力するプログラムの存在を述べている。2 からも Rice の定理が出る。

詳細

$I_{\mathcal{C}}$ が決定可能で $a\in I_{\mathcal{C}}$、$b\notin I_{\mathcal{C}}$ があるなら、$f(x):=b$（$x\in I_{\mathcal{C}}$）、$f(x):=a$（$x\notin I_{\mathcal{C}}$）は計算可能であり、不動点 $e$ について $e\in I_{\mathcal{C}}$ なら $\varphi_e=\varphi_b$ なので $b\in I_{\mathcal{C}}$、$e\notin I_{\mathcal{C}}$ なら $\varphi_e=\varphi_a$ なので $e\in I_{\mathcal{C}}$ となって、どちらも矛盾する。

分野の広がり

ここからは、上の定理の先にある話題を紹介する。いずれもこの記事では証明しない。

Turing 還元と Turing 次数．多対一還元では、$B$ への問い合わせは 1 回で、その答えをそのまま $A$ の答えにする。$B$ への問い合わせを計算の途中で何回でも行ってよい手続きで $A$ を判定できるとき、$A$ は $B$ に Turing 還元可能 であるという（OLT26 §30.16 の説明）。$\mathbb{N}\setminus K$ は $K$ に多対一還元できないが（thm-ct-k と prop-ct-reduction の 4）、Turing 還元はできる。Turing 還元で互いに還元できる集合の同値類を Turing次数という。
完全でない決定不能な集合．$K$、$H$（ex-ct-reductions の 1）、$K_1$（下の反例の表）はどれも $K$ を還元できる半決定可能な集合なので、thm-ct-k-complete の後の注意により完全である。決定可能でも完全でもない半決定可能な集合も存在する（OLT26 §30.17。この記事では証明しない）。
数学の問題の決定不能性．一階述語論理の文が妥当かどうかは決定できない（OLT26 Theorem 32.16、決定可能な理論）。整数係数の多項式方程式が整数解をもつかどうかを判定する手続き（Hilbert の第 10 問題）も存在しないことが、Matiyasevich・Robinson・Davis・Putnam の定理として示されている（OLT26 §75.7）。算術の不完全性（Gödelの不完全性定理）は計算可能性と深く結びついており、たとえば真な算術の文の全体は計算可能枚挙な公理系では捉えられない（決定可能な理論の記事の系「真の算術は公理化可能でない」）。
構成的な論理．「$x\in A$ か $x\notin A$ か」は古典論理では各 $x$ について正しいが、$A$ が決定可能でなければ、それを答える計算手続きはない。この観点からの論理の見直しは排中律と直観主義論理の記事で扱う。

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

外す条件	反例	成り立たなくなること
指数集合である（thm-ct-rice）	$\{e\mid e\le10\}$	決定可能でないこと
$\mathcal{C}$ が空でも全体でもない（thm-ct-rice）	$\mathcal{C}$ を部分計算可能関数の全体とし、$I_{\mathcal{C}}=\mathbb{N}$	決定可能でないこと
還元 $f$ が計算可能（prop-ct-reduction の 3）	$f(x)=0$（$x\in K$）、$f(x)=1$（$x\notin K$）による $K$ から $\{0\}$ への対応	$\{0\}$ が決定可能なら $K$ も決定可能であること
$g$ が部分計算可能（thm-ct-recursion）	$g(x,y)=0$（$\varphi_x(y)\!\uparrow$）、$g(x,y)\!\uparrow$（$\varphi_x(y)\!\downarrow$）	$\varphi_e(y)\simeq g(e,y)$ となる $e$ の存在
すべての入力で定義される（thm-ct-tot）	入力 $0$ で定義される番号の集合 $K_1:=\{e\mid\varphi_e(0)\!\downarrow\}$	半決定可能でないこと

反例の確かめ

1・2・5 行目は集合が決定可能または半決定可能であることを直接確かめ、3・4 行目は定理の結論が成り立たないことを確かめる。

詳細

1 行目：$\{e\mid e\le10\}$ の特性関数は原始再帰関数なので決定可能である。この集合は決定可能で $\emptyset$ でも $\mathbb{N}$ でもないので、thm-ct-rice の対偶により指数集合ではない（計算可能関数の記事の番号付けでの直接の確かめは ex-ct-index-sets の 2）。番号の大きさは番号の書き方の性質であって、関数の性質ではない。

2 行目：$I_{\mathcal{C}}=\mathbb{N}$ の特性関数は定数 $1$ で計算可能である。$\mathcal{C}$ が空のときも $I_{\mathcal{C}}=\emptyset$ で同様である。

3 行目：$x\in K\iff f(x)\in\{0\}$ なので、計算可能性を除けば還元の条件を満たす。$\{0\}$ は決定可能だが $K$ は決定可能でない（thm-ct-k）。$f=1-\chi_K$ は計算可能でない。

4 行目：$\varphi_e(y)\simeq g(e,y)$ がすべての $y$ で成り立つ $e$ があるとすると、$\varphi_e(y)\!\downarrow\iff g(e,y)\!\downarrow\iff\varphi_e(y)\!\uparrow$ となって矛盾する。したがってこの $g$ には再帰定理の結論が成り立たず、thm-ct-recursion の対偶により $g$ は部分計算可能でない。

5 行目：$K_1$ は部分計算可能関数 $e\mapsto\varphi_e(0)$ の定義域なので半決定可能である。$K_1$ は空でない集まりの指数集合で $\emptyset$ を含まない集まり（$0$ で定義される関数の全体）に対応するので、lem-ct-rice-reduction により $K\le_{\mathrm m}K_1$ であり、thm-ct-k-complete とあわせて $K_1$ は完全である。「すべての入力」を「入力 $0$」に弱めると、難しさは $K$ と同じところまで下がる。

参照箇所

OLT26 Chapter 30：Theorem 30.1（p. 449、標準形）、Theorem 30.2・30.3（p. 450、番号の無限性と s-m-n 定理）、Theorem 30.4（p. 451、万能関数）、Theorem 30.12（p. 458、自己停止集合）、§30.15・§30.16（pp. 460–462、多対一還元と Turing 還元、Definition 30.16 p. 461）、§30.17（p. 463、Definition 30.19、完全集合と、完全でない集合の存在）、Proposition 30.22（p. 464、全域性）、Theorem 30.23（p. 465、Rice の定理）、Lemma 30.25・Theorem 30.26（p. 468、再帰定理）。Theorem 32.16（p. 511、一階論理の決定問題）、§75.7（p. 986、Hilbert の第 10 問題と MRDP 定理）。