他の計算可能性モデルとの等価性
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/08 15:15 UTC 版)
「μ再帰関数」の記事における「他の計算可能性モデルとの等価性」の解説
クリーネは以下の最終定理で、「チューリングマシンによる計算可能関数」と「部分μ再帰関数」が等価であることを示した。 次のクラスの部分関数は同一の広がりを持つ。すなわち、同じメンバーを持つ。(a) 部分再帰関数 (b) 何らかの機械で計算可能な関数 (c) 1/1 関数（チューリングマシンを一方向のテープと1つのシンボルだけに制限したもの） さらに、これらは私が定義した関数 Ψ とも同一の広がりを持つ。（Kleene p. 376） クリーネはこれを証明するために、5つの原始再帰関数の作用素とμ作用素をチューリングマシンでエミュレートできることを示し、逆にチューリングマシンの動作を数値化することでその動作をμ再帰関数で表現できることを示した。
※この「他の計算可能性モデルとの等価性」の解説は、「μ再帰関数」の解説の一部です。
「他の計算可能性モデルとの等価性」を含む「μ再帰関数」の記事については、「μ再帰関数」の概要を参照ください。
ウィキペディア小見出し辞書の「他の計算可能性モデルとの等価性」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 他の計算可能性モデルとの等価性のページへのリンク
