Information Technology Reference
In-Depth Information
(It is shown schematically in Fig.
3.22
.) At each unit of time the control unit accepts input
from the tape unit and supplies output to it. The tape unit produces the value in the cell
under the head, a
b
-bit word, and accepts and writes a
b
-bit word to that cell. It also accepts
commands to move the head one cell to the left or right or not at all. The bounded-memory
tape unit is an array of
mb
-bit cells and has a
storage capacity
of
S
=
mb
bits. A formal
definition of the one-tape deterministic Turing machine is given below.
DEFINITION
3.7.1
A
standard Turing machine (TM)
is a six-tuple
M
=(Γ
,
β
,
Q
,
δ
,
s
,
h
)
,
where
Γ
is the
tape alphabet
not containing the
blank symbol
β
,
Q
is the finite
setofstates
,
δ
:
Q
×
(Γ
∪{
β
}
)
→
(
Q
∪{
h
}
)
×
(Γ
∪{
β
}
)
×{
L
,
N
,
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
,
a
)=(
q
,
a
,
C
)
, its control unit enters state
q
and writes
a
in the cell under the head, and moves the head left (if possible), right, or not at all if
C
is
L
,
R
,or
N
, respectively.
The TM
M
accepts the input string
w
∈
Γ
∗
(it contains no blanks) if, when started in
state
s
with
w
placed left-adjusted on its otherwise blank tape and the tape head at the leftmost
tape cell, the last state entered by
M
is
h
.If
M
has other halting states (states from which it does
not exit) these are rejecting states. Also,
M
may not halt on some inputs.
M
accepts the language
L
(
M
)
consisting of all strings accepted by
M
.IfaTuringmachine
halts on all inputs, we say that it
recognizes the language
that it accepts. For simplicity, we
assume that when
M
halts during language acceptance it writes the letter 1 in its first tape cell if its
input string is accepted and 0 otherwise.
The
function computed by a Turing machine
on input string
w
is the string
z
written
leftmost on the non-blank portion of the tape after halting. The function computed by a TM is
partial
if the TM fails to halt on some input strings and
complete
otherwise.
∈
Thus, a TM performs a computation on input string
w
, which is placed left-adjusted on
its tape by placing its head over the leftmost symbol of
w
and repeatedly reading the symbol
under the tape head, making a state change in its control unit, and producing a new symbol
for the tape cell and moving the head left or right by one cell or not at all. The head does not
move left from the leftmost tape cell. If a TM is used for language acceptance, it accepts
w
by
halting in the accepting state
h
. If the TM is used for computation, the result of a computation
on input
w
is the string
z
that remains on the non-blank portion of its tape.
We require that
M
store the letter 1 or 0 in its first tape cell when halting during language
acceptance to simplify the construction of a circuit simulating
M
in Section
3.9.1
.Thisre-
quirement is not essential because the fact that
M
has halted in state
h
can be detected with a
simple circuit.
The
multi-tape Turing machine
is a generalization of this model that has multiple tape
units. (These models and limits on their ability to solve problems are examined in Chapter
5
,
where it is shown that the multi-tape TM is no more powerful than the one-tape TM.) Al-
though in practice a TM uses a bounded number of memory locations, the full power of TMs
is realized only when they have access to an unbounded number of tape cells.
Although the TM is much more limited than the RAM in the flexibility with which it can
access memory, given sufficient time and storage capacity they both compute exactly the same
set of functions, as we show in Section
3.8
.
A very important class of languages recognized by TMs is the class
P
of polynomial-time
languages.
Search WWH ::
Custom Search