# 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 _ _ r 1     # Leftmost 1  (In Boolos, state 1)
0 1 _ r 1     # Leftmost 1  (In Boolos, state 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 400
17 1 1 l 17
400 _ 0 r 40100
400 1 1 r 4040
401 _ * l 404
402 _ 1 r 403
403 _ _ r 403
403 1 _ l 406
403 * _ l 407
404 _ 1 r 405
404 0 1 r 405
404 1 2 r 405
404 2 3 r 405
404 3 4 r 405
404 4 5 r 405
404 5 6 r 405
404 6 7 r 405
404 7 8 r 405
404 8 9 r 405
404 9 0 l 404
405 * * r 403
405 0 0 r 405
405 1 1 r 405
405 2 2 r 405
405 3 3 r 405
405 4 4 r 405
405 5 5 r 405
405 6 6 r 405 
405 7 7 r 405
405 8 8 r 405
405 9 9 r 405
406 _ _ l 406
406 * * l 404
407 _ _ l 407
407 * _ l 407
4040 1 1 r 4040 #Put an end of string marker
4040 _ * l 4041
4041 1 1 l 4041 #Goto lefthand 1
4041 _ _ r 4042
4042 1 _ l 401