計算可能数

数学において、計算可能数（けいさんかのうすう）は実数であって、有限かつ停止するアルゴリズムによって望んだいかなる精度でも計算可能なもののことである。再帰的な数、実効的な数^[1]、計算可能実数、再帰的実数などとしても知られる。^[要出典]

同値な定義はμ再帰関数、チューリングマシン、ラムダ計算などを用いたアルゴリズムの形式的表現によっても得られる。計算可能数は実閉体をなし、全てではないが多くの数学的な目的において実数の代わりに用いることができる。

チューリングマシンを用いた非形式的定義の例

マービン・ミンスキーは数の計算可能性をアラン・チューリングが1936年に行ったのと同様の方法で以下のように定義した^[2]; すなわち、0から1の間にある "十進小数と見なせる数列"として:^[3]。

計算可能数とは以下のようなチューリングマシンが存在する数である: n が初期状態のテープに与えられたら、その数の[エンコード結果]のn桁目を出力して停止する。

この定義における重要な点は (1) 最初にある n を決めておくこと、(2) いかなる n に対しても有限ステップ後、マシンが望まれた出力をして停止することである.

(2) の代わりに次のようなものがある – マシンが n 桁全てを連続でテープに出力した後、n桁目を出力した後停止する – これは次のミンスキーの観察を強調する: (3) チューリングマシンを用いることによって、状態遷移図の形をした "有限的" な定義が無限の長さになるかもしれない十進小数を定義するのに用いられる。

これはしかしながら、与えられた任意精度内に計算結果を収めることのみを要求する現代的な定義とは異なる。上で記した非形式的な定義はtable-maker's dilemmaと呼ばれる丸め誤差の問題の影響を受けるが、現代的な定義はそうではない。

形式的な定義

実数 a が 計算可能である' とは、それがある計算可能関数 $f:\mathbb {N} \to \mathbb {Z}$ によって以下のような意味で近似できることである：与えられた任意の正整数 n に対して、その関数は整数 f(n) を、

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

となるように与えること。この定義には、これと同値な二つの別の定義も存在する。:

与えられたいかなる有理誤差限界 $\varepsilon$ に対しても有理数 r を $|r-a|\leq \varepsilon$ であるように生成するような計算可能関数が存在すること。
有理数の計算可能列 $q_{i}$ であって、 $a$ に収束してさらに各 i に対して $|q_{i}-q_{i+1}|<2^{-i}\,$ が成り立つものが存在すること。

計算可能なデデキント切断を通した同値な定義も存在する。 計算可能なデデキント切断 とは、計算可能関数 $D\;$ であって、有理数 $r$ が入力として与えられると出力として $D(r)=\mathrm {true} \;$ か $D(r)=\mathrm {false} \;$ を返すものであって次の条件を満たすものである。: $\exists rD(r)=\mathrm {true} \;$

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

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

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

3 の立方根を定めるプログラムはその一例である。 $q>0\;$ として、次のように定義する。:

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

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

実数が計算可能であるとは、その実数に対応する計算可能なデデキント切断 D が存在することである。そのような関数 D は各計算可能数に対して一意的である。(しかしながらもちろん、二つの異なるプログラムがあってそれが同じ関数を与えることもある。) 複素数が計算可能であるとは、実部と虚部が共に計算可能であることである。

性質

計算可枚挙でないこと

各チューリングマシンの定義にゲーデル数を割り当てることで計算可能数に対応する自然数部分集合 $S$ を生成し、 $S$ から計算可能数全体への全射を与える。チューリングマシンは可算個しかないので、計算可能数全体はsubcountableである。しかしながら，ゲーデル数の集合 $S$ それ自身は、計算可枚挙ではない (それゆえ、 $S$ の部分集合でSを基に定義されるものも計算可枚挙ではない)。これは計算可能実数を生成するチューリングマシンに対応するゲーデル数を決定するアルゴリズムは存在しないためである。計算可能実数を生成するためには、チューリングマシンは全域関数を計算しなければならない、しかし、対応する決定問題はチューリング次数が 0′′ である。結論として、自然数の集合から計算可能実数の集合への全射計算可能関数は存在しない。実数全体の集合は不可算であって、計算可能数の集合は可算であり、ほとんど全ての実数は計算可能ではない。ここで、任意の与えられた計算可能数 $x$ について、整列原理によって $S$ の極小要素で $x$ に対応するものが存在する。そして、それゆえそのような極小なゲーデル数からなる部分集合から計算可能数全体への全単射が存在する. この全単射の逆写像は計算可能数に対応する自然数の集合への単射である。しかし、前述の通りこの部分集合は計算可能実数が整列されていても計算可能ではない。

