第11章計算可能性 — 計算モデル

「計算できる」とは、正確に何か

「 $2+3$ を計算する」「素数かどうか判定する」——私たちは「機械的に計算できる」を直感で使っています。でも、この直感を数学の定義にできるでしょうか？「有限の手順で、迷わず、必ず答えに至る」—— これを厳密化しない限り、「計算できない問題がある」とは言えません。

1930年代、複数の数学者が独立にこの直感を形式化しました。チューリングは「紙と鉛筆の作業を極限まで単純化した機械」、ゲーデルとエルブランは「基本関数から組み上げる帰納的関数」、チャーチは「関数を記号変形で計算するλ計算」。驚くべきことに、これらはすべて同じ関数のクラスを定める。この一致が、「計算可能とはこういうことだ」という確信——チャーチ–チューリングのテーゼ——を生みます。この章は、次章で「計算できないもの」を示すための土台を据えます。

「機械的に計算できる」を、チューリング機械・帰納的関数・λ計算で厳密化する。三者は一致する。

チューリング機械

紙の上の計算を、これ以上単純にできないところまで削ぎ落とした模型です。

定義チューリング機械

チューリング機械は、両方向に無限のテープ（マス目に記号を書く）、その上を動くヘッド、有限個の内部状態、そして遷移規則からなる。遷移規則は「（現在の状態, ヘッド下の記号） $\mapsto$ （書く記号, ヘッドの移動左/右, 次の状態）」の有限表。入力をテープに置いて始動し、停止状態に達したらテープの内容が出力。停止しないこともある。

たったこれだけ——有限の状態表とテープ——で、あらゆる計算が模倣できます。要点は2つ。第一に、機械が計算するのは 部分関数：入力によっては停止せず値を返さない（この“停止しない”が次章の主役）。第二に、機械そのものを記号列で符号化でき、それを入力にできること。

定理万能チューリング機械

ある一台のチューリング機械 $U$ が存在し、任意の機械 $M$ の符号 $\langle M\rangle$ と入力 $x$ を受け取って、 $M$ が $x$ 上で行う計算をそっくり模倣する（ $U(\langle M\rangle,x)=M(x)$ ）。

「プログラムをデータとして受け取り実行する機械」——これはまさに現代のプログラム内蔵式コンピュータの原理です。 $U$ の存在が、次章の対角線論法（自分自身への適用）を可能にします。

帰納的関数

計算を「機械」でなく「関数の組み立て」で捉える流儀です。ごく少数の基本関数から、2つの操作で閉じたクラスを作ります。

定義原始帰納的関数と μ再帰

基本関数：ゼロ関数 $0$ 、後者関数 $S(n)=n+1$ 、射影 $P^n_i(x_1,\dots,x_n)=x_i$ 。これらから合成と原始帰納法（ $f(0,\bar y)=g(\bar y),\ f(n{+}1,\bar y)=h(n,f(n,\bar y),\bar y)$ ）で得られる関数を原始帰納的という。さらに最小化（μ作用素） $\mu m[f(m,\bar y)=0]$ （ $f(m,\bar y)=0$ となる最小の $m$ を返す；無ければ未定義）を許して得られるのが（部分）帰納的関数。

原始帰納的関数は「あらかじめ回数の決まったループ（for 文）」に対応し、加減乗除・階乗・素数判定などほぼ全ての日常的関数を含みます。しかしすべての計算可能関数は尽くせません（アッカーマン関数は計算可能だが原始帰納的でない）。足りないのは「いつ終わるか分からないループ（while 文）」——それを与えるのが μ作用素です。 μ再帰は「条件を満たす最小の数を探して止まる（見つからなければ止まらない）」探索で、この“止まらないかもしれない”性質が、部分関数性＝計算可能性の本質を捉えます。

λ計算

チャーチのλ計算は、関数を「記号変形」だけで計算する、極限まで削ぎ落とした模型です。関数の適用と抽象しかありません。

定義 λ項とβ簡約

λ項：変数 $x$ 、抽象 $\lambda x.M$ （“ $x$ を受け取り $M$ を返す関数”）、適用 $(M\,N)$ 。計算はβ簡約 $(\lambda x.M)\,N \to M[x:=N]$ （引数を代入する）だけ。

数も真偽もデータ構造も、すべてλ項で表現できます。例えば自然数 $n$ を「関数を $n$ 回適用する」高階関数（チャーチ数 $\underline n=\lambda f.\lambda x.f(f(\cdots f\,x))$ ）として符号化すると、加算・乗算・前者関数・再帰（不動点コンビネータ $Y$ ）がすべてλ項として書け、β簡約が計算になります。純粋な関数の変形だけでチューリング機械と同じ計算能力をもつ——これが関数型プログラミング（Lisp, Haskell）の理論的源流です。

チャーチ–チューリングのテーゼ

3つの独立した定義が、同じクラスに落ち着きます。

定理計算モデルの同値

次の関数のクラスは完全に一致する：チューリング機械で計算可能な部分関数、部分帰納的関数、λ定義可能な関数。（さらにレジスタ機械、文法、セルオートマトンなども同じ。）

定義チャーチ–チューリングのテーゼ

直感的に「機械的・有限的手続きで計算できる」関数は、ちょうど（部分）帰納的関数に一致する——という主張。これは定理ではなくテーゼ（提唱）：「機械的に計算できる」という直感的概念と、数学的に定義されたクラスの一致を述べており、直感の側を証明対象にできない。しかし独立な多数のモデルが同じクラスに収束したことが、テーゼの強い状況証拠になっている。

テーゼが定理でない点は重要です。それでも、これほど異質な定義（機械・関数・記号変形）が寸分違わず一致した事実は、「計算可能性」が人為的な定義ではなく発見された自然な概念であることを強く示唆します。以後、私たちは安心して「計算可能（＝帰納的）」を一つの数学的対象として扱えます。テーゼがあるおかげで、次章で「この問題は どんな機械でも解けない」と、特定のモデルに縛られず結論できるのです。

つまずきポイント

注意よくある誤解

計算可能関数は部分関数。 入力によっては停止せず値を返さない。「全域で計算可能」と「計算可能」は別（前者を保証する一般手段は無い＝次章）。
原始帰納的 ⊊ 帰納的。 for 文だけ（原始帰納）では全計算可能関数を尽くせない。while 文（μ作用素・停止しうる探索）が本質的に必要。
チャーチ–チューリングのテーゼは証明できない。 「直感的計算可能」という非形式概念が片側にあるため。数学的クラスどうしの一致（機械＝帰納的＝λ）は定理だが、テーゼ自体は提唱。

この章のまとめ

チューリング機械（テープ＋状態表）は計算を極限まで単純化した模型で、万能機械 $U$ がプログラムをデータとして実行する。計算するのは部分関数。
帰納的関数は基本関数＋合成＋原始帰納法（for）＋μ作用素（while＝停止しうる探索）。μ作用素が全計算可能関数に届く鍵。λ計算は関数の適用・抽象とβ簡約だけで同じ能力をもつ。
三者は一致し、チャーチ–チューリングのテーゼ（直感的計算可能＝帰納的）を支える。テーゼは定理でなく提唱だが、独立モデルの収束が強い根拠。

次章は、この計算モデルを使って「原理的に計算できない問題」——停止性問題と決定不能性——を証明します。

第11章 計算可能性 — 計算モデル