計算可能な数

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

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

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

計算可能な数とは、最初のテープにnが与えられ、その数（テープにエンコードされている）のn番目の桁で終了するチューリング マシンが存在する数です。

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

(2) の別の形式、つまりマシンがテープ上のn桁すべてを連続的に印刷し、n番目を印刷した後に停止するという形式は、ミンスキーの観察を強調しています。(3) チューリングマシンを使用することで、マシンの状態表の形での有限の定義が、潜在的に無限の 10 進桁の文字列を定義するために使用されています。

しかし、これは、結果が所定の精度の範囲内で正確であることのみを要求する現代の定義ではありません。上記の非公式の定義は、テーブル作成者のジレンマと呼ばれる丸めの問題の影響を受けますが、現代の定義はそうではありません。

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

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

複素数は、実数部と虚数部が計算可能な場合、計算可能と呼ばれます。

同等の類似した定義が 2 つあります。

• 任意の正の有理数誤差境界 が与えられたときに、有理数rを生成する計算可能な関数が存在し、${\displaystyle \epsilon }$ ${\displaystyle |ra|\leq \varepsilon .}$
• 各iに対してとなるような、に収束する計算可能な有理数列が存在する。${\displaystyle q_{i}}$${\displaystyle a}$${\displaystyle |q_{i}-q_{i+1}|<2^{-i}\,}$

計算可能デデキント切断による計算可能数の同等の定義がもう 1 つあります。計算可能デデキント切断とは、有理数を入力として与えられたときに、次の条件を満たす または を返す 計算可能関数です。${\displaystyle D\;}$${\displaystyle r}$${\displaystyle D(r)=\mathrm {true} \;}$${\displaystyle D(r)=\mathrm {false} \;}$

${\displaystyle \exists rD(r)=\mathrm {true} \;}$

${\displaystyle \exists rD(r)=\mathrm {false} \;}$

${\displaystyle (D(r)=\mathrm {true} )\wedge (D(s)=\mathrm {false} )\Rightarrow r<s\;}$

${\displaystyle D(r)=\mathrm {true} \Rightarrow \exists s>r,D(s)=\mathrm {true} .\;}$

3 の3 乗根を定義するプログラムDの例を示します。これは次のように定義されます。 ${\displaystyle q>0\;}$

${\displaystyle p^{3}\Rightarrow D(p/q)=\mathrm {true} \;}$

${\displaystyle p^{3}>3q^{3}\Rightarrow D(p/q)=\mathrm {false} .\;}$

実数は、それに対応する計算可能なデデキント切断Dが存在する場合にのみ計算可能です。関数Dは、計算可能な数ごとに一意です (もちろん、2 つの異なるプログラムが同じ関数を提供する場合もあります)。

