数学の基礎

再帰関数とチューリング機械

アルゴリズムで計算可能な関数を正確に定義する形式的モデル。

直観機械は何を計算できるか?

電卓は足し算と掛け算ができ、コンパイラは型検査ができ、AIは(時に)質問に答えられる。しかし、どんなに賢いアルゴリズムでも決して計算できない関数は存在するだろうか?アラン・チューリングの答えは「ある」——それは「アルゴリズム」の精密な数学的モデル、すなわちテープ、読み書きヘッド、有限の規則表からなるチューリング機械から得られた。一見異なる2つの形式化、再帰関数(合成と再帰によって単純な部品から構成される)とチューリング機械(機械的な段階的過程)は、まったく同じ関数のクラスを計算することが判明した——これはチャーチ–チューリングの提唱、すなわちこれこそが「計算可能なものすべて」であるという主張の強力な証拠である。

小さなチューリング機械の状態遷移グラフ:頂点が状態、辺が(読み取り→書き込み、移動)でラベル付けされた遷移である。

大学原始再帰関数と $\mu$ -再帰関数

定義: 原始再帰関数

原始再帰関数とは、零関数、後続関数 $S(n)=n+1$ 、およびすべての射影を含み、合成と原始再帰の下で閉じている、 $\mathbb N^k \to \mathbb N$ の関数の最小のクラスである: $g:\mathbb N^k\to\mathbb N$ と $h:\mathbb N^{k+2}\to\mathbb N$ が与えられたとき、再帰 $f(\vec x,0)=g(\vec x)$ 、 $f(\vec x,n+1)=h(\vec x,n,f(\vec x,n))$ は新しい原始再帰関数 $f$ を定義する。加法、乗法、冪乗、そして固定された上限を持つあらゆる「forループ」プログラムはすべて原始再帰的である——そしてすべての原始再帰関数は全域的(すべての入力に対して定義される)であり、各入力について有界なステップ数で停止する。

f(\vec x,0)=g(\vec x), \qquad f(\vec x,n+1)=h(\vec x,n,f(\vec x,n))

すべての計算可能関数——停止しないかもしれないものも含めて——を捉えるには、もう一つの演算子を加える。** $\mu$ -再帰(一般再帰)関数は非有界最小化**を加える: $\mu y.\,[P(\vec x,y)=0]$ は $P(\vec x,y)=0$ となる最小の $y$ を返し、 $y=0,1,2,\dots$ と探索する——そしてそのような $y$ が存在しなければ単に決して返らない。これこそが $\mu$ -再帰関数に停止しない能力を与えるものであり、クリーネの定理はそれらがチューリング機械とまったく同じ(部分)関数のクラスを計算することを示している。

\mu y.\,[P(\vec x,y)=0] = \min\{y : P(\vec x,y)=0\}

原始再帰と一般( $\mu$ -)再帰とチューリング計算可能性の比較
クラス	構成要素	必ず停止するか?	例
原始再帰	合成+有界再帰	はい、常に全域的	$+,\times,$ 冪乗
一般( $\mu$ -)再帰	原始再帰+非有界 $\mu$	いいえ、無限に回る場合がある	アッカーマン関数 $A$
チューリング計算可能(部分的)	状態+テープ+遷移規則	いいえ、 $\mu$ -再帰と厳密に一致	あらゆるアルゴリズム

定理: 停止問題の決定不可能性

すべてのプログラム索引 $e$ と入力 $x$ について、 $\varphi_e(x)$ (プログラム $e$ を入力 $x$ で実行すること)が停止するかどうかを常に停止して正しく出力するアルゴリズム $H(e,x)$ は存在しない。

なぜ正しいのか?

これは、どのアンチウイルスソフト、コンパイラ、IDEも、無限ループ、デッドコード、「この関数は常にクラッシュする」といったことを完全に一般的な形で検出できない数学的理由である——今日の工学の限界ではなく、揺るぎない数学の壁である。

