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 ?

  • 3
    $\begingroup$ You probably want to get on Wikipedia and look up Chaitin's constant Omega... $\endgroup$ – Craig Oct 16 '11 at 23:16
  • 2
    $\begingroup$ 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}$. $\endgroup$ – Quinn Culver Oct 16 '11 at 23:56

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.

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$.

| cite | 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.

| 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.