体としての性質

計算可能数上の算術的操作はそれら自身計算可能である。すなわち、計算可能実数 a と b が存在するとき、次の数は全て計算可能である: a + b, a - b, ab, そして b が 0 でない場合の a/b。これらの操作は実際のところ 一様計算可能 である；例えば、チューリングマシンで入力が (A,B, $\epsilon$ ) で出力が r であるものがある。ここで A は a を、B は b を近似するチューリングマシンの記述で、r は a+b の $\epsilon$ 近似である。この計算可能実数が体をなすということはHenry Gordon Riceによって1954年に初めて証明された^[4]。計算可能実数全体は計算可能体はなしていない。計算可能体の定義には実効的な等価性が必要である。

整列の計算不可能性

計算可能数上の順序関係は計算可能でない。A を $a$ を近似するチューリングマシンの記述とする。このとき、任意に A を与えられて $a>0$ なら "YES"、 $a\leq 0.$ なら "NO" を返せるようなチューリングマシンは存在しない。なぜかというと、 $\epsilon$ 近似として0を出力し続けるマシン A を考えてみると、a が正であることを強制する近似を出力することはないと判断するまでの時間が不明なものになっている。それゆえ、このマシンは出力を得るためには最終的には a が 0 に等しいことを推測して出力しなければならないが、実際はそれを決めた後のタイミングで a が 0 でないことを強制する近似が判明してしまう可能性がある。このアイデアは全域関数を計算するいくつかの数列についてマシンが不正確であることを示すのに用いられる。似た問題がデデキント切断によって計算可能数を表現する際に発生する。等式関係は計算不可能である。完全な順序関係は計算不可能である一方、異なる数のペアに限定すれば大小関係は計算可能である。すなわち、次のようなプログラムは存在する。チューリングマシン A, B が実数 $a$ , $b$ ただし $a\neq b$ であるものを計算するものとしてそれが入力として与えられる、これに対して出力は $a<b$ か $a>b$ を与えるものである。これには、 $\epsilon <|b-a|/2$ である $\epsilon$ -近似を用いれば十分でこの $\epsilon$ は0にいくらでも近づけられる。 $a\neq b$ である以上は、最終的に $a<b$ か $a>b$ は必ず判断できる。

その他の性質

計算可能実数の集まりは解析で使われる実数の性質を満たすとは限らない。例えば、計算可能実数からなる有界な増加列があってもその上限は計算可能実数であるとは限らない。^[5] この性質を満たす数列はSpecker sequenceとして知られている。これはErnst Speckerによって1949年に構成された。^[6] このような反例がある一方、実解析の一部は計算可能数の分野で発展し計算可能解析学の研究に繋がっている。

全ての計算可能数は算術的定義可能であるが逆は成り立たない。算術的定義可能であるが計算可能でない実数はたくさん存在する。例えば：

any number that encodes the solution of the 停止問題 (や他の決定不能問題) の解を選ばれた符号化方式で符号化している数。
チャイティンの定数, $\Omega$ , これは停止問題とチューリング同値であるような実数の一種である。

これらの例は実際のところ、定義可能かつ計算不能な数の無限集合を定義し、各万能チューリングマシンごとに一つずつ与える。実数が計算可能であるとき、かつその時に限り、自然数の集合を特性関数として見なしたとき計算可能である。

計算可能実数全体は (およびそのうち可算な稠密順序で端点の無い部分集合は) 有理数全体と順序同型である。

数字列とカントール空間やベール空間

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

実数が計算可能であるとはその桁の並びがなんらかのアルゴリズムやチューリングマシンで生成できることをいう。そのアルゴリズムは整数 $n\geq 1$ を入力として受け取り、その実数の十進表現の $n$ 桁目を出力とするものである。

(ここで a の十進展開と言ったとき、それは小数点以下の部分のみを指している。)

