#### lpetrich

##### Contributor

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.