Computable number

From Wikipedia, the free encyclopedia

In mathematics, theoretical computer science and mathematical logic, the computable numbers, also known as the recursive numbers or the computable reals, are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. Equivalent definitions can be given using μ-recursive functions, Turing machines 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.

1 Informal definition using a Turing machine as example
2 Formal definition
3 Properties
4 Computing digit strings
5 Can computable numbers be used instead of the reals?
6 Implementation
7 References
8 See also
9 External links

[edit] Informal definition using a Turing machine as example

In the following, Minsky defines the numbers to be computed in a manner similar to those defined by Turing 1936-7, i.e. as "sequences of digits interpreted as decimal fractions" between 0 and 1:

"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]." (Minsky 1967:159)

The key notions in the definition are (1) that some n is specified at the start, (2) when the machine's internal counter reaches this n the computation terminates after printing the n^th decimal digit on its tape -- otherwise it would continue computing forever.

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 TABLE -- is being used to define what is a potentially-infinite string of decimal digits.

[edit] Formal definition

A real number a is said to be computable if it can be approximated by some computable function in the following manner: given any integer $n \ge 1$ , the function produces an integer k such that:

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

There are two similar definitions that are equivalent:

There exists a computable function which, given any positive rational error bound $ε$ , produces a rational number r such that $|r - a| \leq \epsilon.$
There is a computable sequence of rational numbers $q i$ converging to $r$ such that $|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 $D\;$ which when provided with a rational number $r$ as input returns $D(r)=true\;$ or $D(r)=false\;$ , satisfying the following conditions:

$\exists r D(r)=\mathit{true}\;$

$\exists r D(r)=\mathit{false}\;$

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

$D(r)=\mathit{true} \Rightarrow \exist s>r, D(s)=\mathit{true}\;$

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

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

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

A real number is computable if and only if there is a computable Dedekind cut D converging to it. The function D is unique for each irrational 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.

[edit] Properties

Although the set of real numbers is uncountable, the set of computable numbers is countable and thus most real numbers are not computable. The computable numbers can be counted by assigning a Gödel number to each Turing machine definition. This gives a function from the naturals to the computable reals. Although the computable numbers are an ordered field, the set of Gödel numbers corresponding to computable numbers is not itself computably enumerable, because it is not possible to effectively 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′′. Thus Cantor's diagonal argument cannot be used to produce uncountably many computable reals; at best, the reals formed from this method will be uncomputable.

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, $ε$ ) 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 $ε$ approximation of a+b.

It is known that the least upper bound of a bounded increasing computable sequence of computable real numbers need not be a computable real number; nevertheless, the calculus can be developed in the field of computable numbers, although an altered definition of the derivative is needed to avoid certain difficulties that can occur when considering functions with removable singularities.

The order relation on the computable numbers is not computable. There is no Turing machine which on input A (the description of a Turing machine approximating the number $a$ ) outputs "YES" if $a > 0$ and "NO" if $a \le 0$ . The reason: suppose the machine described by A keeps outputting 0 as $ε$ 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 cuts. 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 an input two turing machines A and B approximating numbers a and b, where a≠b, and outputs whether a<b or a>b. It is sufficient to use ε-approximations where ε<|b-a|/2; so by taking increasingly small ε (with a limit to 0), one eventually can decide whether a<b or a>b.

Every computable number is definable, but not vice versa. There are many definable, noncomputable real numbers, including:

The binary representation of the Halting problem (or any other uncomputable set of natural numbers).
Chaitin's constant, $Ω$ , which is a type of real number that is Turing equivalent to the Halting problem.

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.

[edit] Computing digit strings

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 $n \ge 1$ as input and produces the

n

-th digit of the real number's decimal expansion as output.

Turing was aware that this definition is equivalent to the $ε$ -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 $ε$ sense: if $n > l o g 10 (1 / ε)$ , then the first n digits of a provide an $ε$ approximation of a. For the converse, we pick an $ε$ computable real number a and distinguish two cases. If a is rational, then a is also Turing computable, since the digit expansions of rational numbers are eventually periodic and can therefore be produced by simple algorithms. If a is not rational, then it is possible to compute ever more precise $ε$ -approximations until the nth digit is certain. This will eventually happen because a is not rational and thus the decimal expansion cannot be eventually constant.

There is no algorithm which takes as input the description of a Turing machine which produces $ε$ 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^{[citation needed]}. So while the two definitions are equivalent, they are not "computably equivalent".

An important property of Turing's definition is that the arithmetic operations are not uniformly computable in this representation. This can be seen most easily with addition: 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. It is true, however, that if two real numbers have representations according to Turing's definitions then so will their sum, product, difference, and quotient. This lack of uniformity is one reason that the contemporary definition of computable numbers uses $ε$ approximations rather than decimal expansions.

[edit] Can computable numbers be used instead of the reals?

The computable numbers include many of the specific real numbers which appear in practice, including all algebraic numbers, as well as e, $π$ , and many other transcendental 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 Bishop and Richman call the Russian school of constructive mathematics. Even though the calculus can be developed over the computable numbers, the set of computable numbers is not closed under basic operations such as taking the supremum of a bounded sequence, so this set cannot be used as a replacement for the full set of real numbers in classical mathematics.

[edit] Implementation

There are some computer packages that work with computable real numbers, representing the real numbers as programs computing approximations. One example is the RealLib package (reallib home page).

[edit] References

Douglas Bridges and Fred Richman. Varieties of Constructive Mathematics, Oxford, 1987.

Marvin Minsky 1967, Computation: Finite and Infinite Machines, Prentice-Hall, Inc. Englewood Cliffs, NJ. No ISBN. Library of Congress Card Catalog No. 67-12342. His chapter §9 "The Computable Real Numbers" expands on the topics of this article.

Alan Turing 1936-7, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1937), pp 230-265. (online version). Computable numbers (and Turing's a-machines) were introduced in this paper; the definition of computable numbers uses infinite decimal sequences.

Oliver Aberth 1968, Analysis in the Computable Number Field, Journal of the Association for Computing Machinery (JACM), vol 15, iss 2, pp 276-299. This paper describes the development of the calculus over the computable number field.

Klaus Weihrauch 2000, Computable analysis, Texts in theoretical computer science, Springer, ISBN 3540668179. (online version) §1.3.2 introduces the definition by nested sequences of intervals converging to the singleton real. Other representations are discussed in §4.1.

Computable numbers were defined independently by Turing, Post and Church. See The Undecidable, ed. Martin Davis, for further original papers.