チューリングはこの定義が上でこれまで定義してきた $\epsilon$ -近似と同値であることに気づいていた。その議論は次のように進められる：ある数がチューリングの意味で計算可能であるときにはそれは、 $\epsilon$ 近似の意味でも計算可能である： $n>\log _{10}(1/\epsilon )$ であるとき、a の最初の n 桁は a の $\epsilon$ 近似を与えている。逆を示すには、 $\epsilon$ 近似可能な a に対しては小数点以下 n 桁目が確定するまで近似精度を上げていけばよい。これは常に a の十進展開に等しい列を生成するが、この考え方だと不適切に9の無限列で終わる可能性がある。しかしその場合は有限の (したがって計算可能な) 適切な十進展開を持つことになるのでいずれにしても計算可能性が導かれる。実数の位相的性質が関係しない限り、区間 $[0,1]$ の実数の代わりに $2^{\omega }$ の元 (0,1 の値を取る全域関数) を扱う方が便利なことがしばしばある。 $2^{\omega }$ の元は実数の二進展開と同一視することができる。ただし、 $.d_{1}d_{2}\ldots d_{n}0111\ldots$ と $.d_{1}d_{2}\ldots d_{n}10$ は同じ実数を表しており、区間 $[0,1]$ は $2^{\omega }$ の元のうち1の列で終わらないもの全体と全単射で対応する(相対位相を考えれば同相にもなる)。この小数展開の性質は計算可能な実数が十進展開で定義されたものであるか $\epsilon$ 近似で定義されたものであるかを実効的に区別することは不可能であることを意味している。ハーストは計算可能数 aの $\epsilon$ 近似を生成するチューリングマシンの記述を入力として受け取り、そしてチューリングの意味における a の桁の並びを列挙するようなチューリングマシンを出力として生成するアルゴリズムは存在しないことを示した。^[7] 同様に、計算可能実数上の算術操作は、十進数の足し算をするときのように、実効的ではないことを意味している。ある一桁を確定するために、繰上りが無いかどうかを予め分からない桁数分の右側を確認しに行かねばならない場合がある。この一様性の無さが現代的な計算可能数の定義で十進展開よりも $\epsilon$ 近似を用いる理由の一つである。しかしながら、計算可能性理論や測度論的観点から $2^{\omega }$ と $[0,1]$ という二つの構造は本質的に同一のものであり、計算可能性理論の分野ではしばしば $2^{\omega }$ の元を実数と呼んでいる。また $2^{\omega }$ は完全不連結であって、 $\Pi _{1}^{0}$ のクラスやランダムネスの問題に関しては $2^{\omega }$ で考える方が考えやすい。 $\mathbb {R}$ と同相な像を含む $\omega ^{\omega }$ の元も実数と呼ばれることがある。 $\omega ^{\omega }$ は完全不連結であることに加えて局所コンパクトですらない。このため、計算的性質に関する明確な違いが発生してくる。例えば、 $x\in \mathbb {R}$ を $\forall (n\in \omega )\phi (x,n)$ を満たすものとしよう。ここで $\phi (x,n)$ は量化子の無いものとする。このとき、これは計算可能でなければならないが、一方、universal formula を満たす一意的な $x\in \omega ^{\omega }$ はhyperarithmetic hierarchyにおける任意の高さに位置することができる。

実数の代わりとして

計算可能数の範囲には全ての代数的数、e、π などの具体的な超越数など実用的な具体的実数が全て含まれている。計算可能実数というのは、計算したり近似したりできる実数全てを網羅したものであるが、考慮すべき実数が全て計算可能であると仮定すると実数に関する結論は大きく異なってくる。全ての数学に、実数全体でなく計算可能数のみを用いることができるのかという問いが自然に出てくる。この考えは構成主義の観点からも魅力的でエレット・ビショップやフレッド・リッチマンが構成的数学の ロシア学派 と呼んで追究してきたものである。^[要出典] 計算可能数上の解析学を実際に展開するためには、いくつかの注意が必要である。例えば、列の古典的な定義を用いる際、計算可能数の集合は有界列の上限を取るという基本的な操作について閉じていない (例えば、前述のSpecker sequenceなど)。この困難さについては計算可能な収束係数を持つ列のみを考慮することによって対処することができ。このようにして得られた理論は計算可能解析学と呼ばれている。

正確な算術の実装

実数を、それ自身を近似計算するプログラムによって表現するコンピュータパッケージは "正確な算術" という名前で1985年に提唱されている^[8]。近年の例としては、 include the CoRN ライブラリ (Coq)^[9] や RealLib パッケージ (C++) などがある^[10]。関連する話題としては iRRAM パッケージのように real RAM プログラムとそれを十分な精度の有理数や浮動小数点数で実行することも挙げられる^[11]。

脚注

^ van der Hoeven (2006).
^ Turing (1936).
^ Minsky (1967).
^ Rice (1954).
^ Bridges & Richman (1987), p. 58.
^ Specker (1949).
^ Hirst (2007).
^ Boehm, Hans-J.; Cartwright, Robert; Riggle, Mark; O'Donnell, Michael J. (8 August 1986). “Exact real arithmetic: a case study in higher order programming”. Proceedings of the 1986 ACM conference on LISP and functional programming: 162–173. doi:10.1145/319838.319860.
^ O’Connor, Russell (2008). “Certified Exact Transcendental Real Number Computation in Coq”. Theorem Proving in Higher Order Logics: 246–261. doi:10.1007/978-3-540-71067-7_21. https://arxiv.org/pdf/0805.2438.pdf.
^ Lambov (2015).
^ Gowland, Paul; Lester, David (2001). “A Survey of Exact Arithmetic Implementations” (英語). Computability and Complexity in Analysis (Springer): 30–47. doi:10.1007/3-540-45335-0_3.

