BadVPN – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | office | 1 | process main { |
2 | # Turing machine specification. |
||
3 | var("B") blank; |
||
4 | var([ |
||
5 | {"0", "0"}:{"0", "0", "right"}, |
||
6 | {"0", "1"}:{"1", "x", "right"}, |
||
7 | {"1", "1"}:{"1", "1", "right"}, |
||
8 | {"1", "0"}:{"2", "0", "right"}, |
||
9 | {"2", "0"}:{"2", "0", "right"}, |
||
10 | {"2", "1"}:{"3", "1", "right"}, |
||
11 | {"3", "1"}:{"3", "1", "right"}, |
||
12 | {"3", "0"}:{"4", "1", "left"}, |
||
13 | {"3", "B"}:{"4", "1", "left"}, |
||
14 | {"4", "1"}:{"4", "1", "left"}, |
||
15 | {"4", "0"}:{"5", "0", "left"}, |
||
16 | {"5", "0"}:{"5", "0", "left"}, |
||
17 | {"5", "1"}:{"6", "1", "left"}, |
||
18 | {"5", "x"}:{"h", "x", "stay"}, |
||
19 | {"6", "1"}:{"6", "1", "left"}, |
||
20 | {"6", "x"}:{"0", "x", "right"}, |
||
21 | {"6", "0"}:{"0", "0", "right"} |
||
22 | ]) rules; |
||
23 | var("0") initial_state; |
||
24 | var({}) initial_tape_left; |
||
25 | var({ |
||
26 | "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", |
||
27 | "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", |
||
28 | "0", "0", |
||
29 | "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", |
||
30 | "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1" |
||
31 | }) initial_tape_right; |
||
32 | |||
33 | # Perform the computation, stopping when no rule matches. |
||
34 | call("turing", {blank, rules, initial_state, initial_tape_left, initial_tape_right}) results; |
||
35 | |||
36 | # Check results. |
||
37 | |||
38 | val_equal(results.tape_left, {"B"}) a; |
||
39 | assert(a); |
||
40 | |||
41 | val_equal(results.tape_right, |
||
42 | {"x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", |
||
43 | "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", "x", |
||
44 | "0", "0", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", |
||
45 | "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", |
||
46 | "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", |
||
47 | "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", "1", |
||
48 | "1", "1"} |
||
49 | ) a; |
||
50 | assert(a); |
||
51 | |||
52 | val_equal({results.side, results.pos}, {"right", "55"}) a; |
||
53 | assert(a); |
||
54 | |||
55 | val_equal(results.state, "h") a; |
||
56 | assert(a); |
||
57 | |||
58 | exit("0"); |
||
59 | } |
||
60 | |||
61 | template turing { |
||
62 | alias("_arg0") blank; |
||
63 | value(_arg1) rules; |
||
64 | alias("_arg2") initial_state; |
||
65 | alias("_arg3") initial_tape_left; |
||
66 | alias("_arg4") initial_tape_right; |
||
67 | |||
68 | # Head state. |
||
69 | var(initial_state) state; |
||
70 | |||
71 | # Tape. Positions go like this: ... L2 L1 L0 R0 R1 R2 ... |
||
72 | value(initial_tape_left) tape_left; |
||
73 | value(initial_tape_right) tape_right; |
||
74 | |||
75 | # Make sure each side of the tape has at least one symbol so we can flip easily. |
||
76 | tape_left->insert(tape_left.length, blank); |
||
77 | tape_right->insert(tape_right.length, blank); |
||
78 | |||
79 | # Head position. |
||
80 | var("right") side; |
||
81 | var("0") pos; |
||
82 | |||
83 | # Enter loop. |
||
84 | blocker() loop_blk; |
||
85 | loop_blk->up(); |
||
86 | loop_blk->use(); |
||
87 | |||
88 | # Get symbol under head. |
||
89 | concat("tape_", side) tape_name; |
||
90 | alias(tape_name) cur_tape; |
||
91 | cur_tape->get(pos) symbol; |
||
92 | |||
93 | # Look for a matching rule. |
||
94 | rules->try_get({state, symbol}) rule; |
||
95 | |||
96 | If (rule.exists) { |
||
97 | # Extract directions from rule. |
||
98 | rule->get("0") new_state; |
||
99 | rule->get("1") new_symbol; |
||
100 | rule->get("2") move; |
||
101 | |||
102 | # Change head state. |
||
103 | state->set(new_state); |
||
104 | |||
105 | # Replace symbol under head. |
||
106 | cur_tape->remove(pos); |
||
107 | cur_tape->insert(pos, new_symbol); |
||
108 | |||
109 | # Branch based on how we move. |
||
110 | strcmp(move, side) is_outside; |
||
111 | strcmp(move, "stay") is_stay; |
||
112 | strcmp(pos, "0") is_zero; |
||
113 | If (is_outside) { |
||
114 | # Increment position. |
||
115 | num_add(pos, "1") new_pos; |
||
116 | pos->set(new_pos); |
||
117 | |||
118 | # If the new position is out of range, extend tape. |
||
119 | strcmp(pos, cur_tape.length) need_extend; |
||
120 | If (need_extend) { |
||
121 | cur_tape->insert(pos, blank); |
||
122 | }; |
||
123 | } elif (is_stay) { |
||
124 | # Nop. |
||
125 | getargs(); |
||
126 | } elif (is_zero) { |
||
127 | # Flip side, leave pos at zero. |
||
128 | side->set(move); |
||
129 | } else { |
||
130 | # Decrement position. |
||
131 | num_subtract(pos, "1") new_pos; |
||
132 | pos->set(new_pos); |
||
133 | }; |
||
134 | |||
135 | # Continue loop. |
||
136 | loop_blk->downup(); |
||
137 | }; |
||
138 | } |