; Determine if k is prime (input a^k)
;
; The basic plan is to mimic the following
; for n from 2 to k-1:
;   if k % n == 0 halt-reject
; halt-accept
; 
; k is represented by the a^k
; n will be represented as b^n 
; so at the start of the loop the tape will look like a^k#b^n
; the remainder is computed by matching of blocks of bs against as, 
; changing those as to upper case. After each block is matched we 
; check to see if all as have been used - if this was the first block (n was k)
; we accept, and if it was a later block we reject
; If we can't match a final complete block we have seen a non-zero remainder and
; increment n.

; Initialisation
; Add a separator and two b's at the end of the tape
; If there were fewer than two a's halt and reject

0            _   _   r  0a
0a           a   a   r  1a
1a           a   a   r  ok
ok           a   a   r  ok
ok           _   #   r  add-bb
add-bb       _   b   r  add-b
add-b        _   b   l  rewind-#-0
rewind-#-0   #   #   r  get-b1
rewind-#-0   *   *   l  rewind-#-0

; Match the first block of bs against as
; If all as match halt and accept (because we can no longer have a proper factor)

get-b1       b   B   l  get-a1
get-b1       B   B   r  get-b1
get-b1       _   _   l  check-a1
get-b1       *   *   r  get-b1

get-a1       a   A   r  get-b1
get-a1       *   *   l  get-a1

check-a1     a   a   r  next-block
check-a1     _   _   *  halt-accept
check-a1     *   *   l  check-a1

; In next-block we first convert all Bs back to bs

next-block   B   b   r  next-block
next-block   _   _   l  rewind-#
next-block   *   *   r  next-block

; Then rewind to # and collect the next block of bs

rewind-#     #   #   r  get-b
rewind-#     *   *   l  rewind-#

get-b        b   B   l  get-a
get-b        B   B   r  get-b
get-b        _   _   l  check-a
get-b        *   *   r  get-b

; When getting an a if we don't find one this is a non-factor and we reset and increment

get-a        a   A   r  get-b
get-a        _   _   r  increment
get-a        *   *   l  get-a

; Now when checking if we find that all as have been converted to As we
; halt and reject since we found a factor

check-a      a   a   r  next-block
check-a      _   _   *  halt-reject
check-a      *   *   l  check-a

increment    A   a   r  increment
increment    B   b   r  increment
increment    _   b   l  rewind-#-0
increment    *   *   r  increment