Density of halting Turing machines

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 ?

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:

• Probability that Turing machine is universal?
• Solving NP problems in (usually) polynomial time?
• Turing machines the read the entire tape?
• Proability a random Turing machine is DFA?
• Limits of non-halting?

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.

For example, here is one easy thing to say. Suppose that your Turing machines have alphabet $\{0,1\}$, a set $Q$ of $n$ states, a single halt state (not counted inside $Q$), and the ability to move the head left and right, so that a program is a function $p:Q\times\{0,1\}\to (Q\cup\{\text{halt}\})\times\{0,1\}\times\{\text{left},\text{right}\}$, where $p(s,i)=(t,j,\text{left})$ means that when in state $s$ reading symbol $i$, the program changes to state $t$, writes symbol $j$ and moves left. In particular, for this model the total number of programs is $(4(n+1))^{2n}$.

Consider now the collection of programs that have no transition to the halt state. The total number of such programs is $(4n)^{2n}$, and the interesting thing here is that $$\lim_{n\to\infty}{(4n)^{2n}\over (4(n+1))^{2n}}=\lim_{n\to\infty}[{n\over n+1}]^{2n}=\frac{1}{e^2}$$ which is about 13.5%.

Thus, for this model of computation, at least 13.5% of the programs never halt on any input.

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.

Theorem. There is a set $A$ of Turing machine programs (for machines with one-way infinite tape, single halt state, any finite alphabet) such that:

• One can easily decide whether a program is in $A$; it is polynomial time decidable.
• Almost every program is in $A$; the proportion of all $n$-state programs that are in $A$ converges to $1$ as $n$ becomes large.
• The halting problem is decidable for members of $A$.

Thus, there is a decision procedure to decide almost every instance of the halting problem. The way the proof goes is to calculate, for any fixed input, the probability that a Turing machine will exhibit a fatally trivializing behavior (falling off the left end of the tape before repeating a state), and observing that in fact this occurs with probability $1$. Basically, the behavior of a random Turing machine is sufficiently close to a random walk that one can achieve the Polya recurrence phenomenon.

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.

The theorem can be extended to other models of computation, such as the model with two-way infinite tapes and halting determined by specifying a subset of the states to be halting states. In this model, as you can guess, machines are likely to halt very quickly (since each new state has 50% chance of being halting), and in particular, the halting problem becomes decidable for this reason.

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

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.

Hamkins & Miasnikov's result answers the first part of your question: for Turing machines as we typically model them, you can approximate the halting problem. Quinn's reasoning also shows that you can easily change the way you enumerate programs to get any limit you want.

Now, can you say interesting things about interesting kinds of enumerations? There is one particularly natural class of enumerations: optimal ones. An enumeration $A_1, A_2, ...$ is optimal if for any other enumeration of programs $B_1, B_2, ...$ there exists a constant $K$ such that every program $B_i$ is equivalent to some program $A_j$ with $j<i+K$. These are the same building blocks that you use to define Kolmogorov complexity.

For those, if you define:

$$p_m = \frac{\#\{k\mid k\lt m \text{ and }A_k\text{ halts}\}}{m}$$

you get a very interesting sequence. This sequence does not converge, and all of its accumulation points are $\emptyset'$-random, which mean that their binary expansion is incompressible, even for a Turing machine with access to an oracle giving the answer to the halting problem (see this Wikipedia article for more details).

We can also say interesting things about $\limsup_m p_m$: not only is it $\emptyset'$-random, but it's also $\emptyset'$-upper-semicomputable (which means upper semicomputable by a Turing machine having access to a halting problem oracle). Oh, and both conditions are equivalent: given any $\emptyset'$-random, $\emptyset'$-upper-semicomputable number between $0$ and $1$, you can build an optimal machine having this number as the $\limsup_m p_m$ for this machine.

These results appear in a paper I co-authored about this problem, and some related questions. It was published at ICALP 2015, and the long version was later published in LMCS.