IMPORTANT: Please do not post solutions, hints, or other spoilers until at least 60 hours after the date of this message. Thanks. WICHTIG: Bitte schicken Sie keine Lösungen, Tipps oder Hinweise für diese Aufgabe vor Ablauf von 60 Stunden nach dem Datum dieser Mail. Danke. BELANGRIJK: Stuur aub geen oplossingen, hints of andere tips in de eerste 60 uur na het verzendingstijdstip van dit bericht. Waarvoor dank. VNIMANIE: Pozhalujsta ne shlite reshenija, nameki na reshenija, i voobshe lyubye podskazki v techenie po krajnej mere 60 chasov ot daty etogo soobshenija. Spasibo. UWAGA: Prosimy nie publikowac rozwiazan, dodatkowych badz pomocniczych informacjii przez co najmniej 60 godzin od daty tej wiadomosci. Dziekuje. ---------------------------------------------------------------- When computer scientists want to study what is computable, they need a model of computation that is simpler than real computers are. One model they use is called a "Turing Machine". A Turing Machine has three parts: 1. One state register which can hold a single number, called the state; the state register has a maximum size specified in advance. 2. An infinite tape of memory cells, each of which can hold a single character, and a read-write head that examines a single square at any given time. 3. A finite program, which is just a big table. For any possible number N in the register, and any character in the currently-scanned memory cell, the table says to do three things: It has a number to put into the register, replacing what was there before,; it has a new character to write into the current memory cell, replacing what was there before, and it has an instruction to the read-write head to move one space left or one space right. 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. 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. Finally, a lot of other totally different models for computation turn out to be equivalent in power to the Turing machine model. 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. 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. 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. 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. For the Regular Quiz of the Week 24, we'll implement a Turing Machine. Let's say that the tape will only hold Perl "word" characters, A-Z a-z 0-9 _ 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. Then a Turing Machine's program will be a list of instructions that look like this: SomeState 1 OtherState 0 L This means that if the Turing Machine's state register contains "SomeState", 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 "OtherState" in the state register. '#' will introduce comments, so this instruction is the same: SomeState 1 OtherState 0 L # flip-flop There is one of these state transition instructions per line. 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. States' labels are made of word characters. The current symbol and new symbol can be any word character (as specified in the definition of finite alphabet, above.) Blank lines or lines consisting only of a comment are acceptable, and are ignored. Your program should take two parameters: the filename of a file containing the state transition instructions, and the tape's initial contents. The filename is required. 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 "123_456abc" really means "...______123_456abc______...". If the initial tape argument is omitted, the tape is assumed to be full of "_" symbols. The "_" symbols are called "blanks". If an initial value for the tape is specified, the read/write head begins over the first character of that initial value. In the example above, the read/write head is initially positioned over the "1" symbol. If no tape is specified, then the read/write head begins over one of the blanks (which, conceptually, could be any location on the tape.) 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. 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.) 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. Your program should die with an error message if it encounters a badly formatted line in the state transition instruction file. EXAMPLES: If binary_incr.tm contains: s0 1 s0 1 R # Seek right to the end of the numeral s0 0 s0 0 R s0 _ s1 _ L s1 1 s1 0 L # Scan left, changing 1s to 0's s1 0 s2 1 L # Until you find the rightmost 0 s1 _ s2 1 L # or fall off the left end of the numeral s2 1 s2 1 L # Seek left to the left end of the numeral s2 0 s2 0 L s2 _ s3 _ R # ... and then stop and your program is in tm.pl, then the output of tm.pl binary_incr.tm 0011001 should be: 0011010 (This state transition table implements incrementing a binary string by 1.) If helloworld.tm contains: s0 _ s1 h R s1 _ s2 e R s2 _ s3 l R s3 _ s4 1 R s4 _ s5 o R s5 _ s6 _ R s6 _ s7 w R s7 _ s8 o R s8 _ s9 r R s9 _ s10 l R s10 _ s11 d R then tm.pl helloworld.tm should output: hello_world if multiply.tm contains: 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 then tm.pl multiply.tm 1111_11111 should output: 1111_11111_1111111111111 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. REFERENCES Turing Machines were first described by Alan Turing in his 1936 paper, "On Computable Numbers, with an Application to the Entscheidungsproblem [decision-making problem]": http://www.abelard.org/turpap2/tp2-ie.asp