証明

背理法で、そのような判定器 $H$ が存在すると仮定する: $\varphi_e(x)\!\downarrow$ (停止する)なら $H(e,x)=1$ 、 $\varphi_e(x)\!\uparrow$ (永遠に走る)なら $H(e,x)=0$ であり、 $H$ 自身は常に停止し正しい答えを出す。

$H$ を用いて、入力 $e$ に対し次のように動作する新しいプログラム $D$ を作る: $H(e,e)$ を計算し、 $H(e,e)=1$ なら $D$ は無限ループに入り、 $H(e,e)=0$ なら $D$ は直ちに停止する。 $D$ は $H$ から実効的に構成される(単に $H$ に if 文とループを加えただけ)ので、あるプログラム索引 $d$ を持つ、すなわち $D=\varphi_d$ 。

ここで自己言及的な問いを立てる: $\varphi_d(d)$ は停止するか?

場合1: $\varphi_d(d)$ が停止するなら、 $H$ の正しさにより $H(d,d)=1$ 。しかし $D$ の定義により $H(d,d)=1$ は $D$ を入力 $d$ で無限ループさせる——すなわち $\varphi_d(d)$ は停止しない。矛盾。

場合2: $\varphi_d(d)$ が停止しないなら、 $H$ の正しさにより $H(d,d)=0$ 。しかし $D$ の定義により $H(d,d)=0$ は $D$ を入力 $d$ で停止させる——すなわち $\varphi_d(d)$ は停止する。矛盾。

どちらの場合も矛盾するので、 $H$ が存在するという仮定は偽である。停止問題は決定不可能である。 $\blacksquare$

発展ライスの定理

停止問題は、より広い現象のほんの一例に過ぎない。部分計算可能関数の性質 $P$ が、プログラム $e$ が計算する関数 $\varphi_e$ のみに依存し、ソースコード自体には依存しないとき意味論的と呼び、ある計算可能関数がそれを持ちある関数が持たないとき非自明と呼ぶ。

定理: ライスの定理

部分計算可能関数のすべての非自明な意味論的性質 $P$ について、集合 $\{e : \varphi_e \text{ has property } P\}$ は決定不可能である。

なぜ正しいのか?

この一つの定理は、「このプログラムはゼロ関数を計算するか」「このプログラムは全域関数を計算するか」「これら2つのプログラムは等価か」といった、プログラムの振る舞いに関する無数の自然な問いに対するアルゴリズムを、それぞれ別々の対角線論法なしに、一挙に排除する。

証明

一般性を失うことなく、いかなる入力に対しても決して停止しないプログラムが計算する至る所未定義の関数 $\emptyset$ が性質 $P$ を持たないと仮定する——そうでなければ、 $P$ が決定可能であることとちょうど同値な補性質 $\lnot P$ で議論する。 $P$ は非自明なので、その関数 $\varphi_{e_0}$ が性質 $P$ を持つプログラム $e_0$ を一つ固定する。

背理法で、 $P$ がある判定アルゴリズム $D$ によって決定可能であると仮定する(プログラム索引が与えられると、 $D$ は停止し、そのプログラムの関数が性質 $P$ を持つかどうかを正しく報告する)。 $P$ に停止問題を還元し、定理1と矛盾させる。

任意の組 $(e,x)$ に対し、実効的に(単純な文字列操作——クリーネの s-m-n 定理により)新しいプログラム $e'$ を構成する。 $e'$ は任意の入力 $y$ について:まずプログラム $e$ を入力 $x$ で実行するシミュレーションを行い、そのシミュレーションが停止したら、次にプログラム $e_0$ を入力 $y$ でシミュレーションしてその出力を出力する。

