computable number

A real number r is called computable if there exists some terminating algorithmMathworldPlanetmath (or Turing machineMathworldPlanetmath) that can approximate it to arbitrary precision. Specifically, the algorithm takes a natural numberMathworldPlanetmath 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 functionMathworldPlanetmath F such that the above inequality holds when m=F(n).

A complex numberMathworldPlanetmathPlanetmath is called computable if its real and imaginary partsMathworldPlanetmath 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 numbersMathworldPlanetmath as well as many known transcendental constants, such as π and e for example. There are however many real numbers which are not computable: the set of all computable numbers is countableMathworldPlanetmath (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, Ω.

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 equivalentMathworldPlanetmathPlanetmathPlanetmathPlanetmath 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