1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
|
Tape layout
===========
Imarker: [ 1 | T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9 ]
Rules
- Each rule: [ 0 | tr1 | tr2 | tr3 | tr4 | qfrom | sread | qto | swrite | dir ]
Mmarker: [ 1 | qcurrent | t1 | t2 | t3 ]
Tape
- Each cell: [ 0 | head | tt1 | tt2 | sym ]
Execution step
==============
Precondition: cursor at Mmarker.0 and all temporaries are 0
Find cell with head=1:
Set t1 to 1
While nonzero:
Zero current cell (leftrule.tt1), then move right a rule width; now at tt1
Set tt1 to 1
Move head to tt1 (multiplier -1) and tt2, move tt2 back to head
Now tt1 is not(head).
Go to tt1
Now at zero tt1, which means that head = 1; go to rule.0 for good measure.
Copy sym to tt1 (using tt2 as scratch)
Move tt1 over tt1's back to t1:
Go to tt2, set to 1
While nonzero:
Zero current cell (tt2)
Set leftcell.tt1 to 1
Move leftcell.0 to leftcell.tt2 (multiplier -1) and leftcell.tt1
Move leftcell.tt1 back to leftcell.0
Move tt1 to leftcell.tt1
Go to leftcell.tt2
Now at zero t2, and t1 is sym.
[t1 = sym; tt1 = tt2 = 0 for all cells]
Copy qcurrent and t1 (=sym) to tr1 and tr2 of last rule (using t2 as scratch)
Move to t2 (same offset as tr3), set to 1
While nonzero:
Zero current cell (rightrule.tr3), then move left a rule width; now at tr3
Zero tr3
[tr1 = qcurrent, tr2 = sym]
Copy qfrom to tr4 (using tr3 as scratch)
Copy tr1 to tr3 (using rule.0 as scratch)
[tr1 = qcurrent, tr2 = sym, tr3 = qcurrent, tr4 = qfrom]
Set tr3 to (qcurrent != qfrom): to(tr3) [- to(tr4) - to(tr3)] to(tr4) [to(tr3) + to(tr4) [-]]
Move tr3 to left-rule.tr3 (or T3 if leftmost rule)
[tr1 = qcurrent, tr2 = sym]
Copy sread to tr4 (using tr3 as scratch)
Copy tr2 to tr3 (using rule.0 as scratch)
[tr1 = qcurrent, tr2 = sym, tr3 = sym, tr4 = sread]
Set tr3 to (sym != sread): to(tr3) [- to(tr4) - to(tr3)] to(tr4) [to(tr3) + to(tr4) [-]]
Move tr3 to left-rule.tr4 (or T4 if leftmost rule)
[tr1 = qcurrent, tr2 = sym, prev.tr3 = q!=q, prev.tr4 = s!=s]
Move leftrule.tr3 to tr4 and leftrule.tr4 also to tr4
If tr4 is nonzero: zero tr4 and set tr3 to 1
[tr1 = qcurrent, tr2 = sym, tr3 = q!=q || s!=s]
Copy tr3 to leftrule.tr3 (using rule.0 as scratch)
[tr1 = qcurrent, tr2 = sym, tr3 = q!=q || s!=s, leftrule.tr3 = q!=q || s!=s]
While leftrule.0 is nonzero:
Zero tr3 and set tr4 to 1
Move tr4 to leftrule.0
[tr1 = qcurrent, tr2 = sym, tr3 = (q!=q || s!=s) && not_leftmost_rule, leftrule.tr3 = q!=q || s!=s]
Move tr1 to leftrule.tr1 and tr2 to leftrule.tr2 (or T1 and T2 if leftmost rule)
Go to tr3
Now at a tr3 that is zero. So either this is the last rule, or this rule matches.
Note that leftrule.tr3 is q!=q || s!=s, or in other words, 0 if the current rule matches and 1 otherwise.
While leftrule.tr3:
Apparently no rule matched, so crash().
Apparently leftrule.tr3 is zero, so the current rule matches.
Zero tr1 and tr2
Copy qto to tr2 (using tr1 as scratch)
Copy swrite to tr3 (using tr1 as scratch)
Copy dir to tr4 (using tr1 as scratch)
Go to rightrule.tr2, set to 1
While nonzero:
Now current cell (tr2) is 1
Move rule.0 to tr2 (multiplier -1) and tr3
Move tr3 back to rule.0
Move tr2 to rightrule.tr2
Move leftrule.tr2 to tr2, leftrule.tr3 to tr3, leftrule.tr4 to tr4
Go to rightrule.tr2
Now: [t1 = qto, t2 = swrite, t3 = dir] and cursor is at t1.
Zero qcurrent
Move t1 to qcurrent
Move t2 to t1 and t3 to t2
[t1 = swrite, t2 = dir]
Go to rightcell.tt1, set to 1
While nonzero:
Now current cell (tt1) is 1
Move head to tt1 (multiplier -1) and tt2
Move tt2 back to head
Move tt1 to rightcell.tt1
Move leftcell.tt1 to tt1 and leftcell.tt2 to tt2
Go to rightcell.tt1
Move left a cell width; then at tt1 of the cell where head=1 and [tt1 = swrite, tt2 = dir].
Zero sym
Move tt1 to sym
Move tt2 to cell.0 and tt1
Move cell.0 back to tt2
[tt1 = dir, tt2 = dir]
Go to tt1
While nonzero:
Subtract 1
While nonzero:
Apparently, dir was -1
Set cell.0 to 1 and go back to tt1
Zero tt1
[cell.0 = (dir == -1), tt1 = 0, tt2 = dir]
Go to tt2
While nonzero:
Add 1
While nonzero:
Apparently, dir was 1
Set tt1 to 1 and go back to tt2
Zero tt2
[cell.0 = (dir == -1), tt1 = (dir == 1), tt2 = 0]
Go to cell.0
While nonzero:
While leftcell.0:
Apparently we moved the head beyond the left end of the tape, so crash().
Move head to leftcell.head
Go back to cell.0 and zero cell.0
Go to tt1
While nonzero:
Move head to rightcell.head
Go back to tt1 and zero tt1
[cell.0 = 0, tt1 = 0, tt2 = 0] and head is in the correct spot.
Now go back to Mmarker:
Go to tt1 and set to 1
While nonzero:
Zero current cell (tt1)
Set leftcell.tt1 to 1
Move leftcell.0 to leftcell.tt1 (multiplier -1) and leftcell.tt2
Move leftcell.tt2 back to leftcell.0
Go to leftcell.tt1
Now at t1, so go to Mmarker.0
|
