Busy beaver on right-moving turing machine?

74 Views Asked by At

So, unless I'm being very silly, it seems completely obvious, that the maximum number of 1s a right moving TM can write is equal to "the number states it has" - 1.

It can't really store anything as it's just moving right, so there's no reason it should write anything else other than 1. The only "memory" it has, is the state it's in.

So, it can't really loop back to any state it's already been in, because then it would just be an infinite loop. However, I'm struggling to formulate this intuition as a formal answer. Would induction be the right way? Or is there a simpler way to prove this?

1

There are 1 best solutions below

0
On BEST ANSWER

I'm assuming that by "right moving TM" you mean a Turing Machine which defined in the same way as for the traditional Busy Beaver problem, except that all transitions must move to the right.

If so, then I agree with your assessment. Using standard Busy Beaver nomenclature we'd say that $BBR(n) = n$ (the largest number of 1s that an $n$ state TM can write is $n$). Note that traditionally we don't count the halt state in the number of states, which I assume is why you say "number of states - 1".

To prove this, we can start by noting that we can completely ignore all of the parts of the transition table that result from reading 1s since this TM will only ever read 0s. Second, we can note that the symbol written doesn't affect the behavior of the TM (it will never read those symbols), they only affect the "score" of the TM.

So, from a behavioral point of view, we can simplify this TM transition function to a simple directed graph among the states (with exactly one edge leaving each state node except for the halt node which has 0). The behavior of this TM is precisely defined by starting at the start node and repeatedly following the single outgoing edge, stopping if we reach the halt state. If this process takes longer than $n$ steps, then by the "pigeon-hole principle" we must have entered the same state more than once (as there are only $n$ non-halt states). But that means that we are in a loop on the state graph. Since the TMs current state is the only thing determining what happens next (it has no other memory as you mention), it will repeat this loop forever.

Therefore, for any halting TM, it must halt within $\le n$ steps. Among those, you can easily demonstrate a TM that writes exactly $n$ 1s and that completes the proof :)