[Kc] Perl Quiz of the Week #24 (Turing Machine simulation)
Garrett Goebel
garrett at scriptpro.com
Wed Sep 15 13:47:55 CDT 2004
From: mjd at plover.com [mailto:mjd at plover.com] On Behalf Of Zed Lopez
Sent: Wednesday, September 15, 2004 9:01 AM
To: perl-qotw at plover.com
Subject: [Retrieved]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 Lsungen, Tipps oder Hinweise fr
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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.pm.org/pipermail/kc/attachments/20040915/e14f31d4/attachment-0001.htm
More information about the kc
mailing list