import Turing

--
--  increment
--     Takes a binary number and increments it by one
--
--  Initially, the tape head begins at the left of the input string.  
--  Thus, it's necessary to scan right ("scanRght") to find the rightmost
--  bit.
--
--  Once there ("carry"), we continue to carry 1s until we hit either a 0
--  (which gets incremented to 1) or a blank (which gets rewritten as a 1).
--
--  At that point, we still need to move to the left to position the tape
--  head to the left of the output ("finishUp").
--  
--

increment :: Prog 
increment = [(("scanRght",'0'),('0',Rght,"scanRght")),
	     (("scanRght",'1'),('1',Rght,"scanRght")),
	     (("scanRght",' '),(' ',Lft,"carry")),
	     (("carry",'1'),('0',Lft,"carry")),
	     (("carry",' '),('1',Lft,"finishUp")),
	     (("carry",'0'),('1',Lft,"finishUp")),
	     (("finishUp",'0'),('0',Lft,"finishUp")),
	     (("finishUp",'1'),('1',Lft,"finishUp"))
	    ]

--
--  copy
--     Makes a copy of the original input string; the two strings are
--     separated by a blank.
--
--  Initially, the tape head begins at the left of the input string.  
--  We copy the characters one at a time, leaving a marker to let us know
--  where we left off ("read").
--
--  To copy a single character (once we've marked it), we skip over all 
--  a's and b's ("skipA" if we're copying an 'a', and "skipB" if we're 
--  copying a 'b').
--
--  Once we hit a blank, we move to "copyA"/"copyB", where we again skip
--  over all a's and b's, and look for the next blank cell, where we'll 
--  write the character we're copying.
--
--  We then go back and look for the next character to copy ("getNext").
--  
--


copy :: Prog
copy =  [
	(("read",' '),(' ',Lft,"done")),
	(("read",'a'),('A',Rght,"skipA")),
	(("read",'b'),('B',Rght,"skipB")),
	(("skipA",'a'),('a',Rght,"skipA")),
	(("skipA",'b'),('b',Rght,"skipA")),
	(("skipA",' '),(' ',Rght,"copyA")),
	(("copyA",'a'),('a',Rght,"copyA")),
	(("copyA",'b'),('b',Rght,"copyA")),
	(("copyA",' '),('a',Lft,"getNext")),
	(("skipB",'a'),('a',Rght,"skipB")),
	(("skipB",'b'),('b',Rght,"skipB")),
	(("skipB",' '),(' ',Rght,"copyB")),
	(("copyB",'a'),('a',Rght,"copyB")),
	(("copyB",'b'),('b',Rght,"copyB")),
	(("copyB",' '),('b',Lft,"getNext")),
	(("getNext",'a'),('a',Lft,"getNext")),
	(("getNext",'b'),('b',Lft,"getNext")),
	(("getNext",' '),(' ',Lft,"getNext2")),
	(("getNext2",'a'),('a',Lft,"getNext2")),
	(("getNext2",'b'),('b',Lft,"getNext2")),
	(("getNext2",'A'),('a',Rght,"read")),
	(("getNext2",'B'),('b',Rght,"read")),
	(("done",'a'),('a',Lft,"done")),
	(("done",'b'),('b',Lft,"done"))
       ]