Using your Head is Permitted

The following riddle comes from David L. Dowe. (Thanks, David!)

A Prefix Turing Machine (PTM) is a a Turing machine whose input is a one-sided-infinite tape (for simplicity, we'll consider tapes over the binary alphabet), which, at each execution step, reads the next bit of its input. The machine always reads exactly one bit and can never go back to previous inputs. At each step, the machine may decide to accept the input (in which case it halts). If it never decides to accept, we say that the input is rejected.

PTMs are as powerful as general Turing machines. As with general Turing machines, PTMs can be universal. A universal Turing machine is one that can simulate any other Turing machine. In the case of PTMs, the definition of "simulate" is especially elegant: machine U is said to be able to simulate machine V if there is some finite binary string x such that if the input to U begins with the string x, the machine accepts/rejects the rest of the input if and only if V would have accepted/rejected it. (V's input, in this example, does not include x.)

We denote this by "Ux=V". V accepts m if and only if U accepts xm, and this can also be stated as "Ux accepts m" (or "Uxm is an accepting state"). Accordingly, the statement "U is universal" is equivalent to "For all V there exists an x such that Ux=V".

David's question relates to universal PTMs whose input is random (each input bit is uniformly and independently distributed). He asks:

What is the (asymptotic) probability that after an infinite number of steps a universal PTM remains universal? Specifically, what is this probability for the universal PTM that maximises this metric?

As always: prove your answer.

List of solvers: