diff options
| -rw-r--r-- | algorithm.txt | 109 | ||||
| -rw-r--r-- | bfturing.bf | 180 |
2 files changed, 247 insertions, 42 deletions
diff --git a/algorithm.txt b/algorithm.txt index 109a7b1..a810953 100644 --- a/algorithm.txt +++ b/algorithm.txt @@ -11,6 +11,8 @@ Mmarker: [ 1 | qcurrent | t1 | t2 | t3 ] Tape - Each cell: [ 0 | head | tt1 | tt2 | sym ] +EXPLICITLY USED: sizeof(rule) == 2 * sizeof(cell) + Read input ========== @@ -19,56 +21,77 @@ Write 1, move right a rule width Go to tr1 Write 1 While nonzero: + Subtract 1 from tr1 Read into qfrom - - Read into sread - Copy to sread+1 (scratch sread+2) - Write 1 to sread+2 - Subtract 32 from sread+1 and go to sread+1 + Copy to tr4 (using tr3 as scratch) + Write 1 to tr3 ("should zero qfrom") + Go to tr4 and add 1 While nonzero: - Subtract 1 from sread+2 - Zero sread+1 and go to sread+1 - Go to sread+2 - While nonzero: - Zero sread - Zero sread+2 and go to sread+2 - Go to sread + Zero tr4 + Subtract 1 from tr3 + Write 1 to rightrule.tr1 - Read into qto + Read into sread + Copy to sread+1 (scratch sread+2) + Write 1 to sread+2 + Subtract 32 from sread+1 and go to sread+1 + While nonzero: + Subtract 1 from sread+2 + Zero sread+1 and go to sread+1 + Go to sread+2 + While nonzero: + Zero sread + Zero sread+2 and go to sread+2 - Read into swrite - Copy to swrite+1 (scratch swrite+2) - Write 1 to swrite+2 - Subtract 32 from swrite+1 and go to swrite+1 - While nonzero: - Subtract 1 from swrite+2 - Zero swrite+1 and go to swrite+1 - Go to swrite+2 - While nonzero: - Zero swrite - Zero swrite+2 and go to swrite+2 - Go to swrite + Read into qto - Read into dir - Subtract '=' (61) from dir - Copy qfrom to tr4 (using tr3 as scratch) - Go to tr4 - While nonzero: - Add 1 + Read into swrite + Copy to swrite+1 (scratch swrite+2) + Write 1 to swrite+2 + Subtract 32 from swrite+1 and go to swrite+1 While nonzero: - Write 1 to rightrule.tr1 - Zero tr4 - Zero tr4 + Subtract 1 from swrite+2 + Zero swrite+1 and go to swrite+1 + Go to swrite+2 + While nonzero: + Zero swrite + Zero swrite+2 and go to swrite+2 + + Read into dir + Subtract '=' (61) from dir + + Go to tr4 + + Go to tr3 + While nonzero: + Zero qfrom + Zero tr3 and go to tr3 Go to rightrule.tr1, which is 1 precisely if we didn't have EOF -Now at a zero tr1 that is really the qcurrent of Mmarker +Now at a zero tr1 that is one rule width too far. +So go one rule width left, at which point we are on the qcurrent of Mmarker. Write 'S' (83), and go to Mmarker.0 Write 1 Set rightcell.head to 1 Go back to Mmarker.0 +Main loop +========= + +Precondition: cursor at Mmarker.0 and all temporaries are 0 + +Subtract 'H' from qcurrent (using t1 as scratch) +While qcurrent is nonzero: + Add 'H' to qcurrent + Go to Mmarker.0 + + Perform execution step + + Subtract 'H' from qcurrent + + Execution step ============== @@ -77,7 +100,7 @@ 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 + Zero current cell (leftrule.tt1), then move right a cell 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). @@ -89,7 +112,7 @@ 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 + Set leftcell.tt2 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 @@ -97,8 +120,9 @@ Move tt1 over tt1's back to t1: 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 +Copy qcurrent to tr1 of last rule (using t2 as scratch) +Move t1 (=sym) to tr2 of last rule +Go 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 @@ -126,6 +150,7 @@ While nonzero: [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 + Zero leftrule.0 Move tr4 to leftrule.0 [tr1 = qcurrent, tr2 = sym, tr3 = (q!=q || s!=s) && not_leftmost_rule, leftrule.tr3 = q!=q || s!=s] @@ -139,7 +164,7 @@ While leftrule.tr3: Apparently no rule matched, so crash(). Apparently leftrule.tr3 is zero, so the current rule matches. -Zero tr1 and tr2 +Zero leftrule.tr1 and leftrule.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) @@ -151,9 +176,9 @@ While nonzero: 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 + Go to rightrule.tr2 (or tt1 of second cell! Here we use that sizeof(rule) == 2 * sizeof(cell)) -Now: [t1 = qto, t2 = swrite, t3 = dir] and cursor is at t1. +Now: [t1 = qto, t2 = swrite, t3 = dir] and cursor is at tt1 of second cell. Zero qcurrent Move t1 to qcurrent diff --git a/bfturing.bf b/bfturing.bf new file mode 100644 index 0000000..536dd51 --- /dev/null +++ b/bfturing.bf @@ -0,0 +1,180 @@ +READ INPUT + ++ >>>>>>>>>> +> + +[ + - + >>>> , + [-<+<+>>]<<[->>+<<] + + + > + + [ + [-] + < - + >>>>>>>> + + + <<<<< , + [->+>+<<]>>[-<<+>>] + + + < -------------------------------- + [>-<[-]] + > [<<[-]>>[-]] + < , + > , + [->+>+<<]>>[-<<+>>] + + + < -------------------------------- + [>-<[-]] + > [<<[-]>>[-]] + + < , + >++++++[-<---------->]<- + + <<<<< + ] + + < + [ >> [-] << [-] ] + + >>>>>>>> +] + +<<<<<<<<<< + +>+++++++[-<++++++++++++>]<- < ++ +>>>>>> + <<<<<< + + +MAIN LOOP + +>>++++++++[-<--------->]< +[ + >++++++++[-<+++++++++>]<< + + EXECUTION STEP + + >> + + [ + - >>>>> + + <[->->+<<]>>[-<<+>>]< + ] + << + + >>>> [-<+<+>>]<[->+<] + + + [ + - + <<<<< + + <<< [->>+>-<<<] >> [-<<+>>] + >>>>> [-<<<<<+>>>>>] <<<< + ] + + << [-<<<<<<<<<<+>>>>>>>>>> >>+<<] >>[-<<+>>] + < [-<<<<<<<<<<+>>>>>>>>>>] + > + + [ + [-] <<<<<<<<<< [-] + >> [-<+<+>>]<<[->>+<<] + << [-<+>>>+<<]<[->+<] + >>> [->-<]>[<+>[-]] + < [-<<<<<<<<<<+>>>>>>>>>>] + + >>> [-<<+<+>>>]<<<[->>>+<<<] + < [-<<+>>>+<]<<[->>+<<] + >>> [->-<]>[<+>[-]] + < [-<<<<<<<<<+>>>>>>>>>] + + <<<<<<<<<< [->>>>>>>>>>>+<<<<<<<<<<<] + > [->>>>>>>>>>+<<<<<<<<<<] >>>>>>>>>> + [[-]<+>] + + < [-<<<+<<<<<<<+>>>>>>>>>>]<<<[->>>+<<<] + + <<<<<<<<<< [>>>>>>>>>> >>>[-]>+<<<< <<<<<<<<<<-] + >>>>>>>>>> >>>> [-<<<< <<<<<<<<<<+>>>>>>>>>> >>>>] + + <<< [-<<<<<<<<<<+>>>>>>>>>>] + > [-<<<<<<<<<<+>>>>>>>>>>] + > + ] + + <<<<<<<<<< + [$] CRASH + + << [-] > [-] + >>>>>>>>>> >>>>> [-<<<<<+<+>>>>>>]<<<<<<[->>>>>>+<<<<<<] + >>>>>>> [-<<<<<+<<+>>>>>>>]<<<<<<<[->>>>>>>+<<<<<<<] + >>>>>>>> [-<<<<<+<<<+>>>>>>>>]<<<<<<<<[->>>>>>>>+<<<<<<<<] + + >>>>>>>>>>> + + [ + << [->>->+<<<] >>> [-<<<+>>>] + < [->>>>>>>>>>+<<<<<<<<<<] + <<<<<<<<<< [->>>>>>>>>>+<<<<<<<<<<] + > [->>>>>>>>>>+<<<<<<<<<<] + > [->>>>>>>>>>+<<<<<<<<<<] + >>>>>>>> >>>>>>>>>> + ] + + <<<<<<<<<< + + < [-] + > [-<+>] + > [-<+>] > [-<+>] + + >>> + + [ + < [->->+<<] >> [-<<+>>] + < [->>>>>+<<<<<] + <<<<< [->>>>>+<<<<<] > [->>>>>+<<<<<] >>>> + >>>>> + ] + + <<<<< + + >> [-] + << [->>+<<] + + > [-<+<<+>>>] <<< [->>>+<<<] + + >> + [ + - + [<<+>>[-]] + ] + + > + [ + + + [<+>[-]] + ] + + <<< + [ + <<<<< + [$] CRASH + >>>>>> [-<<<<<+>>>>>] + < [-] + ] + + >> + [ + < [->>>>>+<<<<<] + > [-] + ] + + + + [ + - + <<<<< + + << [->>->+<<<] >>> [-<<<+>>>] + < + ] + + << + + + FINAL PART OF MAIN LOOP + >>++++++++[-<--------->]< +] |