計算可能な数

数学において、計算可能数とは、有限で終了するアルゴリズムによって任意の所望の精度で計算できる実数のことである。これらは、再帰数^{[ 1 ]} 、有効数^{[ 2 ]}、計算可能実数^{[ 3 ]}、または再帰実数^{[ 4 ]}とも呼ばれる。計算可能実数の概念は、1912年にエミール・ボレルによって、当時利用可能であった計算可能性の直感的な概念を用いて導入された^{[ 5 ] 。}

同等の定義は、μ再帰関数、チューリングマシン、またはλ計算をアルゴリズムの形式的表現として用いることによっても与えることができる。計算可能な数は実閉体を形成し、多くの数学的目的において実数の代わりに用いることができるが、すべての目的に用いることはできない。

以下では、マービン・ミンスキーは、 1936年にアラン・チューリングが定義したのと同様の方法で計算される数値を定義しています。 ^{[ 6 ]}つまり、0から1の間の「小数として解釈される数字の列」として定義されています。 ^{[ 7 ]}

計算可能な数とは、初期テープにnを与えられたときに、その数のn番目の桁をテープにエンコードして終了するチューリングマシンが存在する数のことである。

定義における重要な概念は、（1）開始時に何らかのnが指定されること、（2）任意のnに対して計算は有限のステップ数しか必要とせず、その後マシンは目的の出力を生成して終了することである。

（２）の別の形式、すなわち機械がテープにn桁の数字を順次印刷し、 n桁目を印刷した後に停止するという形式は、ミンスキーの観察（３）を強調している。チューリングマシンを使用することで、機械の状態表という形で有限の定義が、潜在的に無限の10進数の列を定義するために使用されている。

しかし、これは現代の定義とは異なり、数値が所定の精度内で達成されればよいというものではありません。上記の非公式な定義は、表作成者のジレンマと呼ばれる丸め誤差の問題を抱えていますが、現代の定義はそうではありません。

実数a は、何らかの計算可能な関数によって近似できる場合に計算可能であるという。${\displaystyle f:\mathbb {N} \to \mathbb {Z} }$次のようにして、任意の正の整数nが与えられたとき、関数は次の条件を満たす整数f ( n ) を生成します。

${\displaystyle {f(n)-1 \over n}\leq a\leq {f(n)+1 \over n}.}$

複素数は、その実部と虚部がともに計算可能な場合、計算可能であるという。

計算可能な数はすべて算術的に定義可能ですが、その逆は必ずしも成り立ちません。算術的に定義可能でありながら計算不可能な実数は数多く存在し、例えば以下のようなものがあります。

• 選択された符号化方式に従って停止問題（またはその他の決定不能問題）の解を符号化する任意の数値。
• チャイティンの定数、${\displaystyle \Omega }$これは、停止問題とチューリング等価な実数の一種です。

実際、これら二つの例はいずれも、定義可能ではあるものの計算不可能な数の無限集合を定義しており、それぞれの集合は普遍チューリングマシンごとに一つずつ存在します。実数が計算可能であるのは、それが表す自然数の集合（二進数で表され、特性関数として見なされた場合）が計算可能である場合に限ります。

チューリングの原著論文では、計算可能な数を次のように定義している。

実数は、その桁列が何らかのアルゴリズムまたはチューリングマシンによって生成できる場合に計算可能である。アルゴリズムは整数を入力として受け取る。${\displaystyle n\geq 1}$入力として、そして生成する${\displaystyle n}$実数の十進数展開の 番目の桁を出力します。

（ aの小数展開は、小数点以下の数字のみを指します。）

チューリングはこの定義が${\displaystyle \epsilon }$-上記の近似定義。議論は次のように進む：ある数がチューリングの意味で計算可能であれば、それはまた、${\displaystyle \epsilon }$意味: もし${\displaystyle n>\log _{10}(1/\epsilon )}$すると、 aの10進数展開の最初のn桁は、${\displaystyle \epsilon }$aの近似値。逆の場合、 を選択します。${\displaystyle \epsilon }$計算可能な実数aに対して、小数点以下n桁目が確定するまで、より精度の高い近似値を生成します。これにより、常にaに等しい小数展開が生成されますが、不適切に 9 が無限に続く場合があり、その場合は有限の (したがって計算可能な) 適切な小数展開を持つ必要があります。

