; TM that on input a^k halts and accepts with tape in form
; a^k#(2^k bs)
; Other inputs should cause loops or non-accepting halts
; E.g.
; Input: _
; Output: _#b
; Input: _aaa
; Output _aaa#bbbbbbbb

; Reminder: transition syntax is
;   State Symbol Next-symbol Direction Next-state 

0 _ _ r add-# 

add-# a a r add-#
add-# _ # r add-b

add-b _ b l rewind-and-start

rewind-and-start _ _ * start
rewind-and-start * * l rewind-and-start

start _ _ r find-a

find-a a A r double-bs
find-a A A r find-a
find-a # # l cleanup

double-bs a a r double-bs
double-bs # # r double-bs
double-bs b B r write-B

write-B _ B l more-bs
write-B * * r write-B

more-bs B B l more-bs
more-bs b B r write-B
more-bs # # r revert-B

revert-B B b r revert-B
revert-B _ _ l rewind-and-start

cleanup A a l cleanup
cleanup _ _ * halt-accept