We begin our study with a formal definition of a Turing machine, then
develop some feeling for what is involved by doing some simple programs. Next
we argue that, while the mechanism of a Turing machine is quite rudimentary,
the concept is broad enough to cover very complex processes. The discussion
culminates in the Turing thesis, which maintains that any computational
process, such as those carried out by present-day computers, can be done on a
Turing machine.
9.1 The Standard Turing Machine
Although we can envision a variety of automata with complex and sophisticated
storage devices, a Turing machine's storage is actually quite simple. It can be
visualized as a single, one-dimensional array of cells, each of which can hold a
single symbol. This array extends indefinitely in both directions and is therefore
capable of holding an unlimited amount of information. The information can be
read and changed in any order. We will call such a storage device a tape because
it is analogous to the magnetic tapes used in older computers.
Definition of a Turing Machine
A Turing machine is an automaton whose temporary storage is a tape. This tape
is divided into cells, each of which is capable of holding one symbol. Associated
with the tape is a read-write head that can travel right or left on the tape and
that can read and write a single symbol on each move. To deviate slightly from
the general scheme of Chapter 1, the automaton that we use as a Turing machine
will have neither an input file nor any special output mechanism. Whatever input
and output is necessary will be done on the machine's tape. We will see later that
this modification of our general model in Section 1.2 is of little consequence. We
could retain the input file and a specific output mechanism without affecting any
of the conclusions we are about to draw, but we leave them out because the
resulting automaton is a little easier to describe.
A diagram giving an intuitive visualization of a Turing machine is shown in
Figure 9.1. Definition 9.1 makes the notion precise.
Figure 9.1
develop some feeling for what is involved by doing some simple programs. Next
we argue that, while the mechanism of a Turing machine is quite rudimentary,
the concept is broad enough to cover very complex processes. The discussion
culminates in the Turing thesis, which maintains that any computational
process, such as those carried out by present-day computers, can be done on a
Turing machine.
9.1 The Standard Turing Machine
Although we can envision a variety of automata with complex and sophisticated
storage devices, a Turing machine's storage is actually quite simple. It can be
visualized as a single, one-dimensional array of cells, each of which can hold a
single symbol. This array extends indefinitely in both directions and is therefore
capable of holding an unlimited amount of information. The information can be
read and changed in any order. We will call such a storage device a tape because
it is analogous to the magnetic tapes used in older computers.
Definition of a Turing Machine
A Turing machine is an automaton whose temporary storage is a tape. This tape
is divided into cells, each of which is capable of holding one symbol. Associated
with the tape is a read-write head that can travel right or left on the tape and
that can read and write a single symbol on each move. To deviate slightly from
the general scheme of Chapter 1, the automaton that we use as a Turing machine
will have neither an input file nor any special output mechanism. Whatever input
and output is necessary will be done on the machine's tape. We will see later that
this modification of our general model in Section 1.2 is of little consequence. We
could retain the input file and a specific output mechanism without affecting any
of the conclusions we are about to draw, but we leave them out because the
resulting automaton is a little easier to describe.
A diagram giving an intuitive visualization of a Turing machine is shown in
Figure 9.1. Definition 9.1 makes the notion precise.
Figure 9.1