Skip to main content
3 of 3
edited tags
Joel David Hamkins
  • 236.3k
  • 44
  • 777
  • 1.4k

Turing machines that read the entire program tape

Consider a two tape universal 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. Since this TM is universal, $\Omega$ must be in the range $(0,1)$, so the probability must always be in $[0,1)$. Is this entire range, or at least a set dense in this range and including zero, possible?