## Turing Machines

In the 1930's (before the advent of the
digital computer) several mathematicians began to think about what it means to
be able to compute a function. Alonzo Church and Alan Turing independently
arrived at equivalent conclusions. As we might phrase their common definition
now:
*A function is computable if it can be computed by a Turing machine.*

A Turing machine is a very simple machine, but, logically speaking, has all
the power of any digital computer. It may be described as follows: A Turing
machine processes an infinite tape. This tape is divided into squares, any
square of which may contain a symbol from a finite alphabet, with the
restriction that there can be only finitely many non-blank squares on the tape.
At any time, the Turing machine has a read/write head positioned at some square
on the tape. Furthermore, at any time, the Turing machine is in any one of a
finite number of internal states. The Turing machine is further specified by a
set of instructions of the following form:

*(current_state, current_symbol, new_state, new_symbol,
left/right)*

This instruction means that if the Turing machine is now in *current_state*,
and the symbol under the read/write head is *current_symbol*, change its
internal state to *new_state*, replace the symbol on the tape at its
current position by *new_symbol*, and move the read/write head one square
in the given direction (*left* or *right*). If a Turing machine is
in a condition for which it has no instruction, it halts.
Nowadays it is natural to think of the set of instructions as a program for
the Turing machine.

There are several conventions commonly used in Turing machines (and several
slightly different, though of course logically equivalent, definitions of them).
We adopt the convention that numbers are represented in unary notation, i.e.,
that the non-negative integer *n* is represented by a string of *n+1*
successive*1*s. Furthermore, if we want to compute a function *f(n*_{1},n_{2},
... ,n_{k}), we assume that initially the tape consists of *n*_{1},
n_{2}, ... , n_{k}, properly encoded, with each separated
from the previous one by a single blank, and with the tape head initially poised
over the left-most bit of the first argument, and the state of the Turing
machine some initial specified value. We say that the Turing machine has
computed *m = f(n*_{1},n_{2},,,,n_{k}) if, when
the machine halts, the tape consists of *n*_{1}, n_{2}, ... ,
n_{k}, m, properly encoded, and separated by single blanks, and the
read/write head back at the left-most bit of the first argument.

For example, suppose we wish to create a Turing machine to compute the
function

*m = multiply(n*_{1},n_{2}) = n_{1} * n_{2}

Suppose the input tape reads

_<1>1 1 1 _ 1 1 1 1 1 _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _

which encodes 3 and 4 respectively, in unary notation. (Here the position of the
read/write head is marked.) Then the Turing machine should halt with its tape
reading
_<1>1 1 1 _ 1 1 1 1 1 _ 1 1 1 1 1 1 1 1 1 1 1 1 1 _ _ _ _ _

which encodes 3, 4, and 12 in unary notation.
If you want to know more about these machines. you can mail me.

[Home]