Return to Answer

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.

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.

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

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.

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 the halting problem becomes decidable for this reason.

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