2つの場合を調べる。 $e$ が $x$ で停止する場合: $e$ を $x$ で実行するシミュレーションは終了するので、 $e'$ はその後すべての入力で $e_0$ とまったく同じように振る舞う、すなわち $\varphi_{e'}=\varphi_{e_0}$ ——これは性質 $P$ を持つ( $P$ は意味論的なので計算される関数のみに依存し、 $\varphi_{e_0}$ は $P$ を持つ)。 $e$ が $x$ で停止しない場合: $e$ を $x$ で実行するシミュレーションは決して終わらないので、 $e'$ はいかなる入力 $y$ についても $e_0$ のシミュレーション段階に決して到達しない。したがって $\varphi_{e'}$ は至る所未定義の関数 $\emptyset$ であり、仮定によりこれは性質 $P$ を持たない。

よって: $e$ が $x$ で停止する $\iff$ $\varphi_{e'}$ が性質 $P$ を持つ $\iff$ $D(e')$ が「はい」と答える。 $(e,x)\mapsto e'$ は計算可能なので、「 $(e,x)$ から $e'$ を計算し、 $D(e')$ を実行する」というアルゴリズムは停止問題を決定してしまう——定理1と矛盾する。したがってそのような $D$ は存在しない: $P$ は決定不可能である。 $\blacksquare$

大学実世界での応用と具体例

コンパイラの最適化器は「このコードは到達可能か」「この変数の値は意味を持つか」といったことを判定しなければならない——ライスの定理により、これらは完全に一般的な形では決定不可能であり、まさにそれゆえ実際のコンパイラは保守的な近似を用いる(生きたコードを削除する危険を冒すより、本当に死んでいるコードの一部を残しておく)。ビジービーバー関数 $BB(n)$ —— $n$ 状態の停止するチューリング機械が停止するまでにとりうる最大のステップ数——は具体的で計算不可能な関数である:既知の値は $BB(1)=1$ 、 $BB(2)=6$ 、 $BB(3)=21$ 、 $BB(4)=107$ であり、2024年には共同プロジェクト Busy Beaver Challenge(Tristan Stérin らが主導し、「mxdys」という偽名の貢献者による Coq 検証済みの証明を伴う)が $BB(5)=47{,}176{,}870$ を確立した——この「単純」に見える組合せ論的問いですら、一般的なアルゴリズムでは決して計算できず、場合ごとにしか計算できないことを示している。

例: アッカーマン関数 $A(2,2)$ を展開する

規則 $A(0,n)=n+1$ 、 $m>0$ に対し $A(m,0)=A(m-1,1)$ 、 $m,n>0$ に対し $A(m,n)=A(m-1,A(m,n-1))$ を用いて $A(2,2)$ を段階的に計算し、アッカーマン関数が全域的でありながら原始再帰的ではない理由を説明せよ。

解答

第三の規則により $A(2,2)=A(1,A(2,1))$ 。まず $A(2,1)=A(1,A(2,0))$ が必要で、第二の規則により $A(2,0)=A(1,1)$ 。

$A(1,1)=A(0,A(1,0))=A(0,A(0,1))=A(0,2)=3$ (第二と第一の規則で2回展開)。よって $A(2,0)=A(1,1)=3$ なので $A(2,1)=A(1,3)$ 。

$A(1,3)=A(0,A(1,2))$ であり、 $A(1,2)=A(0,A(1,1))=A(0,3)=4$ 。よって $A(1,3)=A(0,4)=5$ 。したがって $A(2,1)=5$ 。

最上位に戻る: $A(2,2)=A(1,A(2,1))=A(1,5)=A(0,A(1,4))$ ; $A(1,4)=A(0,A(1,3))=A(0,5)=6$ と展開;よって $A(1,5)=A(0,6)=7$ 。したがって $A(2,2)=7$ 。

アッカーマン関数は全域的であることが証明されている(最終的に必ず $A(0,n)$ の場合に帰着する)ので、一般再帰関数のクラスに属する——しかしあらゆる原始再帰関数より速く増大する(例えば $A(3,n)=2^{n+3}-3$ 、 $A(4,n)$ はすでに指数のタワーである)。あらゆる原始再帰関数が最終的にある固定された $A(k,\cdot)$ によって支配されることが示せるので、原始再帰関数が $A$ 自身に等しくなることはあり得ない—— $\mu$ 演算子ではなく、この対角線論法風の支配論法こそが、全域的であるにもかかわらずアッカーマン関数を原始再帰の外に置く理由である。

例: 停止問題を「このプログラムはhelloを出力するか?」に還元する

「プログラム $e$ が与えられたとき、 $e$ を(入力なしで)実行すると文字列 `hello` が出力されることがあるか?」という問題が、ライスの定理を使わずに、停止問題からの直接還元により決定不可能であることを示せ。

解答

背理法で、 $e$ を実行すると `hello` が出力されるかどうかを決定するアルゴリズム $Q(e)$ が存在すると仮定する。 $Q$ を用いて停止問題を決定し、定理1と矛盾させる。

任意のプログラム $e$ と入力 $x$ が与えられたとき、実効的に新しいプログラム $e'$ (入力不要)を構成する: $e$ を $x$ で実行するシミュレーションを行い、それが停止したら $e'$ は `hello` を出力して停止する。

$e$ が $x$ で停止する場合:シミュレーションは終了するので $e'$ は出力段階に到達し `hello` を出力する。 $e$ が $x$ で停止しない場合:シミュレーションは決して終わらないので $e'$ は出力段階に決して到達せず `hello` を決して出力しない。

よって $e$ が $x$ で停止する $\iff$ $Q(e')$ が「はい」と答える。 $(e,x)\mapsto e'$ は計算可能なので、「 $e'$ を構成し $Q(e')$ を実行する」ことで停止問題が決定できてしまう——定理1と矛盾する。よって $Q$ は存在し得ない:「helloを出力する」問題は決定不可能である。(これはまさにコンパイラ解析のパターンである:「このコード行は到達可能か」も同じ形をしている。)

よくある誤り. 「決定不可能」と「認識不可能」を混同してはならない。停止問題は認識可能(半決定可能)である:

\varphi_e(x)

をシミュレートし、停止した瞬間に「はい」と出力する機械は、答えが「はい」のとき必ず正しく「はい」と言う——ただ「いいえ」の場合には永遠に走り続けるかもしれない。不可能なのは、答えが「いいえ」のときも正しく速やかに「いいえ」と出力する機械である。学生はしばしば「決定不可能」を「停止した実行さえ確認できない」ことだと誤解するが、これは誤りである——停止そのものは事後に確認するのは容易であり、不可能なのは一般的な予測の方である。

歴史的ノート

1936年、アラン・チューリングの論文「計算可能数について、決定問題への応用とともに」はチューリング機械を導入し、停止問題が決定不可能であることを証明した。これは同年のアロンゾ・チャーチによる同等のラムダ計算の論証とともに、独立にヒルベルトの決定問題を解決した——チャーチ–チューリングの提唱の誕生である。ヴィルヘルム・アッカーマンは、原始再帰的でない全域計算可能関数の最初の既知の例として、すでに1928年に急増加関数を発表していた(もともとアッカーマンとダフィット・ヒルベルトによって研究された)。ヘンリー・ゴードン・ライスは1953年に自身の定理を証明し、決定不可能性を一つの具体的な問題から問題全体の族へと一般化した。

アラン・チューリング

$A(1,n)=n+2$ を用いると $A(1,3)$ はいくつか?

コンパイラ設計にとって停止問題の決定不可能性がもたらす帰結はどれか?

ライスの定理が適用されない性質はどれか?

停止問題の決定不可能性の対角線論法による証明で、何が矛盾を引き起こすか?

参考文献

Wikipedia contributors (2024). Halting problem
Wikipedia contributors (2024). Rice's theorem
Wikipedia contributors (2024). Ackermann function