# 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
Welcome to the
These web essays are designed for those who have already discovered the joys of mathematics as well as for those who may be uncomfortable with mathematics.
Read more . . .