I choose a Turing machine T with n states and an input tape at random.

What can be proven about the probability P_A(n) that it is not decidable whether T will halt for a particular input? What can be proven about P_B(n) that T is universal, that means that there exists an algorithm that takes an obvious encoding of an arbitrary Turing machine A (without input tape) and transforms it into an input for my random Turing machine, so that T halts with this input if and only if A halts? In particular: Is it known that P_A(n) is strictly smaller than P_B(n) for some n?

  • $\begingroup$ Are the bits starting on the input tape also chosen at random, or are they all zero? For your first question, do you want undecidable in ZF or something else (like PA)? $\endgroup$ – user5810 Jul 24 '11 at 18:56
  • $\begingroup$ Undecidability is not a property of the axiomatic system, but an intrinsic property of certain subsets of $\omega$. The poster is asking whether one can decide this for all inputs to the Turing machine, so a distribution on inputs is not meaningful either. $\endgroup$ – David Harris Jul 24 '11 at 20:56
  • $\begingroup$ I want to ask whether there exists a Turing machine that always halts and gives the correct answer, not whether that is provable in some axiomatization. I don't know if I understand your first question: My input tape has finite length (it exists in addition to the working tape, and it can be assumed that it is impossible to modify it), and I want to know whether it can be decided for all initial values on the input tape if it halts. If the input tape was always zero, the program would always halt or not halt, so there must exist a program that tells the correct result. $\endgroup$ – twiz Jul 25 '11 at 10:32

The answer will depend on which model of Turing machine you have adopted.

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 and are not universal.

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. And such kind of argument is the main theme of my article (J. D. Hamkins and A. Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. Formal Logic 47, 2006. http://arxiv.org/abs/math/0504351), which came up also in a few other mathoverflow questions: Solving NP problems in (usually) polynomial time?, Turing machines the read the entire tape?. The main theorem of that article 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.

A corollary to this proof, answering your question, is that for this model of computation, the probability that an $n$-state program is a universal program goes to zero as $n$ becomes large, since almost every program exhibits the trivializing behavior, which is incompatible with being universal. 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 so there is a large set of programs for which the halting problem is decidable for this reason (they halt before they repeat a state).

Let me also mention, since you asked not merely about the probability of halting, but also about the probability of decidability of halting, that every computably enumerable set $B\subset\mathbb{N}$ that is not computable admits infinitely many $n$ for which $n\notin B$ but this is not provable in whatever fixed background theory you prefer, such as PA or ZFC or ZFC + large cardinals. The reason is simply that if non-membership in $B$ were provable for all sufficiently large $n$, then we would have a decision procedure for $B$ by searching either for $n$ to be enumerated into $B$ or else searching for a proof that $n$ is not in $B$, and this contradicts our assumption that $B$ is not decidable.

Thus, every c.e. non-computable set sits in a halo of undecidability: there are infinitely many numbers $n$ that are not in $B$, but for which it is also consistent with your favorite theory that they are in $B$.


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.