Search code examples
algorithmcomputer-scienceautomata

Why can't a N-State busy beaver keep going to the right?


I'm reading about Busy Beavers but if they have an infinite tape, why can't they keep infinitely printing 1's to the Right? Why do they have to keep going left and right


Solution

  • I will elaborate slightly more since my comment was probably not enough to solve your issue. Have you constructed a busy beaver that only moves to the right? Let's try for N = 2:

    • State A, tape 0 ==> write 1, move right, go to state A/B (select whichever you like)
    • State B, tape 0 ==> write 1, move right, go to state A/B (select whichever you like)
    • (definitions for tape 1 don't matter, will not occur when only moving right)

    You can see that this will write a lot of ones! But it will never halt, and the rules of the game are to write a halting turing machine.

    So we have to modify this to halt:

    • State A, tape 0 ==> write 1, move right, go to state B
    • State B, tape 0 ==> write 1, move right, go to state HALT
    • (definitions for tape having 1 don't matter, this will not occur)

    But now we can see how inefficient we are being, completely ignoring a lot of available options. So we add moving left to our arsenal to become more efficient. I will shorthand the notation now, hopefully it will be easier to read.

    • A, 0 => 1, Right, B
    • B, 0 => 1, Left, A (we must go left here to avoid never halting)
    • A, 1 => 1, Left, B
    • B, 1 => 1, <any>, HALT (last option, must be a halt)

    So the execution we get is:

    1. ...0 0 0 0 0..., A => 1, Right, B
    2. ...0 0 1 0 0..., B => 1, Left, A
    3. ...0 0 1 1 0..., A => 1, Left, B
    4. ...0 0 1 1 0..., B => 1, Left, A
    5. ...0 1 1 1 0..., A => 1, Right, B
    6. ...1 1 1 1 0..., B => 1, <any>, HALT

    Thus the final tape has 4 ones after six steps, which was much better than the result we achieved when only moving to the right.