Computability - Models of Computation: Exploring the Power of Computing - page 217

Input Tape
Work Tape
Control
Unit
Oracle Tape
Output Tape
Figure 5.8 The oracle Turing machine has an “oracle tape” on which it writes a string (a problem
instance), after which an “oracle” returns an answer in one step.
the oracle as many times as it wishes. Time on an OTM is the number of steps taken, where
one consultation of the oracle is counted as one step. Space is the number of cells used on
the work tapes of an OTM not including the oracle tape. The OTM machine can be used to
classify problems. (See Problem 8.15 .)
5.2.4 Representing Restricted Models of Computation
Now that we have introduced a variety of Turing machine models, we ask how the finite-state
machine and pushdown automaton fit into the picture.
The finite-state machine can be viewed as a Turing machine with two tapes, the first a
read-only input tape and the second a write-only output tape. This TM reads consecutive
symbols on its input tape, moving right after reading each symbol, and writes outputs on its
output tape, moving right after writing each symbol. If this TM enters an accepting halt state,
the input sequence read from the tape is accepted.
The pushdown automaton can be viewed as a Turing machine with two tapes, a read-only
input tape and a pushdown tape. The pushdown tape is a standard tape that pushes a new
symbol by moving its head right one cell and writing the new symbol into this previously
blank cell. It pops the symbol at the top of the stack by copying the symbol, after which it
replaces it with the blank symbol and moves its head left one cell.
The Turing machine can be simulated by two pushdown tapes. The movement of the head
in one direction can be simulated by popping the top item of one stack and pushing it onto
the other stack. To simulate the movement of the head in the opposite direction, interchange
the names of the two stacks.
The nondeterministic equivalents of the finite-state machine and pushdown automaton
are obtained by making their Turing machine control units nondeterministic.