View source for Computable number

{{short description|Real number that can be computed within arbitrary precision}}
{{distinguish|constructible number}}
[[File:10,000 digits of pi - poster.svg|thumb|[[Pi|π]] can be computed to arbitrary precision, while [[almost every]] real number is not computable.]]
In [[mathematics]], '''computable numbers''' are the [[real number]]s that can be computed to within any desired precision by a finite, terminating [[algorithm]]. They are also known as the '''recursive numbers''',<ref>{{cite book
 | last = Mazur | first = Stanisław | author-link = Stanisław Mazur
 | editor1-last = Grzegorczyk | editor1-first = Andrzej | editor1-link = Andrzej Grzegorczyk
 | editor2-last = Rasiowa | editor2-first = Helena | editor2-link = Helena Rasiowa
 | page = 4
 | publisher = [[Institute of Mathematics of the Polish Academy of Sciences]]
 | series = Rozprawy Matematyczne
 | title = Computable analysis
 | url = https://eudml.org/doc/268535
 | volume = 33
 | year = 1963}}</ref> '''effective numbers''',{{sfnp|van der Hoeven|2006}} '''computable reals''',<ref>{{cite journal
 | last1 = Pour-El | first1 = Marian Boykan | author1-link = Marian Pour-El
 | last2 = Richards | first2 = Ian
 | doi = 10.1016/0001-8708(83)90004-X | doi-access=free
 | issue = 1
 | journal = [[Advances in Mathematics]]
 | mr = 697614
 | pages = 44–74
 | title = Noncomputability in analysis and physics: a complete determination of the class of noncomputable linear operators
 | volume = 48
 | year = 1983}}</ref> or '''recursive reals'''.<ref>{{cite journal
 | last = Rogers | first = Hartley, Jr.
 | journal = Journal of the Society for Industrial and Applied Mathematics
 | mr = 99923
 | pages = 114–130
 | title = The present theory of Turing machine computability
 | volume = 7
 | year = 1959| doi = 10.1137/0107009
 }}</ref> The concept of a computable real number was introduced by [[Émile Borel]] in 1912, using the intuitive notion of computability available at the time.<ref>P. Odifreddi, ''Classical Recursion Theory'' (1989), p.8. North-Holland, 0-444-87295-7</ref>

Equivalent definitions can be given using [[μ-recursive function]]s, [[Turing machine]]s, or [[λ-calculus]] as the formal representation of algorithms. The computable numbers form a [[real closed field]] and can be used in the place of real numbers for many, but not all, mathematical purposes.{{Citation needed|date=October 2024}}

==Informal definition==
In the following, [[Marvin Minsky]] defines the numbers to be computed in a manner similar to those defined by [[Alan Turing]] in 1936;{{sfnp|Turing|1936}} i.e., as "sequences of digits interpreted as decimal fractions" between 0 and 1:{{sfnp|Minsky|1967}}
 
{{Blockquote|text=A computable number [is] one for which there is a Turing machine which, given ''n'' on its initial tape, terminates with the ''n''th digit of that number [encoded on its tape].}}

The key notions in the definition are (1) that some ''n'' is specified at the start, (2) for any ''n'' the computation only takes a finite number of steps, after which the machine produces the desired output and terminates.

An alternate form of (2) – the machine successively prints all ''n'' of the digits on its tape, halting after printing the ''n''th – emphasizes Minsky's observation: (3) That by use of a Turing machine, a ''finite'' definition – in the form of the machine's state table – is being used to define what is a potentially ''infinite'' string of decimal digits.

