Skip to main content
1 of 3

Turing machines that read the entire program tape

Consider a two tape Turing machine with a one-way-infinite, read-only program tape with a head that can only move right, as well as a work tape. The work tape is initialized to all zeros and the program tape is initialized randomly, with each cell being filled from a uniform distribution over the possible symbols. What are the possibilities for the probability that the head on the program tape will move infinitely far to the right in the limit?

Obviously, this will depend on the specifics of the Turing machine, but it must always be in the range $[0,1-\Omega)$, where $\Omega$ is Chaitin's constant for the TM. Is this entire range, or at least a set dense in this range and including zero, possible?