Turing beavers

HALT = -1

def simulate(program, tape, head, NULL="_", display=False):
    tape, state = list(tape), 0
    rules = {rule[:2]: rule[2:] for rule in program}
    steps = 0
    while state != HALT:
        steps += 1
        output, direction, state = rules[(state, tape[head])]
        tape[head] = output
        if direction == "L":
            if head == 0:
                tape.insert(0, NULL)
            else:
                head -= 1
        elif direction == "R":
            if head == len(tape) - 1:
                tape.append(NULL)
            head += 1
        if display:
            print steps, "".join(tape[:head] + [">"] + tape[head:]), head
    return "".join(tape).strip(NULL), head, steps

busy_beaver1 = [(0, "_", "1", "R", HALT),
               ]

busy_beaver2 = [(0, "_", "1", "R", 1),
               (1, "_", "1", "L", 0),
               (0, "1", "1", "L", 1),
               (1, "1", "1", "R", HALT),
               ]

busy_beaver3 = [(0, "_", "1", "R", 1),
               (1, "_", "_", "R", 2),
               (2, "_", "1", "L", 2),
               (0, "1", "1", "R", HALT),
               (1, "1", "1", "R", 1),
               (2, "1", "1", "L", 0),
               ]

busy_beaver4 = [(0, "_", "1", "R", 1),
               (1, "_", "1", "L", 0),
               (2, "_", "1", "R", HALT),
               (3, "_", "1", "R", 3),
               (0, "1", "1", "L", 1),
               (1, "1", "_", "L", 2),
               (2, "1", "1", "L", 3),
               (3, "1", "_", "R", 0),
               ]

tape, head = "_", 0
for program in [busy_beaver1, busy_beaver2, busy_beaver3, busy_beaver4]:
    print simulate(program, tape, head, display=True)