;----------------------------------------------------------------------------
; mul.fsm
; David Boozer
; 1 November 2007 (modified, add documentation)
;----------------------------------------------------------------------------
;
; The structure of the tape is as follows:
;
; +-----+---+-----+---+-----+
; |  a  | 0 |  b  | 0 |  p  |
; +-----+---+-----+---+-----+
;
; Initially a and b are the two numbers to be multiplied, and p is zero.
;
; Algorithm:
;
; 1. mark a
; 2. add b to p by marking b and adding 1's to rhs of x
; 3. check marking on a to see if we're done
;
; Note: initially neither a nor b can be zero
; Note: could simplify by removing 1's from lhs of a rather than marking a
;
; bugs: crashes if either a or b is zero
;----------------------------------------------------------------------------

; mark a

001 0 --> 001 0 R
001 1 --> 002 0 R
002 0 --> 003 0 R   ; exit
002 1 --> 002 1 R

; add b to p by marking b and adding 1's to rhs of p

003 0 --> 001 0 R   ; unreachable?
003 1 --> 004 0 R
004 0 --> 005 0 R
004 1 --> 004 1 R
005 0 --> 006 1 L
005 1 --> 005 1 R
006 0 --> 007 0 L
006 1 --> 006 1 L
007 0 --> 009 1 L   ; exit
007 1 --> 008 1 L
008 0 --> 003 1 R
008 1 --> 008 1 L

; check marking on a to see if we are done multiplying

009 0 --> 010 0 L
009 1 --> 009 1 L
010 0 --> 012 0 L   ; exit here if we're done
010 1 --> 011 1 L
011 0 --> 001 1 R   ; exit here otherwise
011 1 --> 011 1 L

; we're done; erase b and move head to right side of p

012 0 --> 013 0 L
012 1 --> 012 0 L
013 0 --> 013 0 R
013 1 --> 014 0 R
014 0 --> 015 0 R   ; exit
014 1 --> 014 0 R
015 0 --> 016 0 R
015 1 --> 015 1 R
016 0 --> 000 0 L   ; stop
016 1 --> 000 0 R