# Multiply
# multiply two numbers (written as a sum of ones)
#
# This implements the program in Jeffrey and Boolos. 
# The alphabet consists only of 1 and blank.
#
# Input 11..11_11..11 (m 1's, blank, n 1's)
#          
# Output 11..11 (product m * n, with our pointer in the leftmost position.
#
# Bugs to be fixed: Doesn't handle m * 0.  
#    Doesn't handle 0 * m, but I guess that's not valid input a la Boolos!


# St R W M New
(0, , ,1,r)      # Leftmost 1  (In Boolos, state 1)
(0,1, ,1,r)      # 
(1, , ,2,r)     # Boolos state 2
(1,1,1,3,r)      # 
(3, , ,4,r)      # Boolos state 3
(3,1,1,3,r)      # 
(4, , ,4,r)      # Boolos state 4
(4,1, ,5,r)      # 
(5, ,1,6,l)     # Boolos state 6
(5,1,1,7,r)      #
(7, , ,8,r)      # Boolos state 7
(7,1,1,7,r)      #
(8, ,1,9,l)     # Boolos state 8
(8,1,1,10,r) 
(10, ,1,9,l)     # Boolos state 9
(10,1,1,10,r)      # 
(9, , ,11,l)    # Boolos state 10
(9,1,1,9,l)    #
(11, , ,4,r)     # Boolos state 11
(11,1,1,11,l) 
(6, , ,6,l)    # Boolos state 13
(6,1,1,12,l)    
(12, , ,0,r)     # Boolos state 14
(12,1,1,12,l)    #
(2, ,1,2,r)    # Boolos state 15
(2,1,1,13,l) 
(13, , ,14,r) 
(13,1,1,13,l)