<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
<HTML>
<HEAD>
<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=US-ASCII">
<META NAME="Generator" CONTENT="MS Exchange Server version 5.5.2657.73">
<TITLE>Perl Quiz of the Week #24 (Turing Machine simulation)</TITLE>
</HEAD>
<BODY>

<P><FONT SIZE=2>From: mjd@plover.com [<A HREF="mailto:mjd@plover.com">mailto:mjd@plover.com</A>] On Behalf Of Zed Lopez</FONT>
<BR><FONT SIZE=2>Sent: Wednesday, September 15, 2004 9:01 AM</FONT>
<BR><FONT SIZE=2>To: perl-qotw@plover.com</FONT>
<BR><FONT SIZE=2>Subject: [Retrieved]Perl Quiz of the Week #24 (Turing Machine simulation)</FONT>
</P>
<BR>

<P><FONT SIZE=2>IMPORTANT: Please do not post solutions, hints, or other spoilers</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; until at least 60 hours after the date of this message.</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Thanks.</FONT>
</P>

<P><FONT SIZE=2>WICHTIG: Bitte schicken Sie keine Lsungen, Tipps oder Hinweise fr</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; diese Aufgabe vor Ablauf von 60 Stunden nach dem Datum dieser</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; Mail. Danke.</FONT>
</P>

<P><FONT SIZE=2>BELANGRIJK: Stuur aub geen oplossingen, hints of andere tips in de</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; eerste 60 uur na het verzendingstijdstip van dit</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; bericht. Waarvoor dank.</FONT>
</P>

<P><FONT SIZE=2>VNIMANIE: Pozhalujsta ne shlite reshenija, nameki na reshenija, i</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; voobshe lyubye podskazki v techenie po krajnej mere 60 chasov</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; ot daty etogo soobshenija.&nbsp; Spasibo.</FONT>
</P>

<P><FONT SIZE=2>UWAGA: Prosimy nie publikowac rozwiazan, dodatkowych&nbsp; badz pomocniczych</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=2>informacjii przez co najmniej 60 godzin od daty tej wiadomosci.</FONT>
<BR>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <FONT SIZE=2>Dziekuje.</FONT>
</P>

<P><FONT SIZE=2>----------------------------------------------------------------</FONT>
</P>

<P><FONT SIZE=2>When computer scientists want to study what is computable, they need a model of computation that is simpler than real computers are.&nbsp; One</FONT></P>

<P><FONT SIZE=2>model they use is called a &quot;Turing Machine&quot;.&nbsp;&nbsp;&nbsp; A Turing Machine has</FONT>
<BR><FONT SIZE=2>three parts:</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp; 1.&nbsp; One state register which can hold a single number, called the</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; state; the state register has a maximum size specified in</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; advance.</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp; 2.&nbsp; An infinite tape of memory cells, each of which can hold a</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; single character, and a read-write head that examines a single</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; square at any given time.</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp; 3.&nbsp; A finite program, which is just a big table. For any possible</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; number N in the register, and any character in the</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; currently-scanned memory cell, the table says to do three</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; things: It has a number to put into the register, replacing</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; what was there before,; it has a new character to write into</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; the current memory cell, replacing what was there before, and</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; it has an instruction to the read-write head to move one space</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; left or one space right.</FONT>
</P>

<P><FONT SIZE=2>This may not seem like a very reasonable model of computation, but computer scientists have exhibited Turing machines that can do all the things you usually want computers to be able to do, such as performing arithmetic computations and running interpreter programs that simulate the behavior of other computers.</FONT></P>

<P><FONT SIZE=2>They've also showed that a lot of obvious `improvements' to the Turing machine model, such as adding more memory tapes, random-access memory, more read-write heads, more registers, or whatever, don't actually add any power at all; anything that could be computed by such an extended machine could also have been computed by the original machine, although perhaps more slowly.</FONT></P>

<P><FONT SIZE=2>Finally, a lot of other totally different models for computation turn out to be equivalent in power to the Turing machine model.&nbsp; Each of these models has some feature about it that suggests that it really does correspond well to our intuitive idea of what is computable.&nbsp; For example, the lambda calculus, a simple model of funbction construction and invocation, turns out to be able to compute everything that can be computed by Turing Machines, and nothing more.&nbsp; Random-access machines, which have a random-access addressible memory like an ordinary computer, also turn out to be able to compute everything that can be computed by Turing Machines, and nothing more.</FONT></P>

<P><FONT SIZE=2>So there is a lot of evidence that the Turing Machine, limited though is appears, actually does capture our intuitive notion of what it means for something to be computable.</FONT></P>

<P><FONT SIZE=2>For the Regular Quiz of the Week 24, we'll implement a Turing Machine.</FONT>
</P>

