計算可能数のソースを表示

[[File:10,000 digits of pi - poster.svg|thumb|[[Pi|π]] は任意の精度で計算可能である。一方、 [[ほとんど全て]]の実数は計算可能でない。]][[数学]]において、'''計算可能数'''（けいさんかのうすう）は[[実数]]であって、有限かつ停止する[[アルゴリズム]]によって望んだいかなる精度でも計算可能なもののことである。'''再帰的な数'''、'''実効的な数'''{{sfnp|van der Hoeven|2006}}、'''計算可能実数'''、'''再帰的実数'''などとしても知られる。{{cn|reason=Give a source for each naming variant.|date=September 2019}}

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

==チューリングマシンを用いた非形式的定義の例==
[[マービン・ミンスキー]]は数の計算可能性を[[アラン・チューリング]]が1936年に行ったのと同様の方法で以下のように定義した{{sfnp|Turing|1936}}; すなわち、0から1の間にある "十進小数と見なせる数列"として:{{sfnp|Minsky|1967}}。
 
{{quote|text=計算可能数とは以下のようなチューリングマシンが存在する数である: ''n'' が初期状態のテープに与えられたら、その数の[エンコード結果]の''n''桁目を出力して停止する。}}
この定義における重要な点は (1) 最初にある ''n'' を決めておくこと、(2) いかなる ''n'' に対しても有限ステップ後、マシンが望まれた出力をして停止することである.

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

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

