[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.

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.


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

    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

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

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, 


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

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

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.


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:


(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


        tm.pl helloworld.tm

should output:


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
        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
        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
        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


        tm.pl multiply.tm 1111_11111

should output:


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.


Turing Machines were first described by Alan Turing in his 1936 paper, "On
Computable Numbers, with an Application to the Entscheidungsproblem
[decision-making problem]":


-------------- 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