Turing machine





The Turing machine is an abstract model of computer execution and storage
introduced in 1936 by Alan Turing to give a mathematically precise
definition of algorithm or 'mechanical procedure'. As such it is still
widely used in theoretical computer science, especially in complexity theory
and the theory of computation. The thesis that states that Turing machines
indeed capture the informal notion of effective or mechanical method in
logic and mathematics is known as the Church-Turing thesis.

Turing machines shouldn't be confused with the Turing test, Turing's attempt
to capture the notion of artificial intelligence.

A Turing machine that is able to simulate any other Turing machine is called
a universal Turing machine.

Definition

Briefly, a Turing machine is a pushdown automaton made more powerful by
relaxing the last-in-first-out requirement of its stack. (Interestingly, a
seemingly minor relaxation enables the Turing machine to perform such a wide
variety of computations that it can serve as a model for the computational
capabilities of all modern computer software.)

More precisely, a Turing machine consists of:

  1. A tape which is divided into cells, one next to the other. Each cell
     contains a symbol from some finite alphabet. The alphabet contains a
     special blank symbol (here written as '0') and one or more other
     symbols. The tape is assumed to be arbitrarily extendible to the left
     and to the right, i.e., the Turing machine is always supplied with as
     much tape as it needs for its computation. Cells that have not been
     written to before are assumed to be filled with the blank symbol.
  2. A head that can read and write symbols on the tape and move left and
     right.
  3. A state register that stores the state of the Turing machine. The
     number of different states is always finite and there is one special
     start state with which the state register is initialized.
  4. An action table that tells the machine what symbol to write, how to
     move the head ('L' for one step left, and 'R' for one step right) and
     what its new state will be, given the symbol it has just read on the
     tape and the state it is currently in. If there is no entry in the
     table for the current combination of symbol and state then the machine
     will halt.

Note that every part of the machine is finite, but it is the potentially
unlimited amount of tape that gives it an unbounded amount of storage space.

Example

The following Turing machine has an alphabet {'0', '1'}, with 0 being the
blank symbol. It expects a series of 1's on the tape, with the head
initially on the leftmost 1, and doubles the 1's with a 0 in between, i.e.,
"111" becomes "1110111". The set of states is {s1, s2, s3, s4, s5} and the
start state is s1. The action table is as follows.

  Old Read   Wr.      New     Old Read   Wr.      New
  St. Sym.   Sym. Mv. St.     St. Sym.   Sym. Mv. St.
  - - - - - - - - - - - -     - - - - - - - - - - - -
   s1  1  ->  0    R   s2      s4  1  ->  1    L   s4
   s2  1  ->  1    R   s2      s4  0  ->  0    L   s5
   s2  0  ->  0    R   s3      s5  1  ->  1    L   s5
   s3  0  ->  1    L   s4      s5  0  ->  1    R   s1
   s3  1  ->  1    R   s3

A computation of this Turing machine might for example be: (the position of
the head is indicated by displaying the cell in bold face)

  Step State Tape   Step State Tape
  - - - - - - - -   - - - - - - - - -
     1  s1   11        9  s2   1001
     2  s2   01       10  s3   1001
     3  s2   010      11  s3   10010
     4  s3   0100     12  s4   10011
     5  s4   0101     13  s4   10011
     6  s5   0101     14  s5   10011
     7  s5   0101     15  s1   11011
     8  s1   1101       -- halt --

The behavior of this machine can be described as a loop: it starts out in
s1, replaces the first 1 with a 0, then uses s2 to move to the right,
skipping over 1's and the first 0 encountered. S3 then skips over the next
sequence of 1's (initially there are none) and replaces the first 0 it finds
with a 1. S4 moves back to the left, skipping over 1's until it finds a 0
and switches to s5. s5 then moves to the left, skipping over 1's until it
finds the 0 that was originally written by s1. It replaces that 0 with a 1,
moves one position to the right and enters s1 again for another round of the
loop. This continues until s1 finds a 0 (this is the 0 right in the middle
between the two strings of 1's) at which time the machine halts.

The Universal Turing Machine

Every Turing machine computes a certain fixed partial function from the
input strings over its alphabet. In that sense it behaves like a computer
with a fixed program. However, as Alan Turing already described, we can
encode the action table of any Turing machine in a string. Thus we might try
to construct a Turing machine that expects on its tape a string describing
an action table followed by a string describing the input tape, and then
computes the tape that the encoded Turing machine would have computed. As
Turing showed, such a Turing machine is indeed possible and since it is able
to simulate any other Turing machine it is called a universal Turing machine.

With this encoding of action tables as strings, it becomes possible in
principle for Turing machines to answer questions about the behavior of
other Turing machines. Most of these questions, however, are undecidable.
For instance, the problem of determining whether a particular Turing machine
will halt on a particular input, or on all inputs, known as the Halting
problem, was already shown to be undecidable in Turing's original paper.
Rice's theorem shows that any nontrivial question about the behavior or
output of a Turing machine is undecidable.

If we broaden the definition to include any Turing machine that simulates
some Turing-complete computational model, not just Turing machines that
directly simulate other Turing machines, a universal Turing machine can be
fairly simple, using just a few states and a few symbols. For example, only
2 states are needed, since a 2×18 (meaning 2 states, 18 symbols)
universal Turing machine is known. A complete list of the smallest known
universal Turing machines is: 2×18, 3×10, 4×6, 5×5,
7×4, 10×3, 22×2. These simulate a computational model
called tag systems.

A universal Turing machine is Turing-complete. It can calculate any
recursive function, decide any recursive language, and accept any
recursively enumerable language. According to the Church-Turing thesis, the
problems solvable by a universal Turing machine are exactly those problems
solvable by an algorithm or an effective method of computation, for any
reasonable definition of those terms.

A Physical Turing Machine

It is not difficult to simulate a Turing Machine on a modern computer
(except for the limited memory of actually existing computers).

It is also possible to build a Turing Machine on a purely mechanical basis.
The mathematician Karl Scherer has indeed built such a machine in 1986 using
metal and plastic construction sets, and some wood. The 1.5 meter high
machine uses the pulling of strings to read, move and write the data (which
is represented using ball bearing balls).

The machine is now exhibited in the entrance of the Department of Computer
Science of the University of Heidelberg, Germany.