[Neworleans-pm] Fwd: Perl Quiz of the Week #24 (Turing Machine
simulation)
shrek
shr3kst3r at gmail.com
Thu Sep 16 14:04:30 CDT 2004
I found this one to be alot of fun.
http://www.engrowe.com/code/perl/qotw/qotw_regular_24.pl
On Thu, 16 Sep 2004 13:08:56 -0500, E. Strade, B.D. <estrabd at yahoo.com> wrote:
>
>
> =====
> http://www.brettsbsd.net/~estrabd
>
> __________________________________
> Do you Yahoo!?
> Yahoo! SiteBuilder - Free, easy-to-use web site design software
> http://sitebuilder.yahoo.com
>
>
>
> ----- Original message -----
> From: "Zed Lopez" <zed at apricot.com>
> To: perl-qotw at plover.com
> Date: Wed, 15 Sep 2004 10:01:18 -0400
> Subject: Perl Quiz of the Week #24 (Turing Machine simulation)
>
> 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
>
>
> _______________________________________________
> NewOrleans-pm mailing list
> NewOrleans-pm at mail.pm.org
> http://mail.pm.org/mailman/listinfo/neworleans-pm
>
--
"I don't care what everyone likes. Ogres are not like
cakes... You dunce, irritating, miniature beast of
burden. Ogres are like onions. End of story.
Bye bye. See ya later..." -- Shrek
More information about the NewOrleans-pm
mailing list