Information Technology Reference
In-Depth Information
Control
Unit
Figure 5.4
A three-tape Turing machine.
Figure 5.5
A single tape of a TM with a large tape alphabet that simulates a three-tape TM
with a smaller tape alphabet.
tape heads. If the
k
-tape TM executes
T
steps, it uses at most
T
+
1 tape cells. Thus each
pass requires
O
(
T
)
steps and the complete computation can be done in
O
(
T
2
)
steps.
Multi-tape machines in which the tapes are double-ended are equivalent to multi-tape
single-ended Turing machines, as the reader can show.
5.2.2 Nondeterministic Turing Machines
The
nondeterministic standard Turing machine
(NDTM) is introduced in Section
3.7.1
.
We use a slightly altered definition that conforms to the definition of the standard Turing
machine in Definition
5.1.1
.
DEFINITION
5.2.1
A
nondeterministic Turing machine (NDTM)
is a seven-tuple
M
=
(Σ
,
Γ
,
β
,
Q
,
δ
,
s
,
h
)
where
Σ
is the
choice input alphabet
,
Γ
is the
tape alphabet
not con-
taining the
blank symbol
β
,
Q
is the finite
set of states
,
δ
:
Q
×
Σ
×
(Γ
∪{
β
}
)
→
(
Q
∪{
h
}
)
×
(Γ
∪{
β
}∪{
L
,
R
}
)
∪{⊥}
is the
next-state function
,
s
is the
initial state
,
and
h
Q
is the
accepting halt state
. A TM cannot exit from
h
.If
M
is in state
q
with letter
a
under the tape head and
δ
(
q
,
c
,
a
)=(
q
,
C
)
, its control unit enters state
q
and writes
a
∈
if
Search WWH ::
Custom Search