Information Technology Reference
In-Depth Information
More on Turing machines
Turing's super-typewriter
According to Andrew Hodges, as a boy, Turing dreamed of inventing ways of improving typewriters,
and this might have provided him with the starting point for his later ideas about computation. In any case,
the way that typewriters manipulate symbols serves as a good introduction to Turing machines. A typewriter
is mechanical in that its response to any action of the operator is built in. However, the specific response
will depend on whether it was set to type lowercase or uppercase letters; this is the configuration - or state -
of the machine. Turing machines generalize this idea to include a larger but still finite number of possible
states. A typewriter keyboard contains only a finite number of symbols - the letters of the alphabet and the
numbers 0 to 9, plus a few special symbols. Similarly, Turing assumed that his machine was only allowed a
finite number of possible operations. Together with the description of the allowed states, this allowed him
to write a complete description of the behavior of his machine. The other relevant feature of the typewriter
is that the typing point - the point where the typewriter's “head” strikes the paper - can move relative to
the page. Turing incorporated this feature - albeit with symbols written on a tape rather than on a page of
paper - into his idea for a primitive computing machine.
The typewriter analogy is limited in that a typewriter can only write symbols on a page when they
are selected by a human operator, who also decides when to change configuration and where to type the
symbol on the page. Turing wanted a much more general kind of machine to manipulate symbols. In addi-
tion to writing, Turing wanted his machine to be able to “scan” (that is, read) a symbol on the tape as well
as to write or erase a symbol. Such a “super-typewriter” would retain the property of a typewriter in having
a finite number of states and an exactly determined behavior for each operation. In addition, unlike in our
typewriter analogy, instead of human-operated machines, Turing was interested in investigating what he
called
automatic
machines, for which no human intervention would be necessary.
Turing machines in detail
Let us look in more detail at how we can define a Turing machine to do a particular job. We shall
label the various possible states of the machine by the symbol Q, and any particular state “i” as the state Q
i
.
Similarly, we will label the entries on the tape by the symbol S and a particular symbol “i” as the symbol
S
i
. When we start, only a finite part of the tape has any writing on it: either side of this region, the tape is
blank. We start the machine to the left of the writing on the tape at time T. It then proceeds to march along,
step-by-step, in uniform time steps, as if following the ticks of a clock. What the state of the machine and
the tape is at step T + 1 will then be determined by three functions, each of which will depend on the initial
state Q
i
at step T and the symbol Si
i
the head has just read. These three functions define what its new state,
Q
j
will be; what symbol, S
j
, it has written on the tape in the original box; and what was the direction, D, of
its subsequent motion after writing the new symbol. In mathematical notation, we can write this behavior
in terms of three functions - F, G, and D, each depending on the initial Qi
i
and S
i
:
Q
j
= F (Q
i
, S
i
)
S
j
= G (Q
i
, S
i
)
D
j
= D (Q
i
, S
i
)
Search WWH ::
Custom Search