This is however not the modern definition which only requires the result be accurate to within any given accuracy. The informal definition above is subject to a rounding problem called the [[table-maker's dilemma]] whereas the modern definition is not.

==Formal definition==
A [[real number]] ''a'' is '''computable''' if it can be approximated by some [[computable function]] <math>f:\mathbb{N}\to\mathbb{Z}</math> in the following manner: given any positive [[integer]] ''n'', the function produces an integer ''f''(''n'') such that:

:<math>{f(n)-1\over n} \leq a \leq {f(n)+1\over n}.</math>

A [[complex number]] is called computable if its real and imaginary parts are computable.

===Equivalent definitions===
There are two similar definitions that are equivalent:
*There exists a computable function which, given any positive rational [[error bound]] <math>\varepsilon</math>, produces a [[rational number]] ''r'' such that <math>|r - a| \leq \varepsilon.</math>
*There is a computable sequence of rational numbers <math>q_i</math> converging to <math>a</math> such that <math>|q_i - q_{i+1}| < 2^{-i}\,</math> for each ''i''.

There is another equivalent definition of computable numbers via computable [[Dedekind cut]]s. A '''computable Dedekind cut''' is a computable function <math>D\;</math> which when provided with a rational number <math>r</math> as input returns <math>D(r)=\mathrm{true}\;</math> or <math>D(r)=\mathrm{false}\;</math>, satisfying the following conditions:
:<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>
An example is given by a program ''D'' that defines the [[cube root]] of 3. Assuming <math>q>0\;</math> this is defined by:
:<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>

A real number is computable if and only if there is a computable Dedekind cut ''D'' corresponding to it. The function ''D'' is unique for each computable number (although of course two different programs may provide the same function).

==Properties==

===Not computably enumerable===
Assigning a [[Gödel number]] to each Turing machine definition produces a subset <math>S</math> of the [[natural number]]s corresponding to the computable numbers and identifies a [[surjection]] from <math>S</math> to the computable numbers. There are only countably many Turing machines, showing that the computable numbers are [[subcountable]]. The set <math>S</math> of these Gödel numbers, however, is not [[computably enumerable]] (and consequently, neither are subsets of <math>S</math> that are defined in terms of it). This is because there is no algorithm to determine which Gödel numbers correspond to Turing machines that produce computable reals. In order to produce a computable real, a Turing machine must compute a [[total function]], but the corresponding [[decision problem]] is in [[Turing degree]] '''0&prime;&prime;'''. Consequently, there is no surjective [[computable function]] from the natural numbers to the set <math>S</math> of machines representing computable reals, and [[Cantor's diagonal argument]] cannot be used [[Constructivism (mathematics)|constructively]] to demonstrate uncountably many of them.

While the set of real numbers is [[uncountable]], the set of computable numbers is classically [[countable]] and thus [[almost all]] real numbers are not computable. Here, for any given computable number <math>x,</math> the [[well ordering principle]] provides that there is a minimal element in <math>S</math> which corresponds to <math>x</math>, and therefore there exists a subset consisting of the minimal elements, on which the map is a [[bijection]]. The inverse of this bijection is an [[Injective function|injection]] into the natural numbers of the computable numbers, proving that they are countable. But, again, this subset is not computable, even though the computable reals are themselves ordered.

===Properties as a field===
The arithmetical operations on computable numbers are themselves computable in the sense that whenever real numbers ''a'' and ''b'' are computable then the following real numbers are also computable: ''a'' + ''b'', ''a'' - ''b'', ''ab'', and ''a''/''b'' if ''b'' is nonzero.
These operations are actually ''uniformly computable''; for example, there is a Turing machine which on input (''A'',''B'',<math>\epsilon</math>) produces output ''r'', where ''A'' is the description of a Turing machine approximating ''a'', ''B'' is the description of a Turing machine approximating ''b'', and ''r'' is an <math>\epsilon</math> approximation of ''a'' + ''b''.

The fact that computable real numbers form a [[field (mathematics)|field]] was first proved by [[Henry Gordon Rice]] in 1954.{{sfnp|Rice|1954}}

Computable reals however do not form a [[computable field]], because the definition of a computable field requires effective equality.

===Non-computability of the ordering===
The order relation on the computable numbers is not computable. Let ''A'' be the description of a Turing machine approximating the number <math>a</math>. Then there is no Turing machine which on input ''A'' outputs "YES" if <math>a > 0</math> and "NO" if <math>a \le 0.</math> To see why, suppose the machine described by ''A'' keeps outputting 0 as <math>\epsilon</math> approximations. It is not clear how long to wait before deciding that the machine will ''never'' output an approximation which forces ''a'' to be positive. Thus the machine will eventually have to guess that the number will equal 0, in order to produce an output; the sequence may later become different from 0. This idea can be used to show that the machine is incorrect on some sequences if it computes a total function. A similar problem occurs when the computable reals are represented as [[Dedekind cut]]s. The same holds for the equality relation: the equality test is not computable.

While the full order relation is not computable, the restriction of it to pairs of unequal numbers is computable. That is, there is a program that takes as input two Turing machines ''A'' and ''B'' approximating numbers <math> a</math> and <math> b</math>, where <math>a \ne b</math>, and outputs whether <math>a < b</math> or <math>a > b.</math> It is sufficient to use <math>\epsilon</math>-approximations where <math> \epsilon < |b-a|/2,</math> so by taking increasingly small <math>\epsilon</math> (approaching 0), one eventually can decide whether <math>a < b</math> or <math>a > b.</math>

===Other properties===
The computable real numbers do not share all the properties of the real numbers used in analysis. For example, the least upper bound of a bounded increasing computable sequence of computable real numbers need not be a computable real number.{{sfnp|Bridges|Richman|1987|p=58}} A sequence with this property is known as a [[Specker sequence]], as the first construction is due to [[Ernst Specker]] in 1949.{{sfnp|Specker|1949}} Despite the existence of counterexamples such as these, parts of calculus and real analysis can be developed in the field of computable numbers, leading to the study of [[computable analysis]].

Every computable number is [[arithmetically definable number|arithmetically definable]], but not vice versa. There are many arithmetically definable, noncomputable real numbers, including:
*any number that encodes the solution of the [[halting problem]] (or any other [[undecidable problem]]) according to a chosen encoding scheme.
*[[Chaitin's constant]], <math>\Omega</math>, which is a type of real number that is [[Turing degree|Turing equivalent]] to the halting problem.
Both of these examples in fact define an infinite set of definable, uncomputable numbers, one for each [[universal Turing machine]].
A real number is computable if and only if the set of natural numbers it represents (when written in binary and viewed as a characteristic function) is computable.

The set of computable real numbers (as well as every countable, [[densely ordered]] subset of computable reals without ends) is [[order-isomorphic]] to the set of rational numbers.

==Digit strings and the Cantor and Baire spaces==

Turing's original paper defined computable numbers as follows:

{{quote|text=A real number is computable if its digit sequence can be produced by some algorithm or Turing machine. The algorithm takes an integer <math>n \ge 1</math> as input and produces the <math>n</math>-th digit of the real number's decimal expansion as output.}}

(The decimal expansion of ''a'' only refers to the digits following the decimal point.)

Turing was aware that this definition is equivalent to the <math>\epsilon</math>-approximation definition given above. The argument proceeds as follows: if a number is computable in the Turing sense, then it is also computable in the <math>\epsilon</math> sense: if <math>n > \log_{10} (1/\epsilon)</math>, then the first ''n'' digits of the decimal expansion for ''a'' provide an <math>\epsilon</math> approximation of ''a''. For the converse, we pick an <math>\epsilon</math> computable real number ''a'' and generate increasingly precise approximations until the ''n''th digit after the decimal point is certain. This always generates a decimal expansion equal to ''a'' but it may improperly end in an infinite sequence of 9's in which case it must have a finite (and thus computable) proper decimal expansion.

Unless certain topological properties of the real numbers are relevant, it is often more convenient to deal with elements of <math>2^{\omega}</math> (total 0,1 valued functions) instead of reals numbers in <math>[0,1]</math>. The members of <math>2^{\omega}</math> can be identified with binary decimal expansions, but since the decimal expansions <math>.d_1d_2\ldots d_n0111\ldots</math> and <math>.d_1d_2\ldots d_n10</math> denote the same real number, the interval <math>[0,1]</math> can only be bijectively (and homeomorphically under the subset topology) identified with the subset of <math>2^{\omega}</math> not ending in all 1's.

Note that this property of decimal expansions means that it is impossible to effectively identify the computable real numbers defined in terms of a decimal expansion and those defined in the <math>\epsilon</math> approximation sense. Hirst has shown that there is no algorithm which takes as input the description of a Turing machine which produces <math>\epsilon</math> approximations for the computable number ''a'', and produces as output a Turing machine which enumerates the digits of ''a'' in the sense of Turing's definition.{{sfnp|Hirst|2007}} Similarly, it means that the arithmetic operations on the computable reals are not effective on their decimal representations as when adding decimal numbers. In order to produce one digit, it may be necessary to look arbitrarily far to the right to determine if there is a carry to the current location. This lack of uniformity is one reason why the contemporary definition of computable numbers uses <math>\epsilon</math> approximations rather than decimal expansions.

However, from a [[computability theory|computability theoretic]] or [[measure theory|measure theoretic]] perspective, the two structures <math>2^{\omega}</math> and <math>[0,1]</math> are essentially identical. Thus, computability theorists often refer to members of <math>2^{\omega}</math> as reals. While <math>2^{\omega}</math> is [[totally disconnected]], for questions about <math>\Pi^0_1</math> classes or randomness it is easier to work in <math>2^{\omega}</math>.

Elements of <math>\omega^{\omega}</math> are sometimes called reals as well and though containing a [[homeomorphic]] image of <math>\mathbb{R}</math>, <math>\omega^{\omega}</math> isn't even [[locally compact]] (in addition to being totally disconnected). This leads to genuine differences in the computational properties. For instance the <math>x \in \mathbb{R}</math> satisfying <math>\forall(n \in \omega)\phi(x,n)</math>, with <math>\phi(x,n)</math> quantifier free, must be computable while the unique <math>x \in \omega^{\omega}</math> satisfying a universal formula may have an arbitrarily high position in the [[hyperarithmetic hierarchy]].

==Use in place of the reals==

The computable numbers include the specific real numbers which appear in practice, including all real [[algebraic number]]s, as well as ''e'', ''π'', and many other [[transcendental number]]s. Though the computable reals exhaust those reals we can calculate or approximate, the assumption that all reals are computable leads to substantially different conclusions about the real numbers. The question naturally arises of whether it is possible to dispose of the full set of reals and use computable numbers for all of mathematics. This idea is appealing from a [[constructivism (mathematics)|constructivist]] point of view, and has been pursued by the Russian school of constructive mathematics.<ref>{{cite journal
 | last = Kushner | first = Boris A.
 | doi = 10.2307/27641983
 | issue = 6
 | journal = [[The American Mathematical Monthly]]
 | mr = 2231143
 | pages = 559–566
 | title = The constructive mathematics of A. A. Markov
 | volume = 113
 | year = 2006| jstor = 27641983
 }}</ref>

To actually develop analysis over computable numbers, some care must be taken. For example, if one uses the classical definition of a sequence, the set of computable numbers is not closed under the basic operation of taking the [[supremum]] of a [[bounded sequence]] (for example, consider a [[Specker sequence]], see the section above). This difficulty is addressed by considering only sequences which have a computable [[modulus of convergence]]. The resulting mathematical theory is called [[computable analysis]].

==Implementations of exact arithmetic==

Computer packages representing real numbers as programs computing approximations have been proposed as early as 1985, under the name "exact arithmetic".<ref>{{cite book |last1=Boehm |first1=Hans-J. |last2=Cartwright |first2=Robert |last3=Riggle |first3=Mark |last4=O'Donnell |first4=Michael J. |title=Proceedings of the 1986 ACM conference on LISP and functional programming - LFP '86 |chapter=Exact real arithmetic: A case study in higher order programming |date=8 August 1986 |pages=162–173 |doi=10.1145/319838.319860 |isbn=0897912004 |s2cid=12934546 |chapter-url=http://fricas-wiki.math.uni.wroc.pl/public/refs/exact-real-p162-boehm.pdf |archive-url=https://web.archive.org/web/20200924021221/http://fricas-wiki.math.uni.wroc.pl/public/refs/exact-real-p162-boehm.pdf |archive-date=2020-09-24 |url-status=live}}</ref> Modern examples include the CoRN library (Coq),<ref>{{cite book |last1=O’Connor |first1=Russell |title=Theorem Proving in Higher Order Logics |chapter=Certified Exact Transcendental Real Number Computation in Coq |series=Lecture Notes in Computer Science |date=2008 |volume=5170 |pages=246–261 |doi=10.1007/978-3-540-71067-7_21 |arxiv=0805.2438 |isbn=978-3-540-71065-3 |s2cid=17959745 }}</ref> and the RealLib package (C++).{{sfnp|Lambov|2015}} A related line of work is based on taking a [[real RAM]] program and running it with rational or floating-point numbers of sufficient precision, such as the {{proper name|iRRAM}} package.<ref>{{cite book |last1=Gowland |first1=Paul |last2=Lester |first2=David |title=Computability and Complexity in Analysis |chapter=A Survey of Exact Arithmetic Implementations |series=Lecture Notes in Computer Science |date=2001 |volume=2064 |pages=30–47 |doi=10.1007/3-540-45335-0_3 |chapter-url=https://link.springer.com/content/pdf/10.1007%2F3-540-45335-0_3.pdf |archive-url=https://web.archive.org/web/20220324193302/https://link.springer.com/content/pdf/10.1007%2F3-540-45335-0_3.pdf |archive-date=2022-03-24 |url-status=live |publisher=Springer |isbn=978-3-540-42197-9 |language=en}}</ref>

==See also==
*[[Constructible number]]
*[[Definable number]]
*[[Semicomputable function]]
*[[Transcomputational problem]]

==Notes==
{{reflist|30em}}

==References==
{{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 |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|s2cid=11382421 |url=http://doc.rero.ch/record/304204/files/S0022481200105663.pdf |archive-url=https://web.archive.org/web/20180721231142/http://doc.rero.ch/record/304204/files/S0022481200105663.pdf |archive-date=2018-07-21 |url-status=live }}
*{{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 | s2cid= 73712 }}<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}}

==Further reading==
{{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 |doi-access=free }} 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:Computable Number}}
[[Category:Computability theory]]
[[Category:Theory of computation]]