# 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.  I tacked on a unary-to-decimal
# program at the end.
#
# Input 11..11_11..11 (m 1's, blank, n 1's)
#          
# Output m*n in decimal
# (product m * n, with our pointer in the leftmost position.

# St R W M New
(0, , ,1,r)      # Leftmost 1  (In Boolos, state 1)
(0,1, ,1,r)      # Leftmost 1  (In Boolos, state 1)
(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) 
(14, ,0,15,r) 
(14,1,1,16,r) 
(17, ,*,18,l) 
(19, ,1,20,r) 
(20, , ,20,r) 
(20,1, ,21,l) 
(20,*, ,22,l) 
(18, ,1,23,r) 
(18,0,1,23,r) 
(18,1,2,23,r) 
(18,2,3,23,r) 
(18,3,4,23,r) 
(18,4,5,23,r) 
(18,5,6,23,r) 
(18,6,7,23,r) 
(18,7,8,23,r) 
(18,8,9,23,r) 
(18,9,0,18,l) 
(23,*,*,20,r) 
(23,0,0,23,r) 
(23,1,1,23,r) 
(23,2,2,23,r) 
(23,3,3,23,r) 
(23,4,4,23,r) 
(23,5,5,23,r) 
(23,6,6,23,r)  
(23,7,7,23,r) 
(23,8,8,23,r) 
(23,9,9,23,r) 
(21, , ,21,l) 
(21,*,*,18,l) 
(22, , ,22,l) 
(22,*, ,22,l) 
(16,1,1,16,r)  #Put an end of string marker
(16, ,*,24,l) 
(24,1,1,24,l)  #Goto lefthand 1
(24, , ,25,r) 
(25,1, ,17,l)