<P><FONT SIZE=2>Let's say that the tape will only hold Perl &quot;word&quot; characters, </FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; A-Z</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; a-z</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0-9</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; _</FONT>
</P>

<P><FONT SIZE=2>And let's also say that we can give symbolic names of the form /\w+/ to the values that can be stored in the state register.</FONT></P>

<P><FONT SIZE=2>Then a Turing Machine's program will be a list of instructions that look like this:</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; SomeState 1 OtherState 0 L</FONT>
</P>

<P><FONT SIZE=2>This means that if the Turing Machine's state register contains &quot;SomeState&quot;, and there's a 1 in the tape square under the read/write head, it should replace the 1 with a 0, move the read/write head to the left (by one space -- it can only move one space at a time), and store &quot;OtherState&quot; in the state register.</FONT></P>

<P><FONT SIZE=2>'#' will introduce comments, so this instruction is the same:</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; SomeState 1 OtherState 0 L&nbsp;&nbsp; # flip-flop</FONT>
</P>

<P><FONT SIZE=2>There is one of these state transition instructions per line.&nbsp; The five required elements in each instruction (old state, old tape symbol, new state, new tape symbol, and read/write head motion) are separated by one or more whitespace characters.</FONT></P>

<P><FONT SIZE=2>States' labels are made of word characters.</FONT>
</P>

<P><FONT SIZE=2>The current symbol and new symbol can be any word character (as specified in the definition of finite alphabet, above.)</FONT>
</P>

<P><FONT SIZE=2>Blank lines or lines consisting only of a comment are acceptable, and are ignored.</FONT>
</P>

<P><FONT SIZE=2>Your program should take two parameters: the filename of a file containing the state transition instructions, and the tape's initial</FONT></P>

<P><FONT SIZE=2>contents. The filename is required.&nbsp;&nbsp;&nbsp; </FONT>
</P>

<P><FONT SIZE=2>The tape is assumed to be filled with '_' characters forever in both directions on either side of the specified initial value, so an initial value argument of &quot;123_456abc&quot; really means &quot;...______123_456abc______...&quot;.&nbsp; If the initial tape argument is omitted, the tape is assumed to be full of &quot;_&quot; symbols.&nbsp; The &quot;_&quot;</FONT></P>

<P><FONT SIZE=2>symbols are called &quot;blanks&quot;.</FONT>
</P>

<P><FONT SIZE=2>If an initial value for the tape is specified, the read/write head begins over the first character of that initial value.&nbsp; In the example above, the read/write head is initially positioned over the &quot;1&quot;</FONT></P>

<P><FONT SIZE=2>symbol.&nbsp; If no tape is specified, then the read/write head begins over one of the blanks (which, conceptually, could be any location on the</FONT></P>

<P><FONT SIZE=2>tape.)</FONT>
</P>

<P><FONT SIZE=2>Please note that the read/write head _can_ move to the left of its initial position, as the tape extends an arbitrary length in both directions.</FONT></P>

<P><FONT SIZE=2>The Turing Machine's initial state is the first state mentioned in the state transition instructions (i.e. the current state defined on the first instruction line.)</FONT></P>

<P><FONT SIZE=2>If, for a given state and current symbol under the read/write head, the Turing Machine does not have any instructions specified in the state transition table, it halts, and your program should print out the tape from the first non-blank character to the last non-blank character, and exit.</FONT></P>

<P><FONT SIZE=2>Your program should die with an error message if it encounters a badly formatted line in the state transition instruction file.</FONT></P>

<P><FONT SIZE=2>EXAMPLES:</FONT>
</P>

<P><FONT SIZE=2>If binary_incr.tm contains:</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s0 1 s0 1 R&nbsp; # Seek right to the end of the numeral</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s0 0 s0 0 R</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s0 _ s1 _ L</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s1 1 s1 0 L&nbsp; # Scan left, changing 1s to 0's</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s1 0 s2 1 L&nbsp; # Until you find the rightmost 0</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s1 _ s2 1 L&nbsp; # or fall off the left end of the numeral</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s2 1 s2 1 L&nbsp; # Seek left to the left end of the numeral</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s2 0 s2 0 L</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s2 _ s3 _ R&nbsp; # ... and then stop</FONT>
</P>

<P><FONT SIZE=2>and your program is in tm.pl, then the output of</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; tm.pl binary_incr.tm 0011001</FONT>
</P>

<P><FONT SIZE=2>should be:</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 0011010</FONT>
</P>

<P><FONT SIZE=2>(This state transition table implements incrementing a binary string by 1.)</FONT>
</P>

<P><FONT SIZE=2>If helloworld.tm contains:</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s0 _ s1 h R</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s1 _ s2 e R</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s2 _ s3 l R</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s3 _ s4 1 R</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s4 _ s5 o R</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s5 _ s6 _ R</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s6 _ s7 w R</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s7 _ s8 o R</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s8 _ s9 r R</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s9 _ s10 l R</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; s10 _ s11 d R</FONT>
</P>

