[an error occurred while processing this directive]
[an error occurred while processing this directive]
Turing Machines
COMP 200
Elements of Computer Science
Fall 2009
Turing Machines
What is a computer?
What can a computer do? What can a computer not do?
What does it mean to compute something?
What does it mean for something to be NOT computable?
Alan Turing invented an abstract machine called Turing Machine to formalize
the intuitive notion of a computation in an attempt to answer the above
questions. A Turing machine can be rigorously defined in terms of
mathematical concepts. However, for the sake of simplicity, we will
discuss Turing machine in more concrete terms.
A Turing machine can be viewed as a device with the following features.
An input tape consisting of individual cells, each of which can contain
a symbol or a blank. The input tape extends infinitely on both ends.
A read/write head that can read a symbol or blank from the input tape
cell or write a symbol or blank to the input tape cell. The read/write
head can move one cell at a time in each direction on the input tape.
The set of input/output symbols is finite.
A finite set of internal configurations called states. There is
one (one and only one) special state called the start state. There is also a (finite) set
of states called final states. When the Turing machine is in its final
state, it does not read, write nor move. Basically, it stops running.
The machine moves the read/write head and changes its internal state
according to a finite set of rules called the state transition rules.
The state transition rule has the form: (current state, current input
symbol, next state, next output symbol, direction of head movement).
For example, (q2, "a", q5, "x", left) means if the machine is in state q2
and the read head sees the symbol "a", then change to state q5, overwrite
the current symbol "a" with the symbol "x" and move left one cell.
When there is no transition rule available for the current state and the
current input symbol, the Turing machine "hangs," that is it breaks down and
can no longer continue.
Here is a schematic view of the Turing machine.
A Typical Turing Machine
1
a
b
0
a
Input/Output Tape
read/write head
State Transition Rules
State
current state
current symbol
next state
next symbol
direction
q0
start state
q0
a
q5
a
left
q1
q0
q1
b
right
q2
current state
q1
a
q2
a
q3
q1
b
q3
left
q4
q1
q4
q5
q2
a
q5
b
right
q6
q2
b
q6
0
right
…
final states
q2
q6
1
right
…
q3
1
q9
a
left
q15
etc..
…
…
qn
To see how such device can do any computation, it is best to look at an
example.
