aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--algorithm.txt109
-rw-r--r--bfturing.bf180
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
+ >>++++++++[-<--------->]<
+]