## You are here

Homecomputable number

## Primary tabs

# 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

$\frac{m-1}{n}<r<\frac{m+1}{n}$ |

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, $\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).

## Mathematics Subject Classification

03D25*no label found*68Q05

*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections

## Comments

## Practitioners?

In the entry computable number, the following claim appears: "arguably this field contains all the numbers we ever need in practice." To which group of practitioners does the "we" refer?