Turing Machine Multiplication--Code
 
 

---

# Turing machine to multiply two numbers:
# Number n is represented by string of n+1 1's.
# Initially, tape is assumed to be in form of _n1_n2_ (where _ is blank),
# and head is assumed to be positioned at leftmost non-blank square.
# Initial internal machine state is "start".
# At halt, tape is _n1_n2_n3_, where n3=n1*n2,
# and head is positioned at leftmost non-blank square.
start, 1, move1right, W, R	# mark first bit of 1st argument
move1right, 1, move1right, 1, R	# move right til past 1st argument
move1right, _, mark2start, _, R	# square between 1st and 2nd arguments found
mark2start, 1, move2right, Y, R	# mark first bit of 2nd argument
move2right, 1, move2right, 1, R	# move right til past 2nd argument
move2right, _, initialize, _, R	# square between 2nd argument and answer found
initialize, _, backup, 1, L	# put a 1 at start of answer
backup, _, backup, _, L		# move back to leftmost unused bit of 1st arg
backup, 1, backup, 1, L		# ditto
backup, Z, backup, Z, L		# ditto
backup, Y, backup, Y, L		# ditto
backup, X, nextpass, X, R	# in position to start next pass
backup, W, nextpass, W, R	# ditto
nextpass, _, finishup, _, R	# if square is blank, we're done. finish up
nextpass, 1, findarg2, X, R	# if square is not blank, go to work. mark bit
findarg2, 1, findarg2, 1, R	# move past 1st argument
findarg2, _, findarg2, _, R	# square between 1st and 2nd arguments
findarg2, Y, testarg2, Y, R	# start of 2nd arg. skip this bit, copy rest
testarg2, _, cleanup2, _, L	# if blank, we are done with this pass
testarg2, 1, findans, Z, R	# if not, increment ans. mark bit, move there
findans, 1, findans, 1, R	# still in 2nd argument
findans, _, atans, _, R		# square between 2nd argument and answer
atans, 1, atans, 1, R		# move through answer
atans, _, backarg2, 1, L	# at end of answer--write a 1 here, go back
backarg2, 1, backarg2, 1, L     # move left to first unused bit of 2nd arg
backarg2, _, backarg2, _, L     # ditto
backarg2, Z, testarg2, Z, R     # just past it. move right, and test it
backarg2, Y, testarg2, Y, R     # ditto
cleanup2, 1, cleanup2, 1, L	# move back through answer
cleanup2, _, cleanup2, _, L	# square between 2nd arg and answer
cleanup2, Z, cleanup2, 1, L	# restore bits of 2nd argument
cleanup2, Y, backup, Y, L	# done with that. backup to start next pass
finishup, Y, finishup, 1, L	# restore first bit of 2nd argument
finishup, _, finishup, _, L	# 2nd argument restored, move back to 1st
finishup, X, finishup, 1, L	# restore bits of 1st argument
finishup, W, almostdone, 1, L	# restore first bit of 1st arg. almost done
almostdone, _, halt, _, R	# done with work. position properly and halt