I
Chapter 9
Turing
Machines
n our discussion so far we have encountered some fundamental ideas, in
particular the concepts of regular and context-free languages and their
association with finite automata and pushdown accepters. Our study has
revealed that the regular languages form a proper subset of the contextfree languages and, therefore, that pushdown automata are more powerful
than finite automata. We also saw that context-free languages, while
fundamental to the study of programming languages, are limited in scope. This
was made clear in the last chapter, where our results showed that some simple
languages, such as {a n b n c n }and {ww}, are not context-free. This prompts us to
look beyond context-free languages and investigate howone might define
newlanguage families that include these examples. To do so, we return to the
general picture of an automaton. If we compare finite automata with pushdown
automata, we see that the nature of the temporary storage creates the difference
between them. If there is no storage, we have a finite automaton; if the storage is
a stack, we have the more powerful pushdown automaton. Extrapolating from
this observation, we can expect to discover even more powerful language
families if we give the automaton more flexible storage. For example, what
would happen if, in the general scheme of Figure 1.3, we used two stacks, three
stacks, a queue, or some other storage device? Does each storage device define a
newkind of automaton and through it a newlanguage family? This approach
raises a large number of questions, most of which turn out to be uninteresting. It
is more instructive to ask a more ambitious question and consider howfar the
concept of an automaton can be pushed. What can we say about the most
powerful of automata and the limits of computation? This leads to the
fundamental concept of a Turing machine and, in turn, to a precise definition of
the idea of a mechanical or algorithmic computation.
Chapter 9
Turing
Machines
n our discussion so far we have encountered some fundamental ideas, in
particular the concepts of regular and context-free languages and their
association with finite automata and pushdown accepters. Our study has
revealed that the regular languages form a proper subset of the contextfree languages and, therefore, that pushdown automata are more powerful
than finite automata. We also saw that context-free languages, while
fundamental to the study of programming languages, are limited in scope. This
was made clear in the last chapter, where our results showed that some simple
languages, such as {a n b n c n }and {ww}, are not context-free. This prompts us to
look beyond context-free languages and investigate howone might define
newlanguage families that include these examples. To do so, we return to the
general picture of an automaton. If we compare finite automata with pushdown
automata, we see that the nature of the temporary storage creates the difference
between them. If there is no storage, we have a finite automaton; if the storage is
a stack, we have the more powerful pushdown automaton. Extrapolating from
this observation, we can expect to discover even more powerful language
families if we give the automaton more flexible storage. For example, what
would happen if, in the general scheme of Figure 1.3, we used two stacks, three
stacks, a queue, or some other storage device? Does each storage device define a
newkind of automaton and through it a newlanguage family? This approach
raises a large number of questions, most of which turn out to be uninteresting. It
is more instructive to ask a more ambitious question and consider howfar the
concept of an automaton can be pushed. What can we say about the most
powerful of automata and the limits of computation? This leads to the
fundamental concept of a Turing machine and, in turn, to a precise definition of
the idea of a mechanical or algorithmic computation.