各チューリングマシン定義にゲーデル数を割り当てると、計算可能数に対応する自然数のサブセットが生成され、から計算可能数への全射が識別されます。チューリングマシンは可算個しかないため、計算可能数は部分可算であることがわかります。ただし、これらのゲーデル数の集合は計算可能列挙可能ではありません(したがって、それに関して定義されている のサブセットも計算可能列挙可能ではありません)。これは、どのゲーデル数が計算可能実数を生成するチューリングマシンに対応するかを決定するアルゴリズムがないためです。計算可能実数を生成するために、チューリングマシンは全関数を計算する必要がありますが、対応する決定問題はチューリング次数0′′です。したがって、自然数から計算可能実数を表すマシンの集合への全射の計算可能関数は存在せず、カントールの対角論法を使用してそれらの数が非可算であることを示す ことはできません。${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$${\displaystyle S}$ ${\displaystyle S}$

実数の集合は非可算ですが、計算可能数の集合は古典的に可算であり、したがってほとんどすべての実数は計算可能ではありません。ここで、任意の計算可能数に対して、整列原理により、に対応する最小の元が存在するため、最小の元で構成されるサブセットが存在し、その上ではマップが全単射になります。この全単射の逆は、計算可能数の自然数への単射であり、それらが可算であることを証明します。しかし、この場合も、計算可能実数自体が順序付けられているにもかかわらず、このサブセットは計算可能ではありません。 ${\displaystyle x,}$${\displaystyle S}$${\displaystyle x}$

計算可能数に対する算術演算は、実数aとbが計算可能であるときはいつでも、次の実数も計算可能であるという意味で、それ自体が計算可能である: a + b、a - b、ab、およびbがゼロでない場合はa/b。これらの演算は、実際には一様に計算可能である。たとえば、入力 ( A、B、) に対して出力r を生成するチューリングマシンがあり、ここでAはa を近似するチューリングマシンの記述、Bはbを近似するチューリングマシンの記述、r はa + bの近似である。 ${\displaystyle \epsilon }$${\displaystyle \epsilon }$

計算可能な実数が体を形成するという事実は、1954年にヘンリー・ゴードン・ライスによって初めて証明されました。^[8]

ただし、計算可能実数は計算可能体を形成しません。計算可能体の定義には有効な等式が必要であるためです。

計算可能数に関する順序関係は計算可能ではありません。Aを数 を近似するチューリングマシンの記述とします。すると、入力Aに対して、 の場合に「YES」を出力し、 の場合に「NO」を出力するチューリングマシンは存在しません。理由を確認するために、 Aで記述されたマシンが近似値として 0 を出力し続けると仮定します。マシンがa を正にするような近似値を出力しないと判断するまでに、どれくらい待てばよいかは明らかではありません。したがって、マシンは最終的に、出力を生成するために、数が 0 に等しいと推測する必要があります。シーケンスは後で 0 と異なる可能性があります。この考え方は、マシンが全関数を計算する場合、一部のシーケンスで間違っていることを示すために使用できます。同様の問題は、計算可能実数がデデキント切断として表される場合に発生します。同じことが等式関係にも当てはまります。つまり、等式テストは計算可能ではありません。 ${\displaystyle a}$${\displaystyle a>0}$${\displaystyle a\leq 0.}$${\displaystyle \epsilon }$

完全な順序関係は計算不可能だが、不等数のペアへの制限は計算可能である。つまり、2つのチューリングマシンAとBを入力として受け取り、数とを近似するプログラムがあり、ここで、またはを出力する。近似値を使用するだけで十分であり、したがって、を徐々に小さく（0に近づく）とることで、最終的にまたはを決定できる。${\displaystyle a}$${\displaystyle b}$${\displaystyle a\neq b}$${\displaystyle a<b}$${\displaystyle a>b.}$${\displaystyle \epsilon }$${\displaystyle \epsilon <|ba|/2,}$${\displaystyle \epsilon }$${\displaystyle a<b}$${\displaystyle a>b.}$

計算可能実数は、解析で使用される実数のすべての特性を共有するわけではありません。たとえば、計算可能実数の有界増加する計算可能列の最小上限は、計算可能実数である必要はありません。^[9]この特性を持つ列は、 1949年にエルンスト・スペッカーによって最初に構築されたため、スペッカー列として知られています。 ^{[10]このような反例が存在するにもかかわらず、計算可能数の分野で微積分と実解析の一部を展開することができ、}計算可能解析の研究につながっています。

すべての計算可能な数は算術的に定義可能ですが、その逆は成り立ちません。算術的に定義可能で計算不可能な実数は多数あり、その一部を以下に示します。

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

これら 2 つの例は、実際には、定義可能で計算不可能な数の無限集合を、各汎用チューリング マシンごとに 1 つずつ定義しています。実数は、それが表す自然数の集合 (2 進数で記述され、特性関数として表示された場合) が計算可能である場合にのみ計算可能です。

計算可能な実数の集合（および計算可能な実数の無限に密に順序付けられたすべての可算な部分集合）は、有理数の集合と 順序同型です。

チューリングの元の論文では、計算可能な数は次のように定義されています。

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

( aの小数点展開は小数点以下の数字のみを参照します。)

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

実数の特定の位相的性質が関係しない限り、の実数ではなく、（合計 0,1 値関数）の元を扱う方が便利な場合がよくあります。 の要素は2 進小数展開と同一視できますが、 の 10 進展開と は同じ実数を表すため、区間は、すべて 1 で終わらない の部分集合とのみ全単射的に（および部分集合位相の下で同相的に）同一視できます。 ${\displaystyle 2^{\omega}}$${\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}}$

10進展開のこの特性は、10進展開で定義された計算可能な実数と近似の意味で定義された計算可能な実数を効果的に識別することが不可能であることを意味することに留意されたい。ハーストは、計算可能数aの近似値を生成するチューリングマシンの記述を入力として受け取り、チューリングの定義の意味でaの桁を列挙するチューリングマシンを出力するアルゴリズムは存在しないことを示した。 ^[11]同様に、これは、計算可能な実数に対する算術演算が、10進数を加算するときのように10進表現では有効ではないことを意味する。1桁を生成するために、現在の位置への繰り上がりがあるかどうかを判断するために、任意に右に遠くを見る必要があるかもしれない。この統一性の欠如は、計算可能数の現在の定義が10進展開ではなく近似値を使用する理由の1つである。 ${\displaystyle \epsilon }$${\displaystyle \epsilon }$${\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]

• 構築可能な数
• 定義可能な数
• 半計算可能関数
• トランスコンピュテーショナル問題