computable number

A real number $r$ is called computable if there exists some terminating algorithm (or Turing machine) that can approximate it to arbitrary precision. Specifically, the algorithm takes a natural number $n$ as input and produces an integer $m$ as output such that

Alternatively, and equivalently, one may say that $r$ is computable if there exists a recursive function $F$ such that the above inequality holds when $m=F(n)$.

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

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 constants, such as $\pi$ and $e$ for example. 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 uncountable (as shown by Cantor’s diagonal argument).

Every computable number is definable, but not vice versa. An example of a definable, non-computable real is Chaitin’s constant, $\mathrm{\Omega }$.

Computable numbers were introduced by Alan Turing in 1936. Turing’s original definition differed from the one given above. Turing called a real number $r$ computable if there is a Turing machine which on input $n$ produces the $n$-th decimal digit of $r$. By distinguishing the cases of rational and irrational $r$, one can show that Turing’s definition is equivalent to the definition given above. However, there does not exist any general algorithm which transforms approximating Turing machines (in the sense of our definition) into digit-enumerating Turing machines (in the sense of Turing’s definition).

Title	computable number
Canonical name	ComputableNumber
Date of creation	2013-03-22 13:33:51
Last modified on	2013-03-22 13:33:51
Owner	AxelBoldt (56)
Last modified by	AxelBoldt (56)
Numerical id	15
Author	AxelBoldt (56)
Entry type	Topic
Classification	msc 03D25
Classification	msc 68Q05
Synonym	recursive number
Defines	computable
Defines	computable real number