計算可能性：チューリング機械・再帰関数・停止問題とライスの定理

0. この記事の要点

プログラムを書くと、どんな入力でも必ず答えを返すものもあれば、入力によっては延々と動き続けるものもあります。「あるプログラムが、この入力でいつか止まるか」を、別のプログラムで必ず見抜くことはできるのでしょうか。この記事では、まず「計算できる」とは何かを数学の言葉で決め、そのうえで「見抜く手順は存在しない」ことを証明します。読み終えると、「解けない」ことを証明するとはどういうことか、その典型的な形が分かります。

• 「アルゴリズムで計算できる関数」を、チューリング機械で数学的に定義します。有限個の規則をもつ機械が、無限に延びるテープの上で記号 $0,1$（と作業用の目印 $2$）を読み書きする、という最小限のモデルです。
• 同じクラスの関数を、機械を使わない帰納的な定義でも与えられます。原始再帰関数（足し算から掛け算を作るように、一つ前の値から次の値を組み立てる繰り返しで定義される関数）に最小化演算 $\mu$（条件を満たす最小の数を探す操作）を加えたものが部分再帰関数です。両者が一致すること（定理 5.4, 定理 6.2）が、定義の選び方に依らない概念であることの根拠になります。
• チューリング機械の動作を数に置き換えて（算術化）、ステップ数を探索する部分以外が原始再帰的であることを示すと、クリーネの標準形定理（定理 5.3）が出ます。これが機械そのものを数で名指しし、それを実行する万能関数（番号 $e$ と入力を受け取り、番号 $e$ の機械の動作を再現する関数）を得る仕組みです。
• 停止問題は決定不能です（定理 7.2）。証明はカントールの対角線論法と同じ形で、「自分自身に適用した結果を反転する」関数を作ります。
• ライスの定理（定理 8.2）：機械が計算する関数の（自明でない）性質を、機械の記述から判定するアルゴリズムは存在しない。停止問題への帰着が証明の中身です。
• この結果が、不完全性定理（形式体系の定理は列挙できるが判定できない）と、型検査器にできること・できないことの前提になります。

この記事で使う事前知識

• 部分関数: 定義域の一部でしか値が決まらなくてもよい関数。入力によっては「未定義」になります。§1 でこの記事の記号を確認します。
• 対角線論法: 数え上げた表の対角成分をずらして、どの行にも現れないものを作る議論。→ 濃度と無限
• 数学的帰納法: 最初の場合と「$n$ のとき成り立てば $n+1$ でも成り立つ」を示して、すべての自然数で成り立つとする証明。→ 証明の技術
• 背理法: 結論が成り立たないと仮定して矛盾を導く証明。→ 証明の技術
• 特性関数: 集合に属すれば $1$、属さなければ $0$ を返す関数（§2.2 で定義します）。
• 素因数分解の一意性: 自然数は素数の積として（順序を除いて）ただ一通りに書けること。

1. 動機：「機械的に決まる」とは何か

1928 年、ヒルベルトとアッケルマンは決定問題を提示しました。一階述語論理の文を与えられたとき、それが恒真であるか否かを、有限回の機械的な操作で必ず判定する手順はあるか、という問いです。一階述語論理と完全性定理で見たとおり、恒真な文には必ず証明があり、証明は機械的に検査できます。証明を短い順にすべて試せば、恒真な文はいつか見つかります。しかし恒真でない文については、探索は永遠に終わりません。

この問いに「ない」と答えるには、「手順」の意味を数学の言葉で固定しなければなりません。「どんな手順をもってしても不可能だ」を証明するには、手順の全体を定義する必要があるからです。1936 年にチャーチは $\lambda$ 定義可能性で、チューリングはチューリング機械で、これを行いました。さらに両者が（そしてゲーデルとクリーネの再帰関数も）同じクラスの関数を与えることが示されます。

この記事の目標は三つです。(1) 計算可能性の標準的な定義を与え、それらが一致することを示す。(2) 停止問題が解けないことを証明する。(3) その帰結として、機械の性質に関する問いのほとんどが解けないこと（ライスの定理）を示す。

記号と約束。 $\mathbb{N}=\{0,1,2,\ldots\}$ です。関数 $f:\mathbb{N}^n\rightharpoonup\mathbb{N}$ は部分関数（定義域が $\mathbb{N}^n$ の一部でもよい）で、$f(\vec{x})\downarrow$ は「$f(\vec{x})$ が定義されている」、$f(\vec{x})\uparrow$ は「定義されていない」を表します。式 $f(\vec{x})\simeq g(\vec{x})$ は「両辺がともに未定義、またはともに定義されて等しい」ことを意味します。全域で定義された関数を全関数と呼びます。

2. チューリング機械

2.1. 定義

定義 2.1（チューリング機械）↗

チューリング機械（以下、機械）$M$ とは、有限個の規則の集合である。各規則は

