計算モデルの体系（チューリング機械・λ計算・帰納関数）

なぜ複数のモデルを並べて学ぶのか

「計算できる」とは何かを厳密に定義しようとすると、唯一の正解は存在しません。1930年代、複数の数学者がそれぞれ別の出発点から「計算」を形式化しました。チューリングはテープを動く機械から、チャーチは関数の置き換えから、ゲーデルとクリーネは自然数上の関数から。驚くべきは、まったく似ていない4つの定義が、結局まったく同じ計算能力に行き着いたことです。この一致が、計算可能性という概念に客観的な実体を与えます。実務的には「どの言語でも書ける問題の範囲は同じ」という事実の理論的な裏付けであり、停止性問題の限界がモデルを変えても回避できない理由でもあります。

4つの計算モデルの起源

まず系統を年代で押さえます。

チャーチとチューリングはほぼ同時期に発表し、チューリングが自身の機械とλ計算の等価性を証明したことで、両者は同じものを別の角度から見ていたと判明しました。レジスタ機械は後発ですが、現実のCPUに最も近く、抽象モデルと実機の橋渡しになります。

チューリング機械：記号の書き換え

チューリング機械は、左右に無限のマス目を持つテープ、現在位置を指すヘッド、有限個の内部状態、そして遷移規則からなります。遷移規則は「いまの状態と読んでいる記号」に対して「書き込む記号・ヘッドの移動方向（左右）・次の状態」を一意に定めます。

状態 q0 で記号 1 を読んだら → 記号 0 を書き、右へ移動、状態 q1 へ

部品はこれだけです。それでも、テープが任意に長く使える点が本質で、有限の規則表で無限に大きな入力を扱えることが計算可能性の鍵になります。性能や使い勝手ではなく、何が計算できるかの境界を定めるためのモデルである点を見失わないでください。

λ計算：置き換えだけの計算

λ計算は構文が3種類しかありません。変数 x、関数の定義である抽象 λx. M、関数呼び出しである適用 M N です。計算規則も本質的に1つで、関数に引数を渡したとき本体の仮引数を実引数で置き換えるβ簡約だけです。

(λx. λy. x) A B   →   (λy. A) B   →   A

自然数すらプリミティブにありませんが、関数の入れ子で表現できます（チャーチ数）。0 を「何もしない」、後続を「もう一回適用する」と定義する流儀です。条件分岐・対・再帰も同様に項として書け、計算能力はチューリング機械と等価です。λ計算の数学的な掘り下げは型理論の基礎（ラムダ計算と型付け）に譲ります。なお評価戦略（正規順序・値呼びなど）はβ簡約のどこを先に縮約するかの選択であり、計算能力ではなく停止しやすさや効率に影響します。

帰納的関数：関数を積み上げる

帰納的関数は、自然数上の関数を素朴な部品から組み立てます。基本関数は次の3つです。

• ゼロ関数（常に0を返す）
• 後続関数（n に対し n+1 を返す）
• 射影関数（引数の組から1つを取り出す）

これらを次の操作で合成していきます。

合成と原始再帰だけで作れる原始帰納関数は加減乗除や指数など実用的な関数をほぼ覆い、しかも必ず停止します。しかしこれだけでは足りません。アッカーマン関数は全域（あらゆる入力で停止する）でありながら、有界な原始再帰では表せず、原始帰納関数の真の外側にあります。ここに最小化（μ作用素、「述語が真になる最小の引数を探す」探索）を加えて初めて、計算可能な関数すべて＝一般帰納的関数に届きます。最小化は探索が終わらない可能性を持ち込み、その代償として停止しない計算も表現できるようになります。これは再帰が一般には停止保証を持たないことの理論的な裏返しです。

レジスタ機械：実機への橋渡し

レジスタ機械は、無限個の番地付きレジスタ（各々に自然数を格納）と、ごく少数の命令だけを持ちます。代表的な最小命令は「指定レジスタを1増やす」「1減らす（0なら別の行へ分岐）」と無条件ジャンプです。これだけでチューリング機械と等価になります。現代のアセンブリやバイトコードの祖型であり、抽象モデルが現実の計算機と地続きであることを示します。

等価性はどう示すのか：相互シミュレーション

4モデルが「同じ強さ」とは、任意の一方を他方が模倣（シミュレート）できるという意味です。能力の包含を双方向に示せば、計算できる関数のクラスが一致します。

• チューリング機械でλ計算を実装する：項をテープ上の記号列で表し、β簡約をヘッドの書き換え操作として実装する。
• λ計算でチューリング機械を実装する：テープ・状態・規則表を項としてエンコードし、1ステップの遷移を関数適用で表す。
• レジスタ機械でチューリング機械を：テープ内容をレジスタにエンコードし、遷移をインクリメント・デクリメント・分岐で実現する。

この相互変換が一巡してつながるため、どこから出発しても到達できる関数のクラスは同一です。決定的な傍証が万能チューリング機械の存在です。「機械の記述」と「入力」を受け取り、その機械の動作を再現する1台の機械を作れます。プログラムをデータとして扱う発想（格納プログラム方式）の原型であり、インタプリタそのものの数学的な姿です。

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

これらの等価性を踏まえて立つのがチャーチ・チューリングのテーゼです。主張は「直感的な意味で計算可能な関数は、すべてチューリング機械で計算できる（＝一般帰納的関数と一致する）」というもの。

量子計算機もこの枠を破りません。量子計算機が変えるのは計算量（速さ）であって、計算可能性（解けるか否か）の境界ではなく、計算できる関数のクラスはチューリング機械と同じです。

実務に効く帰結

• どの汎用言語も、チューリング完全である限り計算能力は等価です。言語選択は「何が書けるか」ではなく、表現のしやすさ・性能・エコシステムの問題に還元されます。
• 停止性問題や計算可能性の限界は、モデルを乗り換えても消えません。等価なモデルは限界も共有します。
• 表現力をあえて落とした言語（正規言語、全域言語、純粋なクエリ言語など）はチューリング完全より弱く、その代わり停止性などを静的に保証できます。表現力と検証可能性のトレードオフは、この体系から直接導けます。

まとめ

チューリング機械・λ計算・帰納的関数・レジスタ機械は、出発点も見た目もまるで違うのに、相互シミュレーションによって同一の計算能力を持つことが示せます。この一致がチャーチ・チューリングのテーゼ——計算可能性という概念の客観的な核——を支えます。テーゼは証明された定理ではなく、複数の独立した道がすべて同じ場所に通じたという事実に立つ主張です。計算理論を「機械の話」ではなく「計算という概念そのものの話」として捉え直せたとき、言語やパラダイム（プログラミングパラダイム）の違いは能力差ではなく表現の選択にすぎないと、はっきり見えてきます。