[Neworleans-pm] Fwd: Perl Quiz of the Week #24 (Turing Machine
simulation)
E. Strade, B.D.
estrabd at yahoo.com
Thu Sep 16 13:08:56 CDT 2004
=====
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
More information about the NewOrleans-pm
mailing list