実数の特定の位相的性質が関係しない限り、多くの場合、${\displaystyle 2^{\omega }}$（合計 0、1 値関数）実数の代わりに${\displaystyle [0,1]}$. メンバー${\displaystyle 2^{\omega }}$バイナリ十進展開で識別できますが、十進展開は${\displaystyle .d_{1}d_{2}\ldots d_{n}0111\ldots }$そして${\displaystyle .d_{1}d_{2}\ldots d_{n}10}$同じ実数を表す区間${\displaystyle [0,1]}$は、 の部分集合とのみ全単射的に（かつ部分集合トポロジの下で同相的に）同一視される。${\displaystyle 2^{\omega }}$末尾がすべて1ではない。

小数展開のこの性質は、小数展開で定義された計算可能な実数と、${\displaystyle \epsilon }$近似の意味。ハーストは、チューリングマシンの記述を入力として受け取り、それを生成するアルゴリズムは存在しないことを示した。${\displaystyle \epsilon }$計算可能数aの近似値を求め、チューリングの定義の意味でaの桁を列挙するチューリングマシンを出力します。 ^{[ 11 ]}同様に、これは、計算可能実数に対する算術演算が、10 進数の加算のように、その 10 進数表現に対して有効ではないことを意味します。 1 桁を生成するには、現在の位置に繰り上がりがあるかどうかを判断するために、任意の右端まで調べる必要がある場合があります。 この統一性の欠如は、現代の計算可能数の定義が を使用する理由の 1 つです。${\displaystyle \epsilon }$小数展開ではなく、近似値を用いる。

しかし、計算可能性理論または測度論の観点からは、2つの構造は${\displaystyle 2^{\omega }}$そして${\displaystyle [0,1]}$は本質的に同一である。したがって、計算可能性理論家はしばしばメンバーを${\displaystyle 2^{\omega }}$現実として。${\displaystyle 2^{\omega }}$完全に接続が切れています。質問については${\displaystyle \Pi _{1}^{0}}$クラスやランダム性の方が作業しやすい${\displaystyle 2^{\omega }}$。

要素${\displaystyle \omega ^{\omega }}$実数とも呼ばれ、同相像を含むが、${\displaystyle \mathbb {R} }$、${\displaystyle \omega ^{\omega }}$は局所的にコンパクトですらない（完全に不連結であることに加えて）。これは計算特性に真の差異をもたらします。例えば、${\displaystyle x\in \mathbb {R} }$満足${\displaystyle \forall (n\in \omega )\phi (x,n)}$、 と${\displaystyle \phi (x,n)}$量化子を含まず、計算可能でなければならないが、一意である${\displaystyle x\in \omega ^{\omega }}$普遍的な公式を満たすことは、超算術階層において任意に高い位置を占める可能性がある。

計算可能な数には、実際に現れる特定の実数、すなわちすべての実代数的数、 e、π 、およびその他多くの超越数が含まれます。計算可能な実数は、計算または近似できる実数を網羅していますが、すべての実数が計算可能であるという仮定は、実数について大きく異なる結論を導きます。実数の完全な集合を処分して、数学のすべてに計算可能な数を使用することが可能かどうかという疑問が自然に生じます。この考えは構成主義の観点から魅力的であり、ロシアの構成的数学学派によって追求されてきました。^{[ 12 ]}

計算可能な数に関する解析を実際に展開するには、いくつかの注意が必要です。例えば、数列の古典的な定義を用いる場合、計算可能な数の集合は、有界数列の上限を取るという基本的な操作に関して閉じていません（例えば、スペッカー数列を考えてみましょう。上記のセクションを参照してください）。この困難は、収束係数が計算可能な数列のみを考慮することによって解決されます。結果として得られる数学理論は、計算可能解析と呼ばれます。

実数を近似計算を行うプログラムとして表現するコンピュータパッケージは、1985年にはすでに「厳密な算術」という名称で提案されていました。^{[ 13 ]}現代の例としては、CoRNライブラリ（Coq）^{[ 14 ]}やRealLibパッケージ（C++）^{[ 15 ]}などがあります。関連する研究分野としては、実際のRAMプログラムを取り出し、 iRRAMパッケージのように十分な精度を持つ有理数または浮動小数点数で実行する方法があります。^{[ 16 ]}

• 構成可能な数
• 定義可能な数
• 半計算可能関数
• トランス計算問題