Chap ter 4
Turing Machines
4.1 TURING MACHINE MODEL
4.1.1 What is a Turing Machine?
A Turing Machine is like a Pushdown Automaton. Both have a finite-state
machine as a central component, both have additional storage.
A Pushdown Automaton uses a “stack” for storage whereas a Turing
Machine usea a “tape”, which is actually infinite in both the directions. The
tape consists of a series of “squares”, each of which can hold a single symbol.
The “tape-head”, or “read-write head”, can read a symbol from the tape, write
a symbol to the tape and move one square in either direction.
There are two kinds of Turing Machine available.
(a) Deterministic Turing Machine.
(b) Non-deterministic Turing Machine.
We will discuss about Deterministic Machines only. A Turing Machine
does not read “input”, unlike the other automata. Instead, there are usually
symbols on the tape before the Turing Machine begins, the Turing Machine
might read some. all, or none of these symbols. The initial tape may, if desired,
be thought of as “input”.
“Acceptors” produce only a binary (accept/reject) output. “Transducers”
can produce more complicated results. So far all our previous discussions were
only with acceptors. A Turing Machine also accepts or rejects its input. The
results left on the tape when the Turing Machine finshes can be regarded as the
“output” of the computation. Therefore a Turing Machine is a “Transducer”.
4.1.2 Def i ni tion of Turing Machines
A Turing Machine M is a 7-tuple
( , , , , , # , )
Q
q
F
Σ Γ δ 0
where Q is a set of states
Σ is a finite set of symbols, “input alphabet”.
Γ is a finite set of symbols, “tape alphabet”.
δ is the partial transition function
Turing Machines
4.1 TURING MACHINE MODEL
4.1.1 What is a Turing Machine?
A Turing Machine is like a Pushdown Automaton. Both have a finite-state
machine as a central component, both have additional storage.
A Pushdown Automaton uses a “stack” for storage whereas a Turing
Machine usea a “tape”, which is actually infinite in both the directions. The
tape consists of a series of “squares”, each of which can hold a single symbol.
The “tape-head”, or “read-write head”, can read a symbol from the tape, write
a symbol to the tape and move one square in either direction.
There are two kinds of Turing Machine available.
(a) Deterministic Turing Machine.
(b) Non-deterministic Turing Machine.
We will discuss about Deterministic Machines only. A Turing Machine
does not read “input”, unlike the other automata. Instead, there are usually
symbols on the tape before the Turing Machine begins, the Turing Machine
might read some. all, or none of these symbols. The initial tape may, if desired,
be thought of as “input”.
“Acceptors” produce only a binary (accept/reject) output. “Transducers”
can produce more complicated results. So far all our previous discussions were
only with acceptors. A Turing Machine also accepts or rejects its input. The
results left on the tape when the Turing Machine finshes can be regarded as the
“output” of the computation. Therefore a Turing Machine is a “Transducer”.
4.1.2 Def i ni tion of Turing Machines
A Turing Machine M is a 7-tuple
( , , , , , # , )
Q
q
F
Σ Γ δ 0
where Q is a set of states
Σ is a finite set of symbols, “input alphabet”.
Γ is a finite set of symbols, “tape alphabet”.
δ is the partial transition function