参考文献

Bridges, Douglas; Richman, Fred (1987). Varieties of Constructive Mathematics. Cambridge University Press. ISBN 978-0-521-31802-0
Hirst, Jeffry L. (2007). “Representations of reals in reverse mathematics”. Bulletin of the Polish Academy of Sciences, Mathematics 55 (4): 303–316 . doi:10.4064/ba55-4-2. https://eudml.org/doc/281227.
Lambov, Branimir (5 April 2015). “RealLib”. GitHub. 2022年10月10日閲覧。
Minsky, Marvin (1967). “9. The Computable Real Numbers”. Computation: Finite and Infinite Machines. Prentice-Hall. ISBN 0-13-165563-9. OCLC 0131655639
Rice, Henry Gordon (1954). “Recursive real numbers”. Proceedings of the American Mathematical Society 5 (5): 784–791. doi:10.1090/S0002-9939-1954-0063328-5. JSTOR 2031867 .
Specker, E. (1949). “Nicht konstruktiv beweisbare Sätze der Analysis”. Journal of Symbolic Logic 14 (3): 145–158 . doi:10.2307/2267043. JSTOR 2267043.
Turing, A. M. (1936). “On Computable Numbers, with an Application to the Entscheidungsproblem”. Proceedings of the London Mathematical Society. Series 2 42 (1): 230–65. 1937. doi:10.1112/plms/s2-42.1.230.
Turing, A. M. (1938). “On Computable Numbers, with an Application to the Entscheidungsproblem: A correction”. Proceedings of the London Mathematical Society. Series 2 43 (6): 544–6. 1937. doi:10.1112/plms/s2-43.6.544. Computable numbers (and Turing's a-machines) were introduced in this paper; the definition of computable numbers uses infinite decimal sequences.
van der Hoeven, Joris (2006). “Computations with effective real numbers”. Theoretical Computer Science 351 (1): 52–60. doi:10.1016/j.tcs.2005.09.060.

読書案内

Aberth, Oliver (1968). “Analysis in the Computable Number Field”. Journal of the Association for Computing Machinery 15 (2): 276–299 . doi:10.1145/321450.321460. This paper describes the development of the calculus over the computable number field.
Bishop, Errett; Bridges, Douglas (1985). Constructive Analysis. Springer. ISBN 0-387-15066-8
Stoltenberg-Hansen, V.; Tucker, J.V. (1999). “Computable Rings and Fields”. In Griffor, E.R.. Handbook of Computability Theory. Elsevier. pp. 363–448. ISBN 978-0-08-053304-9
Weihrauch, Klaus (2000). Computable analysis. Texts in Theoretical Computer Science. Springer. ISBN 3-540-66817-9 §1.3.2 introduces the definition by nested sequences of intervals converging to the singleton real. Other representations are discussed in §4.1.
Weihrauch, Klaus (1995). A simple introduction to computable analysis. Fernuniv., Fachbereich Informatik

[FOOTNOTEvan_der_Hoeven2006-1] van der Hoeven (2006).

[FOOTNOTETuring1936-2] Turing (1936).

[FOOTNOTEMinsky1967-3] Minsky (1967).

[FOOTNOTERice1954-4] Rice (1954).

[FOOTNOTEBridgesRichman198758-5] Bridges & Richman (1987), p. 58.

[FOOTNOTESpecker1949-6] Specker (1949).

[FOOTNOTEHirst2007-7] Hirst (2007).

[8] Boehm, Hans-J.; Cartwright, Robert; Riggle, Mark; O'Donnell, Michael J. (8 August 1986). “Exact real arithmetic: a case study in higher order programming”. Proceedings of the 1986 ACM conference on LISP and functional programming: 162–173. doi:10.1145/319838.319860.

[9] O’Connor, Russell (2008). “Certified Exact Transcendental Real Number Computation in Coq”. Theorem Proving in Higher Order Logics: 246–261. doi:10.1007/978-3-540-71067-7_21. https://arxiv.org/pdf/0805.2438.pdf.

[FOOTNOTELambov2015-10] Lambov (2015).

[11] Gowland, Paul; Lester, David (2001). “A Survey of Exact Arithmetic Implementations” (英語). Computability and Complexity in Analysis (Springer): 30–47. doi:10.1007/3-540-45335-0_3.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]