$$(q,a)\longmapsto(q',b,d)$$

の形をしている。ここで $q,q'\in\mathbb{N}$ は状態、$a,b\in\{0,1,2\}$ は記号（$0$ を空白とみなし、$2$ は作業用の目印として使う）、$d\in\{L,R\}$ は移動方向である。各組 $(q,a)$ に対して規則は高々一つしか存在しない。

テープは両側に無限に延びる升目の列で、各升目に $0,1,2$ のどれかが書かれている（有限個を除いて $0$）。ヘッドは升目の一つを指す。状況（configuration）とは、テープの内容、ヘッドの位置、現在の状態の組である。

機械は状態 $0$ から始める。状況が $(q,a)$（$q$ は現在の状態、$a$ はヘッドの下の記号）のとき、規則 $(q,a)\mapsto(q',b,d)$ があれば、1 ステップで次のことを行う。ヘッドの下の記号を $b$ に書き換え、$d$ の方向に升目を一つ移動し、状態を $q'$ にする。該当する規則がなければ停止する。

テープとヘッド。状態 q の機械が 1 を読み、規則 (q,1) → (q′, 0, R) があれば、0 を書いて右へ 1 つ動き状態 q′ になる。

規則が高々一つ（決定性）で、状態集合が有限（規則が有限個）である点が肝心です。状態は無限の番号が使えますが、ひとつの機械が実際に使う番号は有限個です。

2.2. 入出力の規約

自然数を関数の入出力に使うため、規約を決めます。

定義 2.2（機械が計算する関数）↗

自然数 $x$ を、$x+1$ 個の連続する $1$ のブロック $1^{x+1}$ で表す。$n$ 個の引数 $x_1,\ldots,x_n$ の標準入力とは、テープが

$$1^{x_1+1}\,0\,1^{x_2+1}\,0\cdots0\,1^{x_n+1}$$

の形で、これ以外の升目がすべて $0$ であり、ヘッドが最左の $1$ を指し、状態が $0$ であるような状況をいう。標準出力 $y$ とは、テープが $1^{y+1}$ 以外すべて $0$ で、ヘッドがその最左の $1$ を指す状況をいう（状態は問わない）。

機械 $M$ が標準入力 $\vec{x}$ から始めて有限ステップで停止し、そのとき標準出力 $y$ になっているならば、$\varphi^{(n)}_M(\vec{x})=y$ と定める。そうでなければ（停止しない、または停止しても標準出力でない）$\varphi^{(n)}_M(\vec{x})\uparrow$ とする。部分関数 $f$ に対して $f=\varphi^{(n)}_M$ となる機械 $M$ があるとき、$f$ はチューリング計算可能であるという。

例 2.3（後者関数を計算する機械）

次の三つの規則からなる機械 $M_S$ は $\varphi^{(1)}_{M_S}(x)=x+1$ を計算します。

$$(0,1)\mapsto(1,1,L),\qquad(1,0)\mapsto(2,1,L),\qquad(2,0)\mapsto(3,0,R).$$

標準入力のヘッドは最左の $1$（位置 $p$）にあります。状態 $0$ で $1$ を読み、そのまま書いて左へ動くと位置 $p-1$（空白）に出ます。状態 $1$ で $0$ を読み、$1$ を書いて左へ動くと位置 $p-2$。状態 $2$ で $0$ を読み、$0$ を書いて右へ動くと位置 $p-1$ に戻り、状態 $3$ で $1$ を読みます。状態 $3$ の規則はないので停止します。テープは位置 $p-1$ から $p+x$ までが $1$（$x+2$ 個）で、ヘッドは最左の $1$ にある。これは標準出力 $x+1$ です。

$x=2$ の入力で、機械 $M_S$ が 1 ステップごとにヘッドと状態を変えていく様子を見てください。

後者関数の機械 M_S を x = 2 で動かした 3 ステップ。テープに 1 が 1 つ増え、ヘッドは最左の 1 に戻って停止する。

決定問題と半決定問題を定義します。集合 $A\subseteq\mathbb{N}$ が決定可能であるとは、特性関数 $\chi_A$（$A$ に属すれば $1$、属さなければ $0$）がチューリング計算可能な全関数であることをいいます。$A$ が半決定可能（計算可能枚挙可能）であるとは、$A$ がチューリング計算可能な部分関数の定義域であることをいいます。属するものにはいつか「はい」と答え、属さないものには永遠に答えない手順があること、と読めます。

3. 原始再帰関数

機械を使わずに、関数を帰納的に定義する方法を用意します。これは「$f(y+1)$ を $f(y)$ から計算する」という素朴な再帰を一般化したものです。

定義 3.1（原始再帰関数）↗

次の基本関数を考える。

• ゼロ関数 $Z(x)=0$。
• 後者関数 $S(x)=x+1$。
• 射影関数 $P^n_i(x_1,\ldots,x_n)=x_i$（$1\le i\le n$）。

原始再帰関数とは、基本関数から次の二つの操作を有限回繰り返して得られる関数である。

• 合成：$g:\mathbb{N}^m\to\mathbb{N}$ と $h_1,\ldots,h_m:\mathbb{N}^n\to\mathbb{N}$ から、$f(\vec{x})=g(h_1(\vec{x}),\ldots,h_m(\vec{x}))$。
• 原始再帰：$g:\mathbb{N}^n\to\mathbb{N}$ と $h:\mathbb{N}^{n+2}\to\mathbb{N}$ から、

$$f(\vec{x},0)=g(\vec{x}),\qquad f(\vec{x},y+1)=h(\vec{x},y,f(\vec{x},y)).$$

原始再帰関数はすべて全関数です（再帰の深さ $y$ に関する帰納法）。集合（述語）$P\subseteq\mathbb{N}^n$ が原始再帰的であるとは、その特性関数が原始再帰的であることをいいます。

命題 3.2（原始再帰関数の道具箱）✓

次はいずれも原始再帰的である。

1. $x+y$、$x\cdot y$、$x^y$、$x!$、前者 $\mathrm{pd}(x)$（$\mathrm{pd}(0)=0$, $\mathrm{pd}(x+1)=x$）、切り捨て差 $x\dot-y=\max(x-y,0)$、符号 $\mathrm{sg}(x)$（$x=0$ なら $0$、それ以外 $1$）。
2. 原始再帰的な述語の否定・論理積・論理和。原始再帰的な関数による場合分け定義。
3. $f$ が原始再帰的ならば、有界和 $\sum_{i<y}f(\vec{x},i)$ と有界積 $\prod_{i<y}f(\vec{x},i)$。
4. $P$ が原始再帰的述語ならば、有界量化 $\exists i<y\,P(\vec{x},i)$、$\forall i<y\,P(\vec{x},i)$、および有界最小化 $\mu i<y\,[P(\vec{x},i)]$（そのような $i$ のうち最小のもの。なければ $y$）。
5. 商 $\lfloor x/y\rfloor$、余り $x\bmod y$、約数関係 $y\mid x$、素数述語、$i$ 番目の素数 $p_i$（$p_0=2$）、素因数分解における指数 $(n)_i$（$n$ の素因数分解での $p_i$ の指数）。

証明（命題 3.2）

(1) $x+0=x$, $x+(y+1)=S(x+y)$ から加法、$x\cdot0=0$, $x\cdot(y+1)=x\cdot y+x$ から乗法、以下同様に $x^y$, $x!$ を得る。$\mathrm{pd}$ は $\mathrm{pd}(0)=0$, $\mathrm{pd}(y+1)=y$ という原始再帰（$h(y,\cdot)=P^2_1$）。$x\dot-0=x$, $x\dot-(y+1)=\mathrm{pd}(x\dot-y)$。$\mathrm{sg}(0)=0$, $\mathrm{sg}(y+1)=1$。 (2) 述語の特性関数 $\chi_P,\chi_Q$ に対し、$\chi_{\neg P}=1\dot-\chi_P$, $\chi_{P\wedge Q}=\chi_P\cdot\chi_Q$, $\chi_{P\vee Q}=\mathrm{sg}(\chi_P+\chi_Q)$。場合分け $f=g_1$（$P$ のとき）、$g_2$（そうでないとき）は $\chi_P\cdot g_1+(1\dot-\chi_P)\cdot g_2$。 (3) $F(\vec{x},0)=0$, $F(\vec{x},y+1)=F(\vec{x},y)+f(\vec{x},y)$（積は初期値 $1$ と乗法）。 (4) $\exists i<y\,P=\mathrm{sg}(\sum_{i<y}\chi_P(\vec{x},i))$。$\forall i<y\,P=\neg\exists i<y\,\neg P$。有界最小化は $\mu i<y[P]=\sum_{j<y}\prod_{i\le j}(1\dot-\chi_P(\vec{x},i))$ で表せる：$P$ を満たす最小の $i_0$ があれば、$j<i_0$ の項は積が $1$、$j\ge i_0$ の項は積が $0$ なので和は $i_0$、なければ全項が $1$ で和は $y$。 (5) $\lfloor x/y\rfloor=\mu k<x+1\,[(k+1)\cdot y>x]$（$y>0$）。$x\bmod y=x\dot-y\cdot\lfloor x/y\rfloor$。$y\mid x\iff x\bmod y=0\ (y>0)$。素数述語は「$x\ge2$ かつ $\forall d<x\,(d\le1\vee d\nmid x)$」。$p_{i+1}$ については、$p_i!+1$ の素因数は $p_i$ 以下の素数ではどれも割り切れない（定理 3.2［素数の魅力と素数定理］の議論）ので $p_i!+1$ の素因数のうち最小のものは $p_i$ より大きく、$p_i!+1$ 以下である。したがって $p_{i+1}=\mu k\le p_i!+1\,[k>p_i\wedge k\text{ は素数}]$ と有界最小化で書ける（$p_{i+1}$ は $p_i$ より大きい最小の素数）。最後に、$n>0$ のとき $(n)_i=\mu k<n\,[\,p_i^{k+1}\nmid n\,]$（$p_i^{k}\le n$ なら $k<n$ なので探索範囲は足りる）。

∎

有界最小化の式 (4) は、小さな例で確かめると意味が見えます。$y=4$ で、$P(i)$ が $i=2$ で初めて成り立つとします（$\chi_P=(0,0,1,\ast)$。$\ast$ は何でもよい）。$j=0,1$ の項は $\prod_{i\le j}(1\dot-\chi_P(i))=1$、$j=2,3$ の項は $\chi_P(2)=1$ を含むので $0$ です。和は $1+1+0+0=2$ で、確かに最小の $i$ が出ます。

素因数分解の存在と一意性（定理 4.2［素数の魅力と素数定理］）により、有限列 $(a_0,\ldots,a_k)$ は数 $p_0^{a_0}p_1^{a_1}\cdots p_k^{a_k}$ に一意に符号化され、$(n)_i$ で復号できます。これがこの記事で使う唯一の符号化の道具です。

4. μ 再帰関数

原始再帰関数はすべて全関数ですが、機械は停止しないことがあるので、機械が計算する関数のクラスに一致させるには部分関数まで広げる必要があります。無限探索を許す最小化を加えます。

定義 4.1（部分再帰関数）↗

部分関数 $g:\mathbb{N}^{n+1}\rightharpoonup\mathbb{N}$ に対して、最小化 $f=\mu g$ を

$$f(\vec{x})\simeq\mu y\,[g(\vec{x},y)=0]$$

で定める。右辺は「$g(\vec{x},0),\ldots,g(\vec{x},y-1)$ がすべて定義されて $0$ でなく、$g(\vec{x},y)=0$ となる最小の $y$」であり、そのような $y$ がなければ未定義とする。

部分再帰関数（$\mu$ 再帰関数）とは、基本関数から合成・原始再帰・最小化を有限回用いて得られる部分関数である。ここで合成と原始再帰は、部分関数に対しても同じ式で、$\simeq$ の意味（右辺の各部分が定義されている限りで定義される）で適用する。たとえば $f(\vec{x},y+1)\simeq h(\vec{x},y,f(\vec{x},y))$ では、$f(\vec{x},y)$ が未定義なら $f(\vec{x},y+1)$ も未定義とする。全関数であるものを再帰関数という。

注意 4.2（原始再帰関数と再帰関数の違い）

すべての原始再帰関数は再帰関数ですが、逆は成り立ちません。アッカーマン関数 $A(0,n)=n+1$, $A(m+1,0)=A(m,1)$, $A(m+1,n+1)=A(m,A(m+1,n))$ は、直観的に計算可能な全関数で、再帰関数であることが知られています。どの原始再帰関数よりも速く増大するため原始再帰的ではありません。この事実は以後使いません（証明は省略します）。

5. チューリング計算可能な関数は部分再帰的である

機械の動作を数の演算に翻訳します（算術化）。以下では $\varphi_e^{(n)}$ という記号で、番号 $e$ の機械が計算する $n$ 変数関数を表します。

5.1. 機械に番号を付ける

定義 5.1（機械の番号）↗

自然数 $e$ に対し、機械 $M_e$ を次で定める。各 $q\in\mathbb{N}$, $a\in\{0,1,2\}$ について $v=(e+1)_{3q+a}$（$e+1$ の素因数分解における $p_{3q+a}$ の指数）とおく。$v=0$ なら $(q,a)$ に対する規則はない。$v\ge1$ なら $w=v-1$ とおき、規則

$$(q,a)\longmapsto(q',b,d),\qquad q'=\lfloor w/6\rfloor,\ b=\lfloor w/2\rfloor\bmod3,\ d=\begin{cases}R&(w\bmod 2=1)\\L&(w\bmod 2=0)\end{cases}$$

を $M_e$ に入れる。$e+1$ の素因数は有限個なので、$M_e$ の規則は有限個である。$\varphi^{(n)}_e=\varphi^{(n)}_{M_e}$ と書く。

$w=6q'+2b+d'$（$d'\in\{0,1\}$）により、$w\mapsto(q',b,d)$ は $\mathbb{N}$ から（状態, 記号, 方向）の組全体への全単射なので、すべての機械はある $M_e$ と一致し、すべての $e$ は機械を与えます（素因数分解の一意性による）。機械の番号は無限に重複なく振られています。

具体例として、§2.2 の機械 $M_S$ の番号を作ってみます。規則 $(0,1)\mapsto(1,1,L)$ では $w=6\cdot1+2\cdot1+0=8$、$v=9$ で、位置は $3q+a=1$ なので素数 $p_1=3$ の指数が $9$ です。同様に $(1,0)\mapsto(2,1,L)$ は $w=14$、$v=15$、位置 $3$（$p_3=7$）、$(2,0)\mapsto(3,0,R)$ は $w=19$、$v=20$、位置 $6$（$p_6=17$）となります。したがって $e+1=3^{9}\cdot7^{15}\cdot17^{20}$ のとき $M_e=M_S$ です。素因数分解の指数を、規則の「表」の各欄として使っているだけです。

5.2. 状況を数にする

テープの内容を、ヘッドが指す升目の記号 $a$、左側の升目を近い順に並べた記号列を 3 進数とみなした数 $l$（最近接の升目が最下位の桁）、右側の升目を近い順に並べた記号列を 3 進数とみなした数 $r$ の三つ組で表します。有限個を除いて $0$ なので $l,r$ は自然数です。

3 進数を使う理由は、記号が $0,1,2$ の三種類で、ヘッドが一つ動くときの更新が「最下位の桁を取り出す・付け加える」という割り算と掛け算だけで書けるからです。たとえばヘッドの左側が近い順に $1,2$、ヘッドの下が $1$、右側が近い順に $0,1$ なら、$l=1+2\cdot3=7$、$a=1$、$r=0+1\cdot3=3$ です。状況を一つの数にまとめれば、機械の動作全体を数の関数として扱え、原始再帰関数の道具が使えるようになります。

状態 $q$ を加え、状況を一つの数

$$\langle q,l,a,r\rangle=2^q3^l5^a7^r$$

で表します。次の補題が、機械の 1 ステップが原始再帰的な計算であることを示します。

補題 5.2（1 ステップの算術化）✓

関数 $\mathrm{Step}(e,c)$ を次で定める。$c=\langle q,l,a,r\rangle$ とし、$M_e$ の規則 $(q,a)\mapsto(q',b,d)$ があれば

• $d=R$ のとき $\mathrm{Step}(e,c)=\langle q',\,3l+b,\ r\bmod3,\ \lfloor r/3\rfloor\rangle$、
• $d=L$ のとき $\mathrm{Step}(e,c)=\langle q',\,\lfloor l/3\rfloor,\ l\bmod3,\ 3r+b\rangle$、

規則がなければ $\mathrm{Step}(e,c)=c$ とする。$\mathrm{Step}$ は原始再帰的であり、$M_e$ の状況 $c$ の次の状況を表す。

証明（補題 5.2）

右へ動く場合：書き込んだ記号 $b$ のある升目は新しいヘッドの左隣の最近接の升目になるので、左側の記号列の最下位の桁に $b$ を付け加えて $l'=3l+b$。新しいヘッドの下の記号は右側の最近接の升目、つまり $r$ の最下位の桁 $r\bmod3$ で、右側の残りは $\lfloor r/3\rfloor$。左へ動く場合は対称。規則の有無と $(q',b,d)$ は 定義 5.1 のとおり $(e+1)_{3q+a}$ から場合分けで決まり、命題 3.2 の道具で原始再帰的に書ける。$q,l,a,r$ は $c$ の素因数分解の指数 $(c)_0,(c)_1,(c)_2,(c)_3$ で、$c$ は $2^{q'}3^{l'}5^{a'}7^{r'}$ で再構成できる。

∎

標準入力の状況 $\mathrm{Init}_n(\vec{x})$ は原始再帰的です。標準入力のテープ全体を、ヘッドの升目を最下位の桁として右へ読んだ 3 進数を $W_n(x_1,\ldots,x_n)$ とおくと、

$$W_1(x)=\frac{3^{x+1}-1}{2},\qquad W_{n+1}(x_1,\vec{x}')=\frac{3^{x_1+1}-1}{2}+3^{x_1+2}\,W_n(\vec{x}')$$

です（$1^{x_1+1}$ は 3 進で $\sum_{i\le x_1}3^i=(3^{x_1+1}-1)/2$ に当たり、その次に $0$ が一つあって、その後に残りの引数の語が続く）。ヘッドの下の記号は $1$、左側は $0$、右側は $r=(W_n-1)/3$ なので、$\mathrm{Init}_n(\vec{x})=\langle0,0,1,(W_n(\vec{x})-1)/3\rangle$ です。

標準出力の状況は、$l=0$, $a=1$, $r=(3^y-1)/2$ となる $y$ が存在する（右側が $1$ だけ $y$ 個並ぶ）という条件で特徴づけられ、出力値は $y=\mu y\le r\,[\,3^y=2r+1\,]$ です。これらも原始再帰的です。

5.3. クリーネの標準形定理

定理 5.3（クリーネの標準形定理）✓

各 $n\ge1$ に対して、原始再帰的な述語 $T_n(e,\vec{x},t)$ と原始再帰的な関数 $U(c)$ が存在して、すべての $e,\vec{x}$ について

$$\varphi^{(n)}_e(\vec{x})\ \simeq\ U\bigl(\mathrm{Conf}(e,\vec{x},\ \mu t\,[T_n(e,\vec{x},t)])\bigr)$$

が成り立つ。ここで $\mathrm{Conf}(e,\vec{x},t)$ は、$M_e$ を標準入力 $\vec{x}$ から $t$ ステップ動かした後の状況の符号である。

証明（定理 5.3）

$\mathrm{Conf}(e,\vec{x},0)=\mathrm{Init}_n(\vec{x})$, $\mathrm{Conf}(e,\vec{x},t+1)=\mathrm{Step}(e,\mathrm{Conf}(e,\vec{x},t))$ は原始再帰（補題 5.2）。$T_n(e,\vec{x},t)$ を「$c=\mathrm{Conf}(e,\vec{x},t)$ に対して $c$ が標準出力の状況である、かつ $M_e$ に $c$ の状態と記号に対する規則がない」と定める。これは原始再帰的である。$U(c)$ は標準出力の状況 $c$ から出力値 $y$ を読む関数とする。

機械が停止するまで $\mathrm{Conf}$ は実際の動作を追い、停止後は $\mathrm{Step}$ の定義から同じ状況に止まる。よって $T_n(e,\vec{x},t)$ が成り立つ最小の $t$ が存在することは、「$M_e$ が停止し、そのとき標準出力である」ことと同値で、その状況は $\mathrm{Conf}(e,\vec{x},t)$ である。このとき $U$ が出力値を与えるので、両辺は定義の意味で一致する。停止しない、または標準出力でない状況で停止する場合は、どの $t$ でも $T_n$ が成り立たないので $\mu$ は未定義で、これは $\varphi^{(n)}_e(\vec{x})\uparrow$ と一致する。

∎

定理 5.4（チューリング計算可能なら部分再帰的）✓

チューリング計算可能な部分関数はすべて部分再帰関数である。さらに、万能関数 $\Phi^{(n)}(e,\vec{x})\simeq\varphi^{(n)}_e(\vec{x})$ は部分再帰関数である。

証明（定理 5.4）

定理 5.3 の右辺は、原始再帰関数と一回の最小化 $\mu t\,[1\dot-\chi_{T_n}(e,\vec{x},t)=0]$ の合成であり、部分再帰関数である。チューリング計算可能な関数 $f$ は、ある $e$ について $f=\varphi^{(n)}_e$ であり（すべての機械は $M_e$ の形）、$f(\vec{x})\simeq\Phi^{(n)}(e,\vec{x})$ は $e$ を定数に固定した $\Phi^{(n)}$ なので部分再帰関数である。

∎

万能関数が部分再帰的であることは、一つの機械が他のすべての機械を番号付きで模倣できる（万能チューリング機械）という事実の算術化された形です。コンピュータの原型です。

6. 部分再帰関数はチューリング計算可能である

逆向きは、再帰関数の構成の各段階に対応する機械を作ることで示します。機械同士を組み合わせるため、次の性質をもつ機械を考えます。

定義 6.1（整った機械）↗

$n$ 変数の部分関数 $f$ について、機械 $M$ が整っているとは、すべての標準入力 $\vec{x}$ から始めた動作が次を満たすことをいう。ヘッドの最初の位置（最左の $1$）を $p$ とする。

• (a) $M$ が停止するのは、升目 $p$ 以右の内容が標準出力（一つのブロック $1^{y+1}$ 以外すべて $0$）になっていて、ヘッドがその最左の $1$ を指しているときに限り、そのとき $y=f(\vec{x})$ である。特に $f(\vec{x})\uparrow$ ならば $M$ は停止しない。（以下、標準出力といえばこの意味、すなわち升目 $p-1$ 以左の内容は問わない。）
• (b) $M$ は升目 $p-2$ 以左を訪れない。升目 $p-1$ には移ってよいが、そこでは書き込まない。

(b) は、$M$ の左側にあるデータを壊さないための条件です。以下ではデータのブロックが空白一つを挟んで並び、$M$ の開始位置 $p$ の左隣 $p-1$ は常に空白です。このとき $M$ の動作は $p$ 以右の升目だけで決まるので、左側に何があっても、標準入力の置かれた位置さえ指せば同じ動作をします。作業用の記号 $2$（目印）を使えば、次の部品は有限個の規則で実現できます。語 $D$ は空白一つで区切られたブロックの列を表します。

• (S1) 語の右端（空白が二つ続く位置）へ移る。
• (S2) $j$ 番目のブロックを、語の右端の空白一つ先に複製する。
• (S3) 語の右端のブロックを消す。
• (S4) 右端のブロックを、直前の空白を詰めて左へ平行移動する。
• (S5) ブロックの長さを一つ増やす。二つのブロックの長さが等しいかを判定して分岐する。

例えば (S2) は、複製元の最左の $1$ を $2$ に書き換えて右端まで運び、そこに $1$ を一つ書き、戻って次の $1$ を $2$ に、というのを繰り返し、最後に $2$ をすべて $1$ に戻す。目印を使うので、ブロックの長さの情報を機械の状態に持たなくて済みます。

定理 6.2（部分再帰関数はチューリング計算可能）✓

すべての部分再帰関数 $f:\mathbb{N}^n\rightharpoonup\mathbb{N}$ について、$f$ について整っている機械 $M_f$ が存在する。特に、$f$ はチューリング計算可能である。

証明（定理 6.2）

$f$ の構成に関する帰納法で示す。以下、機械を図式（部品の連結）で述べる。連結 $M_1;M_2$ とは、$M_1$ が停止する状況（標準出力でヘッドは最左の $1$）から $M_2$ を始めるように規則をつなぐことである（$M_1$ の停止状況の規則のない組に、$M_2$ の開始状態への遷移を足す。$M_1$ は標準出力でしか停止しないので、足した規則が働くのは意図した状況に限られる）。

基本関数。 $Z$：最左の $1$ を残して残りを消し、戻る。$S$：ブロックの右端に $1$ を一つ足し（(S5)）、最左の $1$ に戻る。$P^n_i$：$i$ 番目以外のブロックを（(S3) を左から必要な回数使い、ブロック数 $n$ は機械が知っているので端を検出できる）消して、$i$ 番目のブロックの最左の $1$ に立つ。いずれも (b) を満たす。

合成 $f(\vec{x})=g(h_1(\vec{x}),\ldots,h_m(\vec{x}))$。標準入力 $D=\vec{x}$ から、$i=1,\ldots,m$ について次を行う。(S2) で $D$ のすべてのブロックを右端に複製し、複製の最左の $1$ に立って $M_{h_i}$ を走らせる。(b) により $D$ や既に得た値は壊れない。終わると語は $D\ 0\ y_1\ 0\cdots0\ y_i$（$y_j=h_j(\vec{x})$）になっている。最後に $y_1$ の最左の $1$ に立って $M_g$ を走らせ、出力を得たら (S3) で $D$ と余りを消し、出力の最左の $1$ に立つ。どの $h_i$ も未定義の入力では対応する段階で停止しないので、(a) が保たれる。$g$ の未定義も同様。

原始再帰 $f(\vec{x},0)=g(\vec{x})$, $f(\vec{x},y+1)=h(\vec{x},y,f(\vec{x},y))$。語 $\vec{x}\ 0\ y$ から始め、(S2) で $\vec{x}$ を複製して $M_g$ を走らせ、語 $\vec{x}\ 0\ y\ 0\ 1\ 0\ v_0$ を得る（$1$ のブロックは添字 $i=0$ の表現、$v_0=g(\vec{x})$）。以下を繰り返す。$i$ のブロックと $y$ のブロックの長さを (S5) で比べ、等しければ $v_i$ を (S4) で語の先頭へ移すなどして余りを消し、停止する。等しくなければ $\vec{x},i,v_i$ を (S2) で順に右端へ複製して $M_h$ を走らせ、得た $v_{i+1}$ の前の $v_i$ のブロックを消して詰め、$i$ のブロックに (S5) で $1$ を足す。ループは $y$ の値だけ回って終わり、各段階が定義されている限りで定義される。

最小化 $f(\vec{x})\simeq\mu y\,[g(\vec{x},y)=0]$。語 $\vec{x}\ 0\ y$ に $y=0$（$1$ のブロック）を置いて始める。$\vec{x}$ と $y$ を複製して $M_g$ を走らせ、結果が $0$（長さ $1$ のブロック）かどうかを (S5) で判定する。$0$ なら $y$ のブロックを残して余りを消して停止する。そうでなければ結果を消し、$y$ に $1$ を足して繰り返す。どれかの段階で $g$ が未定義ならそこで停止せず、最小の $y$ がなければ永久に続く。

どの場合も、機械が停止するのは出力を得た後の標準出力に限ることを、構成から確かめられる。

∎

遷移表を一つずつ書き下すことは機械的ですが長いため、上では部品の連結の図式で記述しました。各部品が少数の状態の機械であること、連結が規則の追加と状態の改番で行えることは、読者が確かめられる範囲です。

定理 6.3（チューリング計算可能性と部分再帰性の一致）✓

部分関数 $f:\mathbb{N}^n\rightharpoonup\mathbb{N}$ について、次は同値である。

1. $f$ はチューリング計算可能である。
2. $f$ は部分再帰関数である。

証明（定理 6.3）

(1) $\Rightarrow$ (2) は 定理 5.4、(2) $\Rightarrow$ (1) は 定理 6.2。

∎

以後、「計算可能」はどちらの意味でも同じなので、単に計算可能な部分関数と呼びます。

6.1. チャーチ＝チューリングの提唱

注意 6.4（チャーチ＝チューリングの提唱）

提唱：直観的な意味でアルゴリズムによって計算できる関数は、チューリング計算可能な関数と一致する。

これは定理ではありません。「直観的に計算できる」が数学的に定義されていないからです。証拠は三つあります。(1) チューリング機械、部分再帰関数のほか、次章以降で扱う $\lambda$ 計算、レジスタ機械、文法による書き換えなど、独立に提案された形式がすべて同じクラスを与えた。(2) 知られているあらゆるアルゴリズムが機械で実現できた。(3) 反例になりうる「もっと強い」形式が見つかっていない。

この記事の定理（停止問題、ライスの定理）は、すべて機械や再帰関数の定義の上で証明されており、提唱には依存しません。提唱が必要になるのは、「この手順は機械にできる」と述べるときに遷移表を書く手間を省く場面と、「機械で決定不能なら、いかなるアルゴリズムでも決定不能だ」と解釈する場面だけです。

7. 停止問題

7.1. 決定不能性

機械の番号 $e$ が $\mathbb{N}$ の元なので、機械を入力として受け取る問題を考えられます。

定義 7.1（停止問題）↗

$K=\{\,e\in\mathbb{N}\mid\varphi^{(1)}_e(e)\downarrow\,\}$ を停止問題の集合という。機械 $M_e$ を自分自身の番号 $e$ を入力として走らせたとき、標準出力で停止するような $e$ の集合である。

定理 7.2（停止問題の決定不能性）✓

$K$ は決定可能ではない。一方、$K$ は半決定可能である。

証明の方針は次のとおりです。$K$ を判定する機械があると仮定し、それを使って「$K$ に入っていれば止まらず、入っていなければ $0$ で止まる」機械を作ります。この機械自身の番号を自分に入力すると、止まるなら止まらず、止まらないなら止まる、という矛盾が出ます。なお下の $\mu y\,[\chi_K(e)=0]$ では、条件に $y$ が現れませんが、それで構いません。$\chi_K(e)=0$ なら $y=0$ で探索が終わり、$\chi_K(e)=1$ ならどの $y$ でも条件が成り立たず、探索が永遠に続くだけだからです。

証明（定理 7.2）

決定不能性。$K$ が決定可能で、特性関数 $\chi_K$ がチューリング計算可能な全関数だとする。定理 5.4 から $\chi_K$ は部分再帰関数である。部分関数

$$h(e)\simeq\mu y\,[\chi_K(e)=0]$$

を考える。部分再帰関数の最小化の定義より、$h$ は部分再帰関数である。$e\notin K$ ならば $\chi_K(e)=0$ なので $h(e)=0$。$e\in K$ ならば $\chi_K(e)=1$ で、$y$ によらず $\chi_K(e)\ne0$ だから $h(e)\uparrow$。

定理 6.2 により $h$ はチューリング計算可能なので、ある $e_0$ について $h=\varphi^{(1)}_{e_0}$ である。ここで $e_0$ に自分自身を入力すると、

$$e_0\in K\iff\varphi^{(1)}_{e_0}(e_0)\downarrow\iff h(e_0)\downarrow\iff e_0\notin K$$

となり矛盾する。

半決定可能性。$e\mapsto\Phi^{(1)}(e,e)$ は部分再帰関数（定理 5.4）で、その定義域は $K$。定理 6.2 によりチューリング計算可能である。

∎

証明の骨格は、カントールの対角線論法（定理 7.1［濃度と無限］）と同じです。計算可能な部分関数を表の行 $\varphi_0,\varphi_1,\ldots$ に並べ、対角成分 $\varphi_e(e)$ を取り、それを反転させたものはどの行とも異なる、という議論です。反転が「定義されていれば未定義、未定義なら $0$」であるところだけが違います。

対角線論法。表の行は計算可能な部分関数 φ_e。対角成分を反転した関数 h は、どの行とも対角で食い違う。h が計算可能なら矛盾。

系 7.3（停止問題の補集合は半決定可能でない）✓

集合 $A$ と補集合 $\overline{A}=\mathbb{N}\setminus A$ がともに半決定可能ならば、$A$ は決定可能である。特に $\overline{K}$ は半決定可能でない。

証明（系 7.3）

$A=\mathrm{dom}(\varphi^{(1)}_a)$, $\overline{A}=\mathrm{dom}(\varphi^{(1)}_b)$ とする。「$M_e$ が $x$ から $t$ ステップ以内に標準出力で停止する」という述語 $H(e,x,t)$ は、定理 5.3 の $T_1$ を使って $\exists t'\le t\,T_1(e,x,t')$ と書け、原始再帰的である。$x$ ごとに $x\in A$ か $x\in\overline{A}$ のちょうど一方が成り立つので、$s(x)=\mu t\,[H(a,x,t)\vee H(b,x,t)]$ は全関数であり、$\chi_A(x)=\chi_{H(a,\cdot,\cdot)}(x,s(x))$ と書ける。$\chi_A$ は全域的な部分再帰関数なので、定理 6.2 により $A$ は決定可能である。$\overline{K}$ が半決定可能なら $K$ が決定可能になって 定理 7.2 に反する。

∎

注意 7.4（決定問題とのつながり）

一階述語論理の恒真な文の集合は半決定可能です。完全性定理（一階述語論理と完全性定理）により恒真な文には証明があり、証明は有限列で、証明の検査は機械的なので、証明候補を短い順に列挙して検査すればよいからです。ところが、チャーチとチューリングが示したように、この集合は決定可能ではありません（機械の動作を論理式で記述して停止問題へ帰着する。ここでは主張のみ述べます）。証明の存在を認めるアルゴリズムは作れても、証明が存在しないことを確認するアルゴリズムは存在しない、というのがヒルベルトの決定問題への答えです。この構図は、形式体系の定理の集合が半決定可能であるという事実とともに、不完全性定理の議論でも使われます。

8. ライスの定理

停止問題の次に問いたいのは、「機械が計算する関数が何かの性質をもつか」を機械の記述から判定できるか、ということです。答えは、自明でない性質については否定的です。

8.1. 番号を入れ替える道具

補題 8.1（パラメータの固定（s-m-n））✓

$G$ を 2 変数関数 $\varphi^{(2)}_G$ を計算する機械の番号とする。このとき、原始再帰的な全関数 $s$ が存在して、すべての $e,y$ について

$$\varphi^{(1)}_{s(e)}(y)\simeq\varphi^{(2)}_G(e,y)$$

が成り立つ。

証明（補題 8.1）

$e$ を固定し、機械 $P_e$ を次の規則で定める（状態 $0,1,\ldots,e+3$）。

$$(0,1)\mapsto(1,1,L),\quad(1,0)\mapsto(2,0,L),\quad(2+i,0)\mapsto(3+i,1,L)\ (0\le i\le e),\quad(e+3,0)\mapsto(e+4,0,R).$$

標準入力 $1^{y+1}$（最左の $1$ の位置を $p$ とする）から始めると、$P_e$ は位置 $p-1$ を空白のままにして、$p-2,p-3,\ldots,p-2-e$ に $1$ を $e+1$ 個書き、位置 $p-2-e$ の最左の $1$ に立つ状態 $e+4$ で終わる。テープは $1^{e+1}\,0\,1^{y+1}$、つまり $(e,y)$ の標準入力である。

$M_G$ の各状態 $q$ を $q+e+4$ に付け替えたものを $P_e$ に続けた機械を $M_{s(e)}$ とする。付け替えた開始状態が $e+4$ である。この機械は、入力 $y$ に対して $\varphi^{(2)}_G(e,y)$ を計算する。番号 $s(e)$ は、$P_e$ の規則に対応する素数のべき（定義 5.1 の符号化に従う）と、$G$ の各規則を状態番号を $e+4$ ずらして符号化したものの積に $-1$ した数で、有界な範囲の素数べきの積だから原始再帰的に計算できる。

∎

8.2. ライスの定理

定理 8.2（ライスの定理）✓

$\mathcal{P}$ を 1 変数の計算可能な部分関数の集合とし、$A_{\mathcal{P}}=\{\,e\mid\varphi^{(1)}_e\in\mathcal{P}\,\}$ とする。$\mathcal{P}$ が空でも全体でもなければ、$A_{\mathcal{P}}$ は決定可能でない。

証明（定理 8.2）

どの $x$ でも未定義な関数を $\bot$ とする（常に右へ動き続ける機械で計算できる）。

$\bot\notin\mathcal{P}$ の場合。 $\mathcal{P}\ne\varnothing$ なので $\varphi^{(1)}_{e_1}\in\mathcal{P}$ となる $e_1$ を一つ取る。2 変数の部分関数

$$g(e,y)\simeq\Phi^{(1)}\bigl(e_1,\ y+0\cdot\Phi^{(1)}(e,e)\bigr)$$

を考える。$\Phi^{(1)}(e,e)$ が定義されるのは $e\in K$ のときに限り、そのとき $g(e,y)=\varphi^{(1)}_{e_1}(y)$。$e\notin K$ のときは $g(e,y)\uparrow$（合成で未定義が伝わる）。$g$ は部分再帰関数の合成だから部分再帰関数で、定理 6.2 によりある $G$ について $g=\varphi^{(2)}_G$。補題 8.1 の $s$ をとると

$$e\in K\ \Rightarrow\ \varphi^{(1)}_{s(e)}=\varphi^{(1)}_{e_1}\in\mathcal{P},\qquad e\notin K\ \Rightarrow\ \varphi^{(1)}_{s(e)}=\bot\notin\mathcal{P}.$$

したがって $e\in K\iff s(e)\in A_{\mathcal{P}}$、すなわち $\chi_K=\chi_{A_{\mathcal{P}}}\circ s$。$A_{\mathcal{P}}$ が決定可能なら、$\chi_{A_{\mathcal{P}}}$ も $s$ も部分再帰関数なので $\chi_K$ も（部分再帰関数の合成として）計算可能になり、定理 7.2 に反する。

$\bot\in\mathcal{P}$ の場合。 補集合 $\mathcal{P}^{c}$（計算可能な 1 変数部分関数のうち $\mathcal{P}$ に属さないもの）は空でなく $\bot\notin\mathcal{P}^{c}$ なので、前の場合から $A_{\mathcal{P}^c}$ は決定可能でない。$A_{\mathcal{P}^c}=\mathbb{N}\setminus A_{\mathcal{P}}$ だから、$A_{\mathcal{P}}$ が決定可能なら補集合も決定可能となり矛盾する。

∎

例 8.3（ライスの定理の応用）

次の集合はいずれも決定可能でありません（$\mathcal{P}$ は空でも全体でもない）。

• $\{e\mid\varphi_e\text{ が全関数}\}$（機械が全入力で停止するか）。
• $\{e\mid\varphi_e(0)\downarrow\}$（入力 $0$ で停止するか）。
• $\{e\mid\varphi_e\text{ は定数関数}\}$。
• $\{e\mid\varphi_e=\varphi_{e'}\}$（$e'$ を固定。二つの機械が同じ関数を計算するか）。

プログラムの「意味」に関する自明でない問いは、静的解析で完全には判定できない、という事実の数学的な根拠です。一方、機械の記述に関する問い（規則が 5 個以下か、状態番号が偶数か）は、$\varphi_e$ が同じでも $e$ によって答えが変わるので $A_{\mathcal{P}}$ の形ではなく、決定可能です。

9. 演習

演習 9.1標準

フィボナッチ数列 $F(0)=0$, $F(1)=1$, $F(n+2)=F(n+1)+F(n)$ は原始再帰的な関数であることを示せ。（原始再帰の定義は $f(y+1)$ が $f(y)$ のみに依存する形であることに注意する。）

解答

$G(n)=2^{F(n)}3^{F(n+1)}$ を考える。$G(0)=2^03^1=3$。$G(n+1)=2^{F(n+1)}3^{F(n+2)}=2^{(G(n))_1}\cdot3^{(G(n))_0+(G(n))_1}$ なので、$G(n+1)$ は $G(n)$ の原始再帰的な関数であり、$G$ は原始再帰で定義できる（命題 3.2 (5) の $(\cdot)_i$ と冪、加法を使う）。そして $F(n)=(G(n))_0$ は $G$ と $(\cdot)_0$ の合成なので原始再帰的である。

演習 9.2標準

$B=\{\,e\mid\varphi^{(1)}_e(0)\downarrow\,\}$ は半決定可能だが決定可能でないことを示せ。

解答

$B$ は $e\mapsto\Phi^{(1)}(e,0)$ の定義域であり、この関数は 定理 5.4 により部分再帰的、定理 6.2 により計算可能だから、$B$ は半決定可能。決定可能でないことは、$\mathcal{P}=\{f\mid f(0)\downarrow\}$ にライスの定理 (定理 8.2) を使う。$\mathcal{P}$ は定数関数 $0$（機械 $Z$ で計算できる）を含むので空でなく、$\bot\notin\mathcal{P}$ より全体でもない。

演習 9.3難

全関数 $g:\mathbb{N}^2\to\mathbb{N}$ で、すべての計算可能な全関数 $f:\mathbb{N}\to\mathbb{N}$ について、ある $e$ が存在して $f=g(e,\cdot)$ となるものは、計算可能でないことを示せ。（部分関数なら万能関数 $\Phi$ は計算可能であった。全関数に制限すると何が起こるか。）

解答

$g$ がそのような計算可能な全関数だとする。$d(x)=g(x,x)+1$ は計算可能な全関数。よって $d=g(e_0,\cdot)$ となる $e_0$ が存在し、$d(e_0)=g(e_0,e_0)$ だが定義から $d(e_0)=g(e_0,e_0)+1$ で矛盾。万能関数が部分関数であることは、対角成分が未定義になって対角線論法が働かないための必然的な条件である。

参考文献

• A. M. Turing, “On Computable Numbers, with an Application to the Entscheidungsproblem”, Proceedings of the London Mathematical Society (2) 42 (1936), 230–265.
• S. C. Kleene, “General recursive functions of natural numbers”, Mathematische Annalen 112 (1936), 727–742.
• H. G. Rice, “Classes of recursively enumerable sets and their decision problems”, Transactions of the American Mathematical Society 74 (1953), 358–366.
• M. Davis, Computability and Unsolvability, McGraw-Hill, 1958（Dover 版 1982）。
• H. Rogers Jr., Theory of Recursive Functions and Effective Computability, McGraw-Hill, 1967。
• 田中一之編『ゲーデルと 20 世紀の論理学』東京大学出版会、2006–2007。