計算可能数
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2024/06/15 06:18 UTC 版)
数学において、計算可能数（けいさんかのうすう）は実数であって、有限かつ停止するアルゴリズムによって望んだいかなる精度でも計算可能なもののことである。再帰的な数、実効的な数[1]、計算可能実数、再帰的実数などとしても知られる。[要出典]
同値な定義はμ再帰関数、チューリングマシン、ラムダ計算などを用いたアルゴリズムの形式的表現によっても得られる。計算可能数は実閉体をなし、全てではないが多くの数学的な目的において実数の代わりに用いることができる。
チューリングマシンを用いた非形式的定義の例
マービン・ミンスキーは数の計算可能性をアラン・チューリングが1936年に行ったのと同様の方法で以下のように定義した[2]; すなわち、0から1の間にある "十進小数と見なせる数列"として:[3]。
計算可能数とは以下のようなチューリングマシンが存在する数である: n が初期状態のテープに与えられたら、その数の[エンコード結果]のn桁目を出力して停止する。
この定義における重要な点は (1) 最初にある n を決めておくこと、(2) いかなる n に対しても有限ステップ後、マシンが望まれた出力をして停止することである.
(2) の代わりに次のようなものがある – マシンが n 桁全てを連続でテープに出力した後、n桁目を出力した後停止する – これは次のミンスキーの観察を強調する: (3) チューリングマシンを用いることによって、状態遷移図の形をした "有限的" な定義が 無限 の長さになるかもしれない十進小数を定義するのに用いられる。
これはしかしながら、与えられた任意精度内に計算結果を収めることのみを要求する現代的な定義とは異なる。上で記した非形式的な定義はtable-maker's dilemmaと呼ばれる丸め誤差の問題の影響を受けるが、現代的な定義はそうではない。
形式的な定義
実数 a が 計算可能である' とは、それがある計算可能関数
一覧
カテゴリ:数
- 計算可能数のページへのリンク
