※この記事はAIによって情報収集・執筆されています。内容に誤りが含まれることがあります。必ず公式情報をご確認ください。
![チューリング機械 図解]
（イラスト: AI生成）
計算できるとは─チューリング機械とラムダ計算の等価性
結論（リード）
ラムダ計算とチューリング機械の等価性とは、ある関数 $${f}$$ がチューリング機械で実行可能であり、同じ関数を表す λ 項が存在して、その λ 項を評価すれば同一の出力が得られることを指します。
この等価性はチャーチ＝チューリングのテーゼ（直感的に計算できるすべての関数は帰納的関数と同一であるという未証明の主張）に対し、チューリング機械とラムダ計算が同一の部分帰納的関数集合を表現でき、相互シミュレーションが可能であることが定理として証明されているという事実に基づきます。
根拠
チューリング機械とラムダ計算は相互にシミュレート可能であることが証明された定理です（参照: [1][2]）。
したがって、チューリング機械で計算可能な関数は等価な λ 項に変換でき、逆に λ 項で表された関数は対応するチューリング機械で実行できます。
チャーチ＝チューリングのテーゼは「直感的に計算できるすべての関数が帰納的関数（＝チューリング機械で計算可能な関数）と同一である」という主張で、形式化の問題から未証明です（ https://ja.wikipedia.org/wiki/チャーチ＝チューリングのテーゼ ）。
1. 計算可能性の定義
**計算可能関数（部分帰納的関数）**は、入力が与えられたとき、対応するチューリング機械が停止すれば必ず出力が得られ、停止しなければその入力に対する出力は未定義となります [3]。
※部分帰納的関数とは、計算が停止しない場合（無限ループ）も含む、すべての（部分的に定義された）関数を指します。
この定義は「すべての入力で必ず停止する」ことを要求せず、停止すれば必ず結果が得られることが重要です。
2. チューリング機械の基本構成
チューリング機械は次の要素で構成されます。
- 状態集合：有限個の内部状態（開始状態・受理状態・非受理状態を含む） [1]
- テープ：無限に伸びるセル列で、各セルには記号集合から 1 つの記号が書かれます [1]
- ヘッド：左または右に 1 セルずつ移動し、同時にセル上の記号を書き換えます [1]
- 遷移関数：現在の状態と読んでいる記号から、次の状態・書き換える記号・ヘッドの移動方向を決定します [1]
機械は遷移関数に従い状態を変化させます。
受理状態または非受理状態に遷移した場合は計算が停止し、テープ上の内容を出力として受理・拒否のいずれかとみなす。
停止しない（無限ループ）場合は、その入力に対する出力は未定義と扱う [1]。
任意のチューリング機械をエミュレートできる 万能チューリング機械 が存在し、これは停止性問題が決定不能であることを示す基本定理の一部でもあります（追加調査結果参照）。
本節の解説は、さらに詳細な説明が掲載されている https://www.geeksforgeeks.org/theory-of-computation/turing-machine-in-toc/ と https://www.cs.cornell.edu/courses/cs4820/2012sp/handouts/turingm.pdf も参照してください。
3. ラムダ計算の基本要素
ラムダ計算は変換規則に基づいて計算を進めます。
- α変換：変数名を自由に置き換えても同一の関数を表す（例：
λx.xとλy.yは α 等価） [2] - β簡約：関数適用
((λx.M) N)をM中のxをNに置き換える操作 [2] - η変換：
λx.(M x)がM（xが自由に現れない場合）と等価であることを示す [2]
計算はこれらの変換だけで進行します。λ 項が β 簡約によりこれ以上簡約できない正規形に到達したときが、ラムダ計算における「停止」 とみなせます。
計算可能関数すべてを表現するには、自然数や組などのデータを λ 項で符号化することが前提となります。たとえば チャーチ数 による自然数の表現は次のとおりです。
- 0 :
λf.λx.x - 1 :
λf.λx.f x - 2 :
λf.λx.f (f x)
このように符号化すれば、α・β・η の変換だけで任意の部分帰納的関数をシミュレートできます [2]。
4. 等価性が示す意義
4.1 相互変換可能性
任意のチューリング機械を手続き的に λ 項へ変換でき、同じ計算結果が得られる [1][2]。
任意の λ 項をシミュレートするチューリング機械を構成でき、計算可能関数を同等に実行できる [1][2]。
4.2 客観的な計算可能性
状態遷移モデル（チューリング機械）と関数変換モデル（ラムダ計算）が同一の部分帰納的関数集合を共有することで、計算できることは実装やプログラミング言語に依存しない数学的概念であることが裏付けられます [3]。
4.3 共通の限界（判定不可能性の代表例）
停止問題：あるチューリング機械が任意の入力で停止するかを判定する問題は計算不可能です（ https://ja.wikipedia.org/wiki/停止性問題 ）。
λ 項の等価性問題：α・β・η 変換をすべて考慮した λ 項が同一関数かどうかを判定する問題は計算不可能です [2]。
正規形判定問題：λ 項が正規形（計算が停止した形）を持つかどうか、すなわち計算が止まるかを判定する問題も計算不可能であることが知られています（コンビネータ論理における結果） [2]。
これらは別個の計算不可能問題であり、両モデルが同じ計算可能性の限界を共有していることを示す具体例です。
5. まとめ
計算できるとは、チューリング機械とラムダ計算が同一の部分帰納的関数集合を表現でき（相互シミュレーションが可能である）ことを意味します。
チューリング機械は有限状態と無限テープを持つ抽象計算装置で、受理状態または非受理状態に遷移したときに計算が停止し、テープ上の内容が結果として得られます。
ラムダ計算は関数抽象と適用だけで計算を表現し、α・β・η 変換により評価が進み、β 簡約が止まった正規形が「停止」を表します。データの符号化（例：チャーチ数）を前提とすれば、任意の計算可能関数を表現できます。
等価性により「計算可能」という概念は形式的に一貫した客観的基準となり、関数型言語（例：Lisp や Haskell）の理論的基盤にも直結しています。
参考URL
- [1] https://ja.wikipedia.org/wiki/チューリングマシン
- [2] https://ja.wikipedia.org/wiki/ラムダ計算
- [3] https://en.wikipedia.org/wiki/Computability
- [4] https://www.geeksforgeeks.org/theory-of-computation/turing-machine-in-toc/
- [5] https://www.cs.cornell.edu/courses/cs4820/2012sp/handouts/turingm.pdf
