diff options
| -rw-r--r-- | algorithm.txt | 168 |
1 files changed, 168 insertions, 0 deletions
diff --git a/algorithm.txt b/algorithm.txt new file mode 100644 index 0000000..82e0d69 --- /dev/null +++ b/algorithm.txt @@ -0,0 +1,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 |