4
4.1 One-Tape Turing Machines
In the previous chapters, we have studied two types of computational models:
finite automata and pushdown automata. A finite automaton is an abstract
machine having a finite control but no run-time memory. The class of lan-
guages recognized by finite automata is characterized exactly as regular lan-
guages. A pushdown automaton also has a finite control and has, in addition,
a single pushdown stack as the run-time memory, whose size may grow at
the run time. The class of languages recognized by pushdown automata is
characterized as context-free languages. It is clear that these machines are of
limited computational power, compared with our real digital computers. For
instance, the language {unbncn ] n > - 0) is not a context-free language but
can be easily recognized by a short program in the real computers.
In this chapter, we introduce a new machine model, called the Turing
machine, which has a finite control plus a tape as the run-time memory, whose
size is unlimited. Furthermore, the tape head of the machine is allowed to
move around the tape to read and write symbols, and so it behaves similarly
to a real computer. Indeed, one of the main results of this chapter is to show
that the computational power of Turing machines is the same as that of many
other well-studied computational models.
There are many variations of Turing machines. We start with the simplest
kind, the one-tape deterministic Turing machine. A one-tape deterministic
Turing machine (also called one-tape RTM, DTM or, simply, TM), similar
to a DFA, consists of three parts: a tape, a tape head, and a finite control
159
Problem Solving in Automata, Languages, and Complexity.
Ding-Zhu Du, Ker-I Ko
Copyright2001 by John Wiley & Sons, Inc.
ISBNs: 0-471-43960-6 (Hardback); 0-471-22464-2 (Electronic)