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?

  • $\begingroup$ Please define relative density. $\endgroup$ – Rasmus Oct 27 '11 at 15:30
  • 7
    $\begingroup$ 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. $\endgroup$ – t.b. Oct 27 '11 at 15:41
  • 2
    $\begingroup$ Here's a somewhat related thread $\endgroup$ – t.b. Oct 27 '11 at 15:50
  • 2
    $\begingroup$ @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. $\endgroup$ – Brian M. Scott Oct 27 '11 at 20:25
  • 4
    $\begingroup$ 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? $\endgroup$ – 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.

This is similar to but not exactly the same as using Kolmogorov complexity, which you suggested in your question, since we will not be able to avoid repetition in our enumeration, as the problem of determining whether two programs compute the same set is not decidable. In other words, this enumeration does enumerate reals in their order of Kolmogorov complexity, in the sense that reals with smaller programs are enumerated earlier, but they will also be enumerated again by other programs producing the same real.

Now, for the answer. Using one of the standard models of computability, where we have a one-way infinite tape, and the machine uses a finite alphabet and one halt state, then in my paper "The halting problem is decidable on a set of asymptotic probability one", which is also discussed in the question on The density of halting Turing machine programs, mentioned by t.b. in the comments, it is proved that with asymptotic probability one, the Turing machines accept only finitely many input. See the remarks after corollary 6 in the linked paper, which state that almost every c.e. set is finite.

Conclusion. For this enumeration, almost every computable real has only finitely many $1$s, and therefore is a rational number, with asymptotic probability one.

In fact, for this enumeration, almost every computable real is a dyadic rational. Adopting a three-symbol representation would lead to a different enumeration of the computable reals, according to which almost every (in the sense of asymptotic density) computable real would have only finitely many non-zero digits, in which case almost every computable real is a triadic rational. And so on. Finally, let me say that although we were able to compute the densities, nevertheless the fact that we could fundamentally change the asymptotic density to concentrate on such different sets merely by using three digits instead of two suggests that this notion of density is not robust.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.