Take the 2-minute tour ×

If we enumerate all Turing machines, $T_1$, $T_2$, $T_3,\ldots,T_n,\ldots$, What is $$\lim_{m\to\infty}\frac{\#\{k\mid k\lt m \text{ and }T_k\text{ halts}\}}{m}\quad?$$

Or does this depend on how we enumerate them ?

share|improve this question
You probably want to get on Wikipedia and look up Chaitin's constant Omega... –  Craig Oct 16 '11 at 23:16
You probably want to specify that the enumeration is computable. Otherwise - since there are infinitely many machines that halt and infinitely many that don't - you could enumerate the machines one way so that the limit is $\frac{1}{2}$ and another way so that $\frac{1}{3}$. –  Quinn Culver Oct 16 '11 at 23:56

2 Answers 2

up vote 25 down vote accepted

This question is exactly the theme of my article, "The halting problem is decidable on a set of asymptotic probability one," (J. D. Hamkins and A. Miasnikov, Notre Dame J. Formal Logic 47, 2006, various links available at http://boolesrings.org/hamkins/haltingproblemdecidable/).

Similar questions have arisen several times on mathoverflow:

The answer is that it depends on the model of computation. (This fact comes after the issue of enumeration raised in the comments and in the answer of Quinn Culver, which seems partially addressed by the fact that we have several canonical enumeration of Turing machine programs based on the fact that for any $n$ there are only finitely many programs having $n$ states.)

One of the ideas is that it may be more natural to consider the asymptotic density of the desired set of programs, by considering the limit of the proportion of all $n$-state programs with the property, as $n$ goes to infinity. This seems to avoid the trivializing effects of arbitrary rearranged enumerations.




The topic is fun, because we are in effect considering the behavior of a random program, where each new program line is chosen randomly from among all the legal program lines. The main theorem of my article with Miasnikov is the following.




Corollary. For this model of computation, for any enumeration listing the programs in order of the number of states, your limit is $0$.

The reason is that the probability that an $n$-state program is halting (in the sense of reaching the halt state) goes to zero as $n$ becomes large, since almost every program exhibits the trivializing behavior of falling off the tape. Furthermore, the set of programs with that behavior is decidable.


Theorem. For the halting state model of computation, for any enumeration listing the programs by the number of states, your limit is $1$.

share|improve this answer

As I pointed out in the comments above, if the enumeration isn't required to be computable, then the value of the limit definitely depends on the enumeration. In fact, it depends upon the enumeration anyway. To wit, fix two machines $T$, which halts, and $S$, which doesn't halt. Given an enumeration (computable or not), use the padding lemma to insert $T$ frequently enough into the enumeration (thus creating a new enumeration) to ensure that the limit is 1. Or do the same with $S$ to ensure that the limit is 0.

share|improve this answer

Your Answer