<P><FONT SIZE=2>then</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; tm.pl helloworld.tm</FONT>
</P>

<P><FONT SIZE=2>should output:</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; hello_world</FONT>
</P>

<P><FONT SIZE=2>if multiply.tm contains:</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; start 1 move1right W R&nbsp; # mark first bit of 1st argument</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; move1right 1 move1right 1 R&nbsp;&nbsp;&nbsp;&nbsp; # move right til past 1st argument</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; move1right _ mark2start _ R&nbsp;&nbsp;&nbsp;&nbsp; # square between 1st and 2nd arguments found</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; mark2start 1 move2right Y R&nbsp;&nbsp;&nbsp;&nbsp; # mark first bit of 2nd argument</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; move2right 1 move2right 1 R&nbsp;&nbsp;&nbsp;&nbsp; # move right til past 2nd argument</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; move2right _ initialize _ R&nbsp;&nbsp;&nbsp;&nbsp; # square between 2nd argument and answer found</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; initialize _ backup 1 L # put a 1 at start of answer</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; backup _ backup _ L&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # move back to leftmost unused bit of 1st arg</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; backup 1 backup 1 L&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # ditto</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; backup Z backup Z L&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # ditto</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; backup Y backup Y L&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # ditto</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; backup X nextpass X R&nbsp;&nbsp; # in position to start next pass</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; backup W nextpass W R&nbsp;&nbsp; # ditto</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; nextpass _ finishup _ R # if square is blank we're done. finish up</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; nextpass 1 findarg2 X R # if square is not blank go to work. mark bit</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; findarg2 1 findarg2 1 R # move past 1st argument</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; findarg2 _ findarg2 _ R # square between 1st and 2nd arguments</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; findarg2 Y testarg2 Y R # start of 2nd arg. skip this bit copy rest</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; testarg2 _ cleanup2 _ L # if blank we are done with this pass</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; testarg2 1 findans Z R&nbsp; # if not increment ans. mark bit move there</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; findans 1 findans 1 R&nbsp;&nbsp; # still in 2nd argument</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; findans _ atans _ R&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # square between 2nd argument and answer</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; atans 1 atans 1 R&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # move through answer</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; atans _ backarg2 1 L&nbsp;&nbsp;&nbsp; # at end of answer__write a 1 here go back</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; backarg2 1 backarg2 1 L&nbsp;&nbsp;&nbsp;&nbsp; # move left to first unused bit of 2nd arg</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; backarg2 _ backarg2 _ L&nbsp;&nbsp;&nbsp;&nbsp; # ditto</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; backarg2 Z testarg2 Z R&nbsp;&nbsp;&nbsp;&nbsp; # just past it. move right and test it</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; backarg2 Y testarg2 Y R&nbsp;&nbsp;&nbsp;&nbsp; # ditto</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cleanup2 1 cleanup2 1 L # move back through answer</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cleanup2 _ cleanup2 _ L # square between 2nd arg and answer</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cleanup2 Z cleanup2 1 L # restore bits of 2nd argument</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cleanup2 Y backup Y L&nbsp;&nbsp; # done with that. backup to start next pass</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; finishup Y finishup 1 L # restore first bit of 2nd argument</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; finishup _ finishup _ L # 2nd argument restored move back to 1st</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; finishup X finishup 1 L # restore bits of 1st argument</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; finishup W almostdone 1 L&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; # restore first bit of 1st arg. almost done</FONT>
<BR><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; almostdone _ halt _ R&nbsp;&nbsp; # done with work. position properly and halt </FONT>
</P>

<P><FONT SIZE=2>then </FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; tm.pl multiply.tm 1111_11111</FONT>
</P>

<P><FONT SIZE=2>should output:</FONT>
</P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 1111_11111_1111111111111</FONT>
</P>

<P><FONT SIZE=2>This program implements multiplication where a quantity n is represented by n+1 1's. So the example above passes it 3 and 4, and the program writes the result, 12, represented as 13 1's, to the end of the tape.</FONT></P>
<BR>

<P><FONT SIZE=2>REFERENCES</FONT>
</P>

<P><FONT SIZE=2>Turing Machines were first described by Alan Turing in his 1936 paper, &quot;On Computable Numbers, with an Application to the Entscheidungsproblem [decision-making problem]&quot;:</FONT></P>

<P><FONT SIZE=2>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <A HREF="http://www.abelard.org/turpap2/tp2-ie.asp" TARGET="_blank">http://www.abelard.org/turpap2/tp2-ie.asp</A></FONT>
</P>
<BR>

</BODY>
</HTML>