ploffie

Turing beavers

Jun 24th, 2014
189
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. HALT = -1
  2.  
  3. def simulate(program, tape, head, NULL="_", display=False):
  4.     tape, state = list(tape), 0
  5.     rules = {rule[:2]: rule[2:] for rule in program}
  6.     steps = 0
  7.     while state != HALT:
  8.         steps += 1
  9.         output, direction, state = rules[(state, tape[head])]
  10.         tape[head] = output
  11.         if direction == "L":
  12.             if head == 0:
  13.                 tape.insert(0, NULL)
  14.             else:
  15.                 head -= 1
  16.         elif direction == "R":
  17.             if head == len(tape) - 1:
  18.                 tape.append(NULL)
  19.             head += 1
  20.         if display:
  21.             print steps, "".join(tape[:head] + [">"] + tape[head:]), head
  22.     return "".join(tape).strip(NULL), head, steps
  23.    
  24. busy_beaver1 = [(0, "_", "1", "R", HALT),
  25.                ]
  26.    
  27. busy_beaver2 = [(0, "_", "1", "R", 1),
  28.                (1, "_", "1", "L", 0),
  29.                (0, "1", "1", "L", 1),
  30.                (1, "1", "1", "R", HALT),
  31.                ]
  32.    
  33. busy_beaver3 = [(0, "_", "1", "R", 1),
  34.                (1, "_", "_", "R", 2),
  35.                (2, "_", "1", "L", 2),
  36.                (0, "1", "1", "R", HALT),
  37.                (1, "1", "1", "R", 1),
  38.                (2, "1", "1", "L", 0),
  39.                ]
  40.  
  41. busy_beaver4 = [(0, "_", "1", "R", 1),
  42.                (1, "_", "1", "L", 0),
  43.                (2, "_", "1", "R", HALT),
  44.                (3, "_", "1", "R", 3),
  45.                (0, "1", "1", "L", 1),
  46.                (1, "1", "_", "L", 2),
  47.                (2, "1", "1", "L", 3),
  48.                (3, "1", "_", "R", 0),
  49.                ]
  50.  
  51. tape, head = "_", 0
  52. for program in [busy_beaver1, busy_beaver2, busy_beaver3, busy_beaver4]:
  53.     print simulate(program, tape, head, display=True)
RAW Paste Data