lpetrich
Contributor
Alan Turing and the Countability of Computable Numbers – Feature Column and
Computable number
A computable real number is a real number that can be approximated arbitrary closely by running a Turing machine arbitrarily long. As with algebraic numbers, the output of each Turing machine can be tagged by Turing machine to resolve repetitions, so
{Nonnegative integers} < {computable numbers} < {Turing-machine results tagged by Turing machine}
As for algebraic numbers, can show that the number of Turing machines is countable, so we find
A0 <= |computable numbers| <= |Turing machines| = A0
and thus
|computable numbers| = A0
Computable numbers include not only algebraic numbers but also every transcendental number that one will ever use. Think of root-finding algorithms, infinite-series sums and products, and numerical integration.
There is an exception: Chaitin's constant, or more properly, family of constants. It's a number between 0 and 1 where each fractional digit has a Turing machine assigned to it, and is 1 if the Turing machine halts and 0 if it does not.
Alan Turing proved that one cannot construct a Turing machine that can return whether or not a Turing machine will halt, and that means that there is no Turing machine that can generate Chaitin's constant. Thus, Chaitin's constant is uncomputable.
![](/data/assets/editor_icons/wikipedia.png)
A computable real number is a real number that can be approximated arbitrary closely by running a Turing machine arbitrarily long. As with algebraic numbers, the output of each Turing machine can be tagged by Turing machine to resolve repetitions, so
{Nonnegative integers} < {computable numbers} < {Turing-machine results tagged by Turing machine}
As for algebraic numbers, can show that the number of Turing machines is countable, so we find
A0 <= |computable numbers| <= |Turing machines| = A0
and thus
|computable numbers| = A0
Computable numbers include not only algebraic numbers but also every transcendental number that one will ever use. Think of root-finding algorithms, infinite-series sums and products, and numerical integration.
There is an exception: Chaitin's constant, or more properly, family of constants. It's a number between 0 and 1 where each fractional digit has a Turing machine assigned to it, and is 1 if the Turing machine halts and 0 if it does not.
Alan Turing proved that one cannot construct a Turing machine that can return whether or not a Turing machine will halt, and that means that there is no Turing machine that can generate Chaitin's constant. Thus, Chaitin's constant is uncomputable.