;----------------------------------------------------------------------------
; prime.fsm
; David Boozer
; 1 November 2007 (modified, add documentation, rearrange code)
;----------------------------------------------------------------------------
;
; The structure of the tape is as follows:
;
; +-----+---+-----+---+-----+
; |  d  | 0 |  n  | 0 |  x  |
; +-----+---+-----+---+-----+
;
; Initially d is the input, n and x are zero.
;
; During the calculation d holds the potential divisor and x is used
; as a scratchpad.
;
; Algorithm:
;
; 1. copy d, which contains the input, to n
; 2. copy n, which contains the input, to x
; 3. erase leftmost 1 of d
; 4. subtract d from x by marking d and removing 1's from rhs of x
; 5. repeat 4 until x=0
; 6. check marking on d to see if d divides input, if not, goto 3
; 
; bugs: crashes for 0, misidentifies 1 as prime
;----------------------------------------------------------------------------

; copy d to n

001 0 --> 001 0 R
001 1 --> 002 0 R
002 0 --> 003 0 R
002 1 --> 002 1 R
003 0 --> 004 1 L
003 1 --> 003 1 R
004 0 --> 005 0 L
004 1 --> 004 1 L
005 0 --> 007 1 R   ; exit
005 1 --> 006 1 L
006 0 --> 001 1 R
006 1 --> 006 1 L

; copy n to x

007 0 --> 007 0 R
007 1 --> 008 0 R
008 0 --> 009 0 R
008 1 --> 008 1 R
009 0 --> 010 1 L
009 1 --> 009 1 R
010 0 --> 011 0 L
010 1 --> 010 1 L
011 0 --> 013 1 L   ; exit
011 1 --> 012 1 L
012 0 --> 007 1 R
012 1 --> 012 1 L

; erase leftmost 1 of d

013 0 --> 014 0 L
013 1 --> 013 1 L
014 0 --> 001 0 R  ; unreachable?
014 1 --> 015 0 L
015 0 --> 016 0 R
015 1 --> 015 1 L

; repeatedly subtract d from x until x is zero

016 0 --> 026 0 R
016 1 --> 017 0 R
017 0 --> 035 0 R   ; exit (d=0, so input is prime)
017 1 --> 018 1 R
018 0 --> 019 0 R
018 1 --> 018 1 R
019 0 --> 019 0 R
019 1 --> 020 1 R
020 0 --> 021 0 R
020 1 --> 020 1 R
021 0 --> 022 0 L
021 1 --> 021 1 R
022 0 --> 028 0 L   ; exit (x=0, now check if d divides input)
022 1 --> 023 0 L
023 0 --> 024 0 L
023 1 --> 023 1 L
024 0 --> 025 0 L
024 1 --> 024 1 L
025 0 --> 016 1 L
025 1 --> 025 1 L
026 0 --> 027 0 L   ; (one subtraction of d has been completed)
026 1 --> 026 1 R
027 0 --> 001 0 R   ; unreachable?
027 1 --> 019 0 R

; x is now zero, check marking on d to see if d divides input

028 0 --> 029 0 L
028 1 --> 028 1 L
029 0 --> 032 0 L   ; exit (d divides input)
029 1 --> 030 1 L
030 0 --> 031 1 R
030 1 --> 030 1 L
031 0 --> 007 0 R   ; exit (d does not divide input)
031 1 --> 031 1 R

; input is composite

032 0 --> 033 0 R
032 1 --> 032 0 L
033 0 --> 033 0 R
033 1 --> 034 0 R
034 0 --> 000 1 R   ; stop (composite)
034 1 --> 034 0 R

; input is prime

035 0 --> 035 0 R
035 1 --> 036 0 R
036 0 --> 037 0 R
036 1 --> 036 0 R
037 0 --> 037 0 R
037 1 --> 038 0 R
038 0 --> 039 1 R
038 1 --> 038 0 R
039 0 --> 000 1 R   ; stop (prime)
039 1 --> 001 0 R   ; unreachable?