# Properties of computable numbers

If we enumerate* all the computable numbers, those for which there exist a turing machine that outputs its digits to arbitrary precision. What is known about the asymptotic density of rationals, irrationals, algebraic, normal and transcendental numbers in this set?

*Enumerate them by their Kolmogorov complexity, ie we enumerate all turing programs up to a total character length n, then take the limit as n approaches infinity, does any of the number types have a limiting density in this set?

• Please define relative density. – Rasmus Oct 27 '11 at 15:30
• Doesn't that depend drastically on the enumeration you choose? You can just play Hilbert's hotel and take another enumeration: first 10 irrationals, then 27 transcendentals, then 1 rational and repeat this pattern, so I'd be surprised if this question is well-posed. – t.b. Oct 27 '11 at 15:41
• Here's a somewhat related thread – t.b. Oct 27 '11 at 15:50
• @Raphael: No. For each positive integer $n$ the multiples of $n$ have density $1/n$ in the integers, but all of these sets are countable. – Brian M. Scott Oct 27 '11 at 20:25
• There is no effective enumeration of all computable numbers. However, there are effective enumerations of the Turing machines, but not all Turing machines compute real numbers. How should we think of those machines that don't compute real numbers? – François G. Dorais Oct 28 '11 at 11:30

Allow me to interpret your question as follows. For each Turing machine program $e$, we consider the set $W_e$ of natural numbers accepted by program $e$, and then interpret $W_e$ as the locations of digit $1$ in the binary expansion of a number in the unit interval. Thus, program $e$ is in effect giving us better and better lower bounds for the limit real, as the digits gradually appear. (Note that we cannot control the rate of convergence here, but some accounts of computable reals insist that one does control the rate of convergence.) There is a natural enumeration of the Turing machine programs, and so we thereby obtain a natural enumeration of the computable reals in the unit interval. This enumeration is uniformly semi-computable, in the sense that we may enumerate all the pairs $(e,k)$, such that the $k^{\rm th}$ digit of the $e^{\rm th}$ real is $1$. François pointed out in his comment that a simple diagonalization prevents us from improving semi-computable here to computable.
Conclusion. For this enumeration, almost every computable real has only finitely many $1$s, and therefore is a rational number, with asymptotic probability one.