Computable number
Not computably enumerable

Assigning a Gödel number to each Turing machine definition produces a subset S {\displaystyle S} of the natural numbers corresponding to the computable numbers and identifies a surjection from S {\displaystyle S} to the computable numbers. There are only countably many Turing machines, showing that the computable numbers are subcountable. The set S {\displaystyle S} of these Gödel numbers, however, is not computably enumerable (and consequently, neither are subsets of S {\displaystyle S} that are defined in terms of it). 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 set S {\displaystyle S} of machines representing computable reals, and Cantor's diagonal argument cannot be used constructively to demonstrate uncountably many of them.

While the set of real numbers is uncountable, the set of computable numbers is classically countable and thus almost all real numbers are not computable. Here, for any given computable number x, {\displaystyle x,} the well ordering principle provides that there is a minimal element in S {\displaystyle S} which corresponds to x {\displaystyle x}, and therefore there exists a subset 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. But, again, this subset is not computable, even though the computable reals are themselves ordered.
change_case:english_lowercase