[ create a new paste ] login | about

Link: http://codepad.org/aZZzutGm    [ raw code | output | fork ]

ploffie - Python, pasted on Jun 24:
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)


Output:
1 1>_ 1
('1', 1, 1)
1 1>_ 1
2 >11 0
3 >_11 0
4 >_111 0
5 1>111 1
6 11>11 2
('1111', 2, 6)
1 1>_ 1
2 1_>_ 2
3 1>_1 1
4 >111 0
5 >_111 0
6 1>111 1
7 11>11 2
8 111>1 3
9 1111>_ 4
10 1111_>_ 5
11 1111>_1 4
12 111>111 3
13 11>1111 2
14 111>111 3
('111111', 3, 14)
1 1>_ 1
2 >11 0
3 >_11 0
4 >_111 0
5 1>111 1
6 >1_11 0
7 >_1_11 0
8 1>1_11 1
9 1_>_11 2
10 1_1>11 3
11 1_>1_1 2
12 1>_1_1 1
13 11>1_1 2
14 11_>_1 3
15 11_1>1 4
16 11_>1_ 3
17 11>_1_ 2
18 111>1_ 3
19 111_>_ 4
20 111_1>_ 5
21 111_>11 4
22 111>_11 3
23 11>1111 2
24 1>11111 1
25 >1_1111 0
26 >_1_1111 0
27 1>1_1111 1
28 1_>_1111 2
29 1_1>1111 3
30 1_>1_111 2
31 1>_1_111 1
32 11>1_111 2
33 11_>_111 3
34 11_1>111 4
35 11_>1_11 3
36 11>_1_11 2
37 111>1_11 3
38 111_>_11 4
39 111_1>11 5
40 111_>1_1 4
41 111>_1_1 3
42 1111>1_1 4
43 1111_>_1 5
44 1111_1>1 6
45 1111_>1_ 5
46 1111>_1_ 4
47 11111>1_ 5
48 11111_>_ 6
49 11111_1>_ 7
50 11111_>11 6
51 11111>_11 5
52 1111>1111 4
53 111>11111 3
54 11>1_1111 2
55 1>11_1111 1
56 1_>1_1111 2
57 1>_1_1111 1
58 >111_1111 0
59 >_111_1111 0
60 >_1111_1111 0
61 1>1111_1111 1
62 >1_111_1111 0
63 >_1_111_1111 0
64 1>1_111_1111 1
65 1_>_111_1111 2
66 1_1>111_1111 3
67 1_>1_11_1111 2
68 1>_1_11_1111 1
69 11>1_11_1111 2
70 11_>_11_1111 3
71 11_1>11_1111 4
72 11_>1_1_1111 3
73 11>_1_1_1111 2
74 111>1_1_1111 3
75 111_>_1_1111 4
76 111_1>1_1111 5
77 111_>1__1111 4
78 111>_1__1111 3
79 1111>1__1111 4
80 1111_>__1111 5
81 1111_1>_1111 6
82 1111_>111111 5
83 1111>_111111 4
84 111>11111111 3
85 11>111111111 2
86 1>1_11111111 1
87 >11_11111111 0
88 _>1_11111111 1
89 >_1_11111111 0
90 >_11_11111111 0
91 1>11_11111111 1
92 >1_1_11111111 0
93 >_1_1_11111111 0
94 1>1_1_11111111 1
95 1_>_1_11111111 2
96 1_1>1_11111111 3
97 1_>1__11111111 2
98 1>_1__11111111 1
99 11>1__11111111 2
100 11_>__11111111 3
101 11_1>_11111111 4
102 11_>1111111111 3
103 11>_1111111111 2
104 1>111111111111 1
105 >1111111111111 0
106 >__111111111111 0
107 1>_111111111111 1
('1_111111111111', 1, 107)


Create a new paste based on this one


Comments: