Turing  -  Turing machine implementation

by Richard Taylor

What, in principle, may be computed by a computer? That which is
computable? But what is computable? Well, one answer could be that it is
anything that may be implemented by a Turing machine.

A Turing machine is a device which may move left and right along an infinite
tape of 0's and 1's altering the tape as it goes. The Turing machine also
has an internal state which may take any (finite) value. At every step it
alters the tape, changes its internal state and moves left or right or comes
to a stop, according the current internal state and the digit which it reads
from the tape.

For example the Turing machine may have been given the rule that if it is in
state 5 and reads a 1 on the tape then it should change to internal state 3,
replace the 1 on the tape with a 0, and move one step left. This rule can
be summarised as '5,1;3,0,L'. So the first two numbers of a rule, which
come before the semi-colon, represent the current internal state and the
value being read from the tape. The numbers that come after are the new
internal state to which it should change, the new value to be written on to
the tape and the direction in which to move after this has been done. Thus
'2,0;7,0,R' means that when the machine is in internal state 2 and reads a
0, it should change to state 7, leave the 0 on the tape and move right.
And if the machine were in state number 3 and reading a 1, the rule
'3,1;3,0,S' would require it to stay in state 3, replace the 1 with a 0, and
come to a stop.

Believe it or not, everything that is computable may be computed by a
suitable set of rules. The machine starts with its input data, in the form
of 1's and 0's on its right and comes to a stop with the output on its left.
This program allows the user to experiment with existing Turing machine
specifications and furthermore, to design new ones.

Double-click on the !Turing icon in the normal way and the application will
install itself on the icon bar. Click on this icon and the program
will open a window. At the top left of this window are the video-style
control icons. The first one ( - ) pauses the Turing machine, the second
one ( ] ) moves the Turing machine forward by one step, the third ( > )
starts it moving at the rate of around four steps per second while the
fourth ( >> ) moves it forward as fast as is possible. The current action
- pause, play, or fast-forward - is shown in the larger icon to the right.
Next to this is a 'rewind' icon which restarts the Turing machine with the
original tape (note it would be impossible to move back one step at a
time as there is often no way of telling from which internal state the
current state was entered - i.e. Turing machines are generally
non-reversible).

At the top right of the window there is an icon which keeps a count of the
total steps made from the start. The 'pane' window beneath this contains
the tape of 0's and 1's. If the tape is too large for the window then it
may be scrolled in the normal manner. The arrow, which starts above the
first digit of the tape, represents the current position of the Turing
machine. Finally, beneath this window, the current internal state and the
rule which is about to be applied are shown. However, when the program is
running in its fast-forward mode this icon and the step counter are not
updated to maximise the speed.

The program starts with a default Turing machine which simply adds one to a
'unary' number (a unary number is simply given by a string of 1's
in between the zeros on the tape - for example, five is written as
'...00011111000...'). Try repeatedly clicking on the 'one step forward'
icon ( ] ) to see it in action.

You may wish to load up the specification file for this machine which
contains all the rules - double-click on the !Turing icon whilst holding
down Shift to open the application directory and load the text file
Default into Edit. Having all the rules in view makes it somewhat easier
to follow what is going on, especially later on with more complex machines.

There are a number of specification files for such machines inside the
directory Examples within the !Turing application directory you have just
opened. They contain simple remarks which explain their action. To
make the machines act on different numbers simply alter the line near the
end of the file, beneath the word Tape, which contains the 1's and 0's
which are to be on the tape at the beginning. Remember to include enough
0's on the left and the right to ensure the machine does not move off the
edge and that it has enough space to record the 'answer'.

Note that most of the given machines act on 'unary' numbers (explained
above). This is obviously a most inefficient (though easy to understand)
way of representing numbers. So a few files have been included describing
machines which act on numbers given in an expanded binary notation (see
explanation below).

It is very easy to design and run your own Turing machines - just follow the
format of the example files. Any line that begins Rem is ignored so you
may write remarks as in Basic (case is unimportant for keywords - you may
write 'REM' or 'rem' or even 'rEm'). The first line (ignoring any 'Rem's)
should just consist of the word Turing identifying the text file as a
Turing machine specification. This is followed by all the rules, as
explained previously, that the machine is to use. Then comes the tape
description, as mentioned above, and finally the word End follows to
terminate the file.

While a theoretical Turing machine has an infinite tape and any number of
internal states, in actual fact the program imposes a maximum tape length of
1024 and allows up to 256 internal states (0 - 255). This should not be a
problem - it would be a very complicated machine that needed more. Note
also, that if a file is loaded without a tape description then the current
tape is used as the input, so one Turing machine may use the output of
another. Further, files may be exported directly from Edit into the
application which is very useful when experimenting.

Readers who are interested in learning more about Turing machines are
referred to Roger Penrose's book (see reference) where he discusses them in
greater detail together with their mathematical and philosophical
significance. He gives the specifications for the Turing machines I have
called BinDouble, BinPlusOne, Default, Double and Euclids. The book also
explains the halting problem - that it is not possible in general to decide
whether a given Turing machine will stop. Furthermore, he describes the
idea of a universal Turing machine that is able to emulate any other Turing
machine - today's computers may be considered, in some respects, as such
universal machines.

N.B It was mentioned earlier that more efficient Turing machines could use an
expanded binary coding of numbers on the tape (the input could not be
written in ordinary binary for there is no way of separating or terminating
these numbers). The expanded binary notation is read by looking at the
number of 1's in between successive 0's on the tape. If there are none,
this should be interpreted as a zero; if there is one, this translates as a
one; if there are two this represents a terminator (say a comma or full
stop). For example ...000010100011000... represents the normal binary
number 1100 or 12 in decimal. So ordinary binary numbers are easily
translated into this form - leave a 0 as a 0, replace a 1 by 10 and write
commas as 110.

Reference
The Emperor's New Mind, by Roger Penrose (1989), Oxford University Press.


Copyright  RISC User 1994
