codepad
[
create a new paste
]
login
|
about
Language:
C
C++
D
Haskell
Lua
OCaml
PHP
Perl
Plain Text
Python
Ruby
Scheme
Tcl
HALT = -1 def simulate(program, tape, head, NULL="_", display=False): tape, state = list(tape), 0 rules = {} for rule in program: rules[rule[:2]] = rule[2:] 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)
Private
[
?
]
Run code
Submit