Information Technology Reference
In-Depth Information
instances of a , b ,or c , it terminates in the accepting halt state h .Ifnot,thenitmovesright
over pseudo-blanks until it finds an a , entering state f if it finds some other letter. It then
resumes the process executed on the first pass by invoking C ( a , b ) . This computation either
enters the non-accepting halt state f or on each pass it replaces one instance each of a , b ,and
c with a pseudo-blank. Thus, M accepts the language L =
a n b n c n
;thatis, L
is decidable (recursive). Since M makes one pass over the tape for each instance of a ,ituses
time O ( n 2 ) on a string of length n . Later we give examples of languages that are recursively
enumerable but not recursive.
In Section 3.8 we reasoned that any RAM computation can be simulated by a Turing
machine. We showed that any program written for the RAM can be executed on a Turing
machine at the expense of an increase in the running time from T steps on a RAM with S bits
of storage to a time O ( ST log 2 S ) on the Turing machine.
{
|
n
}
1
5.2 Extensions to the Standard Turing Machine Model
In this section we examine various extensions to the standard Turing machine model and
establish their equivalence to the standard model. These extensions include the multi-tape,
nondeterministic, and oracle Turing machines.
We first consider the double-ended tape Turing machine . Unlike the standard TM that
has a tape bounded on one end, this is a TM whose single tape is double-ended. A TM of this
kind can be simulated by a two-track one-tape TM by reading and writing data on the top
track when working on cells to the right of the midpoint of the tape and reading and writing
data on the bottom track when working with cells to its left. (See Problem 5.7 .)
5.2.1 Multi-Tape Turing Machines
A k -tape Turing machine has a control unit and k single-ended tapes of the kind shown in
Fig. 5.1 . Each tape has its own head and operates in the fashion indicated for the standard
model. The FSM control unit accepts inputs from all tapes simultaneously, makes a state
transition based on this data, and then supplies outputs to each tape in the form of either a
letter to be written under its head or a head movement command. We assume that the tape
alphabet of each tape is Γ . A three-tape TM is shown in Fig. 5.4 .A k -tape TM M k can be
simulated by a one-tape TM M 1 , as we now show.
THEOREM 5.2.1 For each k -tape Turing machine M k there is a one-tape Turing machine M 1
such that a terminating T -step computation by M k can be simulated in O ( T 2 ) steps by M 1 .
Proof Let Γ and Γ be the tape alphabets of M k and M 1 , respectively. Let
) k
so that Γ has enough letters to allow the tape of M 1 to be subdivided into k tracks, as
suggested in Fig. 5.5 . Each cell of a track contains 2
Γ |
|
=( 2
|
Γ
|
letters, a number large enough to
allow each cell to contain either a member of Γ or a marked member of Γ .Themarked
members retain their original identity but also contain the information that they have been
marked. As suggested in Fig. 5.5 for a three-tape TM, k heads can be simulated by one head
by marking the positions of the k heads on the tracks of M 1 .
M 1 simulates M k in two passes. First it visits marked cells to collect the letters under
the original tape heads, after which it makes a state transition akin to that made by M k .Ina
second pass it visits the marked cells either to change their entries or to move the simulated
|
Γ
|
Search WWH ::




Custom Search