# 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 _ _ r 1     # Leftmost 1  (In Boolos, state 1)
0 1 _ r 1     # 
1 _ _ r 15    # Boolos state 2
1 1 1 r 2     # 
2 _ _ r 3     # Boolos state 3
2 1 1 r 2     # 
3 _ _ r 3     # Boolos state 4
3 1 _ r 4     # 
4 _ 1 l 13    # Boolos state 6
4 1 1 r 7     #
7 _ _ r 8     # Boolos state 7
7 1 1 r 7     #
8 _ 1 l 10    # Boolos state 8
8 1 1 r 9
9 _ 1 l 10    # Boolos state 9
9 1 1 r 9     # 
10 _ _ l 11   # Boolos state 10
10 1 1 l 10   #
11 _ _ r 3    # Boolos state 11
11 1 1 l 11
13 _ _ l 13   # Boolos state 13
13 1 1 l 14   
14 _ _ r 0    # Boolos state 14
14 1 1 l 14   #
15 _ 1 r 15   # Boolos state 15
15 1 1 l 17
17 _ _ r 18
17 1 1 l 17