Computable Number

heavy stuff.

from Wikipedia

Computable Number

In mathematics, computable numbers are the real numbers that can be computed to within any desired precision by a finite, terminating algorithm. They are also known as the recursive numbers or the computable reals or recursive reals.

Equivalent definitions can be given using μ-recursive functions, Turing machines, or λ-calculus as the formal representation of algorithms. The computable numbers form a real closed field and can be used in the place of real numbers for many, but not all, mathematical purposes.

Countable but not computably enumerable

While the set of real numbers is uncountable, the set of computable numbers is only countable and thus almost all real numbers are not computable. That the computable numbers are at most countable intuitively comes from the fact that they are produced by Turing machines, of which there are only countably many. More precisely, assigning a Gödel number to each Turing machine definition produces a subset S {\displaystyle S} S of the natural numbers corresponding to the computable numbers and identifies a surjection from S {\displaystyle S} S to the computable numbers, which shows that the computable numbers are subcountable. Moreover, for any computable number x , {\displaystyle x,} x, the well ordering principle provides that there is a minimal element in S {\displaystyle S} S which corresponds to x {\displaystyle x} x, and therefore there exists a subset S 1 ⊂ S {\displaystyle S_{1}\subset S} {\displaystyle S_{1}\subset S} consisting of the minimal elements, on which the map is a bijection. The inverse of this bijection is an injection into the natural numbers of the computable numbers, proving that they are countable.

The set S {\displaystyle S} S of these Gödel numbers, however, is not computably enumerable (nor consequently is S 1 {\displaystyle S_{1}} S_{1}), even though the computable reals are themselves ordered. This is because there is no algorithm to determine which Gödel numbers correspond to Turing machines that produce computable reals. In order to produce a computable real, a Turing machine must compute a total function, but the corresponding decision problem is in Turing degree 0′′. Consequently, there is no surjective computable function from the natural numbers to the computable reals, and Cantor's diagonal argument cannot be used constructively to demonstrate uncountably many of them.