Turing Machine Multiplication--Code

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