Probability that a Turing machine is universal? 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?
 A: 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$.
