Information Technology Reference
In-Depth Information
5.1
The Standard Turing Machine Model
The standard Turing machine consists of a control unit, which is a finite-state machine, and
a (single-ended) infinite-capacity tape unit. (See Fig.
5.1
.) Each cell of the tape unit initially
contains the blank symbol
β
. A string of symbols from the tape alphabet
Γ
is written left-
adjusted on the tape and the tape head is placed over the first cell. The control unit then reads
the symbol under the head and makes a state transition the result of which is either to write
a new symbol under the tape head or to move the head left (if possible) or right. (The TM
described in Section
3.7
is slightly different; it always replaces the cell contents and always
issues a move command, even if the effect in both cases is null. The equivalence between the
standard TM and that described in Section
3.7
is easily established. See Problem
5.1
.) A move
left from the first cell leads to
abnormal termination
, a problem that can be avoided by having
the Turing machine write a special
end-of-tape marker
in the first tape cell. This marker is a
tape symbol not used elsewhere.
DEFINITION
5.1.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
}
)
×
(Γ
∪{
β
}∪{
}
)
is the
next-state function
,
s
is the
L
,
R
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
,
C
)
, its control unit enters state
q
and writes
a
∈
if
C
=
a
∈
Γ
∪{
β
}
or moves the head left (if possible) or right if
C
is
L
or
R
, 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
.
M
accepts the language
L
(
M
)
consisting of all strings accepted
by
M
. Languages accepted by Turing machines are called
recursively enumerable
.Alangua e
L
is
decidable
or
recursive
if there exists a TM
M
that halts on every input string, whether in
L
or not, and accepts exactly the strings in
L
.
Afunction
f
:Γ
∗
→
∈
Γ
∗
∪{⊥}
,where
⊥
is a symbol that is not in
Γ
,is
partial
if for some
Γ
∗
,
f
(
w
)=
w
∈
(
f
is
not defined
on
w
). Otherwise,
f
is
total
.
ATM
M
computes a function
f
:Γ
∗
→
⊥
Γ
∗
∪⊥
for those
w
such that
f
(
w
)
is defined 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,
M
enters the accepting halt state
h
with
f
(
w
)
written left-adjusted on its
otherwise blank tape. If a TM halts on all inputs, it implements an
algorithm
.Ataskdefinedby
a total function
f
is
solvable
if
f
has an algorithm and
unsolvable
otherwise.
0
1
2
Ta p e Un i t
Control
Unit
Figure 5.1
The control and tape units of the standard Turing machine.
Search WWH ::
Custom Search