Turing machines that read the entire program tape

Question

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?

Answer 1

As far as I can see, if you consider a single TM, then you get only one specific probability, not a dense set, whereas if you let the TM vary then $\Omega$ will vary also, and the set of probabilities will contain all rational numbers in $[0,1]$ (and some other numbers too). If you fix the number of symbols but let the TM vary, it's not so clear that you'll get all the rationals, but you'll still get a dense set.

EDIT to take into account the revision of the question: Given a universal TM, you can make trivial modifications that maintain universality but change the probability $p$ of going infinitely far to the right. For example, modify your original machine $M$ to an $M'$ that works like this: If the first symbol $x$ on the program tape is 0, then halt immediately; otherwise, move one step to the right and work like $M$ on the program minus the initial symbol $x$ (and, just to guarantee universality, if the computation halts, go back to $x$, erase it, and move $M$'s answer one step to the left so that it's located where answers should be). That modification decreases the probability $p$. You can increase $p$ by having an initial 0 in the program trigger a race to the right by $M'$ --- it just keeps marching to the right regardless of what symbols it sees. You can achieve some control over the amount by which $p$ increases or decreases by having the modification $M'$ begin by checking more than just one symbol at the beginning of the program. As far as I can tell, such modifications, carried out with enough care (which I don't have time for just now) should give you a dense set of $p$'s.

EDIT to add some details: Given a universal TM $M$ with tape alphabet $A$, and given a subinterval of $[0,1]$, choose an integer $n$ so large that your given interval includes one of the form $[k/|A|^n,(k+1)/|A|^n]$. Let $S$ be a set of $k$ words of length $n$ over $A$, and let $w$ be another such word that is not in $S$. Modify $M$ to $M'$ that works as follows. If the first $n$ symbols on the tape are a word from $S$, then march to the right forever, ignoring everything else. If they are the word $w$, then simulate $M$ on the remainder of the tape (the part after $w$), moving any final answer into the right location, as in my previous edit. Finally, if the word consisting of the tape's first $n$ letters is neither in $w$ nor in $S$, then halt immediately. Then the probability that $M'$ moves infinitely to the right will be at least $k/|A|^n$ (the probability that the initial $n$-word on the tape is in $S$) and at most $(k+1)/|A|^n$ (the probability that this $n$-word is either $w$ or in $S$) and therefore within the originally given interval.

Answer 2

Andreas considered the interpretation of your question where we fix the program and then vary the input. Let me now consider the dual version of the question, where we fix the infinite random input and vary the program. Surprisingly, there is something interesting to say.

The concept of asymptotic density provides a natural way to measure the size or density of a collection of Turing machine programs. Given a set $P$ of Turing machine programs, one considers the proportion of all $n$-state programs that are in $P$, as $n$ goes to infinity. This limit, when it exists, is called the asymptotic density or probability of the set $P$, and a set with asymptotic density $1$ will contain more than 99% of all $n$-state programs, when $n$ is large enough, as close to 100% as desired.

What I claim is that for your computational model, almost every program leads to a finite computation.

Theorem. For any fixed infinite input (on the read-only tape), the set of Turing machine programs that complete their computation in finitely many steps has asymptotic density $1$.

In other words, for fixed input, almost every program stops in finite time.

The proof follows from the main result of my article: J. D. Hamkins and A. Miasnikov, The halting problem is decidable on a set of asymptotic probability one, Notre Dame J. Formal Logic 47, 2006. http://arxiv.org/abs/math/0504351. The argument depends on the convention in the one-way infinite tape context that computation stops should the head attempt to move off the end of the tape. The idea has also come up on a few other MO quesstions: What are the limits of non-halting? and Solving NP problems in (usually) polynomial time? in which it is explained that the theme of the result is the black-hole phenomenon in undecidability problems, the phenomenon by which the difficulty of an undecidable or infeasible problem is confined to a very small region, outside of which it is easy.

The main result of our paper is to show that the classical halting problem admits a black hole. In other words, there is a computable procedure to correctly decide almost every instance of the classical halting problem, with asymptotic probability one. The proof method is to observe that on fixed infinite input, a random Turing machine operates something like a random walk, up to the point where it begins to repeat states. And because of Polya's recurrence theorem, it follows that with probability as close as you like to one, the work tape head will return to the starting position and fall off the tape before repeating a state.

My point now is that the same observation applies to your problem. For any particular fixed infinite input, the work tape head will fall off for almost all programs. Thus, almost every program sees only finitely much of the input before stopping.