Computable number

In the following, Marvin Minsky defines the numbers to be computed in a manner similar to those defined by Alan Turing in 1936;[3] i.e., as "sequences of digits interpreted as decimal fractions" between 0 and 1:[4]

A computable number [is] one for which there is a Turing machine which, given n on its initial tape, terminates with the nth 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 nth – 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.

A real number a is computable if it can be approximated by some computable function ${\displaystyle f:\mathbb {N} \to \mathbb {Z} }$ in the following manner: given any positive integer n, the function produces an integer f(n) such that:

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

There are two similar definitions that are equivalent:

• There exists a computable function which, given any positive rational error bound ${\displaystyle \varepsilon }$, produces a rational number r such that ${\displaystyle |r-a|\leq \varepsilon .}$
• There is a computable sequence of rational numbers ${\displaystyle q_{i}}$ converging to ${\displaystyle a}$ such that ${\displaystyle |q_{i}-q_{i+1}|<2^{-i}\,}$ for each i.

There is another equivalent definition of computable numbers via computable Dedekind cuts. A computable Dedekind cut is a computable function ${\displaystyle D\;}$ which when provided with a rational number ${\displaystyle r}$ as input returns ${\displaystyle D(r)=\mathrm {true} \;}$ or ${\displaystyle D(r)=\mathrm {false} \;}$, satisfying the following conditions:

${\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} .\;}$

An example is given by a program D that defines the cube root of 3. Assuming ${\displaystyle q>0\;}$ this is defined by:

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

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

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).

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

Turing's original paper defined computable numbers as follows:

A real number is computable if its digit sequence can be produced by some algorithm or Turing machine. The algorithm takes an integer ${\displaystyle n\geq 1}$ as input and produces the ${\displaystyle n}$-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 ${\displaystyle \epsilon }$-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 ${\displaystyle \epsilon }$ sense: if ${\displaystyle n>\log _{10}(1/\epsilon )}$, then the first n digits of the decimal expansion for a provide an ${\displaystyle \epsilon }$ approximation of a. For the converse, we pick an ${\displaystyle \epsilon }$ computable real number a and generate increasingly precise approximations until the nth 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 ${\displaystyle 2^{\omega }}$ (total 0,1 valued functions) instead of reals numbers in ${\displaystyle [0,1]}$. The members of ${\displaystyle 2^{\omega }}$ can be identified with binary decimal expansions, but since the decimal expansions ${\displaystyle .d_{1}d_{2}\ldots d_{n}0111\ldots }$ and ${\displaystyle .d_{1}d_{2}\ldots d_{n}10}$ denote the same real number, the interval ${\displaystyle [0,1]}$ can only be bijectively (and homeomorphically under the subset topology) identified with the subset of ${\displaystyle 2^{\omega }}$ 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 ${\displaystyle \epsilon }$ approximation sense. Hirst has shown that there is no algorithm which takes as input the description of a Turing machine which produces ${\displaystyle \epsilon }$ 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.[8] 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 ${\displaystyle \epsilon }$ approximations rather than decimal expansions.

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

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

The computable numbers include the specific real numbers which appear in practice, including all real algebraic numbers, as well as e, π, and many other transcendental numbers. 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 constructivist point of view, and has been pursued by what Errett Bishop and Fred Richman call the Russian school of constructive mathematics. [9]

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.

Computer packages representing real numbers as programs computing approximations have been proposed as early as 1985, under the name "exact arithmetic".[10] Modern examples include the CoRN library (Coq),[11] and the RealLib package (C++).[12] 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 iRRAM package.[13]

• Constructible number
• Definable number
• Semicomputable function
• Transcomputational problem