# Using your Head is Permitted

## October 2015 solution

The answer is that the "universality probability" (the probability for a PTM
to stay universal forever) can be as close to 1 as we want.
To construct a machine that remains universal forever with as high probability
as we want, let us begin with some universal PTM, *U*, with some
arbitrary universality probability.

Let us define the PTM *W* as follows.

for i=1,2,3,...
Read k*i bits. If all were 0, simulate U and halt (accept).

Unless the algorithm begins to simulate *U* at some stage, it will continue
forever. As long as it does so, it always has
the potential to start simulating *U*, so the
PTM is clearly universal. However, once the simulation of *U*
starts, the algorithm may halt and lose its universality. Consider the
probability of this happening.

The probability of it happening on round *i* (given that it didn't happen
before) is 2^{-ki}. This makes the total probability of it ever
happening at no more than the sum of all 2^{-ki}, which is
1/(2^{k}-1). By choosing an arbitrarily large *k*, this
can be made as close to 0 as we want. The universality probability, which is
lower-bounded by the complement of this probability,
can therefore be made as close to 1 as we
want.

Notably, the universality probability cannot be exactly 1, because this would
indicate that the PTM never halts, which contradicts it being universal.

The notion of "universality probability" is due to C.S. Wallace, and
this result regarding it was first published by George Barmpalias and
David L. Dowe. See here.

Despite the ability to design machines with universality probability as close
as we wish to any number we choose, it is interesting to note that the
exact probability, if not zero, is uncomputable. Not just that, it is one of
the very few known cases of a
normal number.
(Not only that, the few numbers known to be normal tend to have quite
unnatural-looking definitions. This one, by contrast, has a very natural one,
at least in my opinion.)

Back to riddle

Back to main page