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/(2k-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