Computable number

Computable number

In mathematics and theoretical computer science, a real number a is said to be a computable number if it can be approximated by some algorithm (or Turing machine), in the following sense: given any integer n≥1, the algorithm produces an integer k such that:

Or, equivalently, there exists an algorithm which, given any rational error bound ε, produces a rational number r such that:

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

Table of contents

1 Properties
2 Computing digit strings
3 References
4 See also

Properties

The computable complex numbers form an algebraically closed field, and arguably this field contains all the numbers we ever need in practice. It contains all algebraic numbers as well as many known transcendental mathematical constants. There are however many real numbers which are not computable: the set of all computable numbers is countable (because the set of algorithms is) while the set of real numbers is not (see Cantor's diagonal argument).

The arithmetical operations on computable numbers are themselves computable. Take addition as example: there exists an algorithm or Turing machine which on input (A,B,ε) produces output r, where A is the description of a Turing machine approximating a (in the sense of the above definition), B is the description of a Turing machine approximating b, and r is an ε approximation of a+b.

However, order relations on computable numbers are 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≤0. The reason: suppose the machine described by A keeps outputing 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.

While the set of computable numbers is countable, it cannot be enumerated by any algorithm, program or Turing machine. Formally: it is not possible to provide a complete list x₁, x₂, x₃, ... of all computable real numbers and a Turing machine which on input (m, ε) produces an ε-approximation of x_m. This is proved with a slight modification of Cantor's diagonal argument.

Every computable number is definable, but not vice versa. An example of a definable, non-computable real number is Chaitin's constant, &Omega.

Computing digit strings

Turing's original paper (and a previous version of this article) 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≥1 as input and produces the n-th digit of the real number's decimal expansion as output.

The problem with this definition is this: addition is not computable if we use descriptions of digit-enumerating Turing machines as input and require a digit enumeration as ouput. The reason is similar to the one described above, when talking about order relations: if the first machine keeps outputing the digit 9 and the second machine the digit 0, how long do you wait before deciding that no carry to the current digit position is needed?

Is Turing's definition equivalent to our definition above?

References

Alan Turing, On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230-265. online version. Computable numbers (and Turing machines) were introduced in this paper.