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