==形式的な定義==
[[実数]] ''a'' が ''計算可能である''' とは、それがある[[計算可能関数]]<math>f:\mathbb{N}\to\mathbb{Z}</math>によって以下のような意味で近似できることである：与えられた任意の正[[整数]] ''n'' に対して、その関数は整数 ''f''(''n'') を、
:<math>{f(n)-1\over n} \leq a \leq {f(n)+1\over n}.</math>

となるように与えること。
この定義には、これと同値な二つの別の定義も存在する。:
*与えられたいかなる有理[[誤差限界]] <math>\varepsilon</math> に対しても[[有理数]] ''r'' を <math>|r - a| \leq \varepsilon</math>であるように生成するような計算可能関数が存在すること。 
*有理数の計算可能列 <math>q_i</math> であって、<math>a</math> に収束してさらに各 ''i'' に対して<math>|q_i - q_{i+1}| < 2^{-i}\,</math>が成り立つものが存在すること。
計算可能な[[デデキント切断]]を通した同値な定義も存在する。 '''計算可能なデデキント切断''' とは、計算可能関数 <math>D\;</math> であって、有理数 <math>r</math> が入力として与えられると出力として <math>D(r)=\mathrm{true}\;</math> か <math>D(r)=\mathrm{false}\;</math> を返すものであって次の条件を満たすものである。:<math>\exists r D(r)=\mathrm{true}\;</math>
:<math>\exists r D(r)=\mathrm{false}\;</math>
:<math>(D(r)=\mathrm{true}) \wedge (D(s)=\mathrm{false}) \Rightarrow r<s\;</math>
:<math>D(r)=\mathrm{true} \Rightarrow \exist s>r, D(s)=\mathrm{true}.\;</math>
3 の [[立方根]]を定めるプログラムはその一例である。<math>q>0\;</math> として、次のように定義する。:
:<math>p^3<3 q^3 \Rightarrow D(p/q)=\mathrm{true}\;</math>
:<math>p^3>3 q^3 \Rightarrow D(p/q)=\mathrm{false}.\;</math>

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

==性質==

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

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

===整列の計算不可能性===
計算可能数上の順序関係は計算可能でない。''A'' を<math>a</math>を近似するチューリングマシンの記述とする。このとき、任意に ''A'' を与えられて<math>a > 0</math>なら "YES"、<math>a \le 0.</math>なら "NO" を返せるようなチューリングマシンは存在しない。なぜかというと、<math>\epsilon</math>近似として0を出力し続けるマシン ''A'' を考えてみると、''a'' が正であることを強制する近似を出力することはないと判断するまでの時間が不明なものになっている。それゆえ、このマシンは出力を得るためには最終的には ''a'' が 0 に等しいことを推測して出力しなければならないが、実際はそれを決めた後のタイミングで ''a'' が 0 でないことを強制する近似が判明してしまう可能性がある。このアイデアは全域関数を計算するいくつかの数列についてマシンが不正確であることを示すのに用いられる。似た問題が[[デデキント切断]]によって計算可能数を表現する際に発生する。等式関係は計算不可能である。
完全な順序関係は計算不可能である一方、異なる数のペアに限定すれば大小関係は計算可能である。すなわち、次のようなプログラムは存在する。チューリングマシン ''A'', ''B'' が実数 <math> a</math>, <math> b</math>ただし<math>a \ne b</math>であるものを計算するものとしてそれが入力として与えられる、これに対して出力は<math>a < b</math>か<math>a > b</math>を与えるものである。これには、<math> \epsilon < |b-a|/2</math>である<math>\epsilon</math>-近似を用いれば十分でこの<math>\epsilon</math>は0にいくらでも近づけられる。<math>a \ne b</math>である以上は、最終的に<math>a < b</math>か<math>a > b</math>は必ず判断できる。
===その他の性質===
計算可能実数の集まりは解析で使われる実数の性質を満たすとは限らない。例えば、計算可能実数からなる有界な増加列があってもその上限は計算可能実数であるとは限らない。{{sfnp|Bridges|Richman|1987|p=58}} この性質を満たす数列は[[Specker sequence]]として知られている。これは[[Ernst Specker]]によって1949年に構成された。{{sfnp|Specker|1949}} このような反例がある一方、実解析の一部は計算可能数の分野で発展し[[計算可能解析学]]の研究に繋がっている。

全ての計算可能数は[[定義可能実数#算術における定義可能性|算術的定義可能]]であるが逆は成り立たない。算術的定義可能であるが計算可能でない実数はたくさん存在する。例えば：
*any number that encodes the solution of the [[停止問題]] (や他の [[決定不能問題]]) の解を選ばれた符号化方式で符号化している数。
*[[チャイティンの定数]], <math>\Omega</math>, これは停止問題と[[チューリング次数|チューリング同値]]であるような実数の一種である。
これらの例は実際のところ、定義可能かつ計算不能な数の無限集合を定義し、各[[万能チューリングマシン]]ごとに一つずつ与える。
実数が計算可能であるとき、かつその時に限り、自然数の集合を特性関数として見なしたとき計算可能である。

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

==数字列とカントール空間やベール空間==
チューリングは原論文で次のように計算可能数を定義している：

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

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

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

==実数の代わりとして==

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

実数を、それ自身を近似計算するプログラムによって表現するコンピュータパッケージは "正確な算術" という名前で1985年に提唱されている<ref>{{cite journal |last1=Boehm |first1=Hans-J. |last2=Cartwright |first2=Robert |last3=Riggle |first3=Mark |last4=O'Donnell |first4=Michael J. |title=Exact real arithmetic: a case study in higher order programming |journal=Proceedings of the 1986 ACM conference on LISP and functional programming |date=8 August 1986 |pages=162–173 |doi=10.1145/319838.319860 |url=http://fricas-wiki.math.uni.wroc.pl/public/refs/exact-real-p162-boehm.pdf}}</ref>。 近年の例としては、 include the CoRN ライブラリ (Coq)<ref>{{cite journal |last1=O’Connor |first1=Russell |title=Certified Exact Transcendental Real Number Computation in Coq |journal=Theorem Proving in Higher Order Logics |date=2008 |pages=246–261 |doi=10.1007/978-3-540-71067-7_21 |url=https://arxiv.org/pdf/0805.2438.pdf}}</ref> や RealLib パッケージ (C++) などがある{{sfnp|Lambov|2015}}。 関連する話題としては iRRAM パッケージのように [[real RAM]] プログラムとそれを十分な精度の有理数や浮動小数点数で実行することも挙げられる<ref>{{cite journal |last1=Gowland |first1=Paul |last2=Lester |first2=David |title=A Survey of Exact Arithmetic Implementations |journal=Computability and Complexity in Analysis |date=2001 |pages=30–47 |doi=10.1007/3-540-45335-0_3 |url=https://link.springer.com/content/pdf/10.1007%2F3-540-45335-0_3.pdf |publisher=Springer |language=en}}</ref>。

==関連項目==
*[[作図可能数]]
*[[定義可能実数]]
*[[Semicomputable function]]
*[[Transcomputational problem]]

==脚注==
{{reflist|30em}}

==参考文献==
{{refbegin|30em}}
*{{cite book |first1=Douglas |last1=Bridges |first2=Fred |last2=Richman |title=Varieties of Constructive Mathematics |url=https://books.google.com/books?id=oN5nsPkXhhsC |date=1987 |publisher=Cambridge University Press |isbn=978-0-521-31802-0 }}
*{{cite journal |first=Jeffry L. |last=Hirst |title=Representations of reals in reverse mathematics |journal= Bulletin of the Polish Academy of Sciences, Mathematics|year=2007 |volume=55 |issue=4 |pages=303–316  |url=https://eudml.org/doc/281227 |doi=10.4064/ba55-4-2|doi-access=free }}
*{{Cite web |title=RealLib |last=Lambov |first=Branimir |publisher=GitHub |date=5 April 2015 |accessdate=2022-10-10|url= https://github.com/blambov/RealLib }}
*{{cite book |author-link=Marvin Minsky |first=Marvin |last=Minsky |chapter=9. The Computable Real Numbers |title=Computation: Finite and Infinite Machines |url=https://archive.org/details/computationfinit0000mins |url-access=registration |publisher=Prentice-Hall |year=1967 |isbn=0-13-165563-9  |oclc=0131655639}}
*{{cite journal |first=Henry Gordon |last=Rice |title=Recursive real numbers |journal=Proceedings of the American Mathematical Society |year=1954 |volume=5 |issue=5 |pages=784–791 |doi=10.1090/S0002-9939-1954-0063328-5 |jstor=2031867  |doi-access=free }}
*{{cite journal |first=E. |last=Specker |author-link = Ernst Specker|title=Nicht konstruktiv beweisbare Sätze der Analysis |journal=Journal of Symbolic Logic |year=1949 |volume=14 |issue=3 |pages=145–158  |doi=10.2307/2267043 |jstor=2267043|url=http://doc.rero.ch/record/304204/files/S0022481200105663.pdf }}
*{{cite journal | last= Turing | first= A. M. | publication-date = 1937 | year = 1936 | title = On Computable Numbers, with an Application to the Entscheidungsproblem | periodical = Proceedings of the London Mathematical Society | series = Series 2 | volume = 42 | issue= 1 | pages = 230–65 | doi= 10.1112/plms/s2-42.1.230 }}<br/>{{cite journal | last = Turing | first = A. M. | publication-date = 1937 | title = On Computable Numbers, with an Application to the Entscheidungsproblem: A correction | periodical = Proceedings of the London Mathematical Society | series = Series 2 | volume = 43 | issue = 6 | pages = 544–6 | url = http://www.abelard.org/turpap2/tp2-ie.asp | doi = 10.1112/plms/s2-43.6.544 | year = 1938 }} Computable numbers (and Turing's a-machines) were introduced in this paper; the definition of computable numbers uses infinite decimal sequences.
*{{cite journal |last1=van der Hoeven |first1=Joris |title=Computations with effective real numbers |journal=Theoretical Computer Science |date=2006 |volume=351 |issue=1 |pages=52–60 |doi=10.1016/j.tcs.2005.09.060|doi-access=free }}
{{refend}}

==読書案内==
{{refbegin|30em}}
*{{cite journal |first=Oliver |last=Aberth |title=Analysis in the Computable Number Field |journal=Journal of the Association for Computing Machinery |year=1968 |volume=15 |issue=2 |pages=276–299  |doi=10.1145/321450.321460 |s2cid=18135005 }} This paper describes the development of the calculus over the computable number field.
*{{cite book |first1=Errett |last1=Bishop |first2=Douglas |last2=Bridges |title=Constructive Analysis |publisher=Springer |year=1985 |isbn=0-387-15066-8 }}
*{{cite book |first1=V. |last1=Stoltenberg-Hansen |first2=J.V. |last2=Tucker |chapter=Computable Rings and Fields |editor-first=E.R. |editor-last=Griffor |title=Handbook of Computability Theory |chapter-url=https://books.google.com/books?id=KqeXZ4pPd5QC&pg=PA363 |date=1999 |publisher=Elsevier |isbn=978-0-08-053304-9 |pages=363–448}}
*{{cite book |first=Klaus |last=Weihrauch |title=Computable analysis |series=Texts in Theoretical Computer Science |publisher=Springer |year=2000 |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.
*{{cite book |first=Klaus |last=Weihrauch |url=http://eccc.uni-trier.de/static/books/A_Simple_Introduction_to_Computable_Analysis_Fragments_of_a_Book/  |title=A simple introduction to computable analysis |year=1995 |publisher=Fernuniv., Fachbereich Informatik}}
{{refend}}

{{Number systems}}

{{DEFAULTSORT:けいさんかのうすう}}
[[Category:計算可能性理論]]
[[Category:計算理論]]