Information Technology Reference
In-Depth Information
THEOREM
5.8.1
The language
L
H
is recursively enumerable but not decidable.
Proof
To s h ow t h a t
L
H
is recursively enumerable, pass the encoding
ρ
(
M
)
of the TM
M
and the input string
w
to the universal Turing machine
U
of Section
5.5
. This machine
simulates
M
and halts on the input
w
if and only if
M
halts on
w
.Thus,
L
H
is recursively
enumerable.
To s h ow t h a t
L
H
is decidable by a Turing machine
M
H
and show a contradiction. Using
M
H
we construct a Turing machine
M
∗
that decides
the language
L
H
is undecidable, we assume that
.
M
∗
simulates
M
H
on
ρ
(
M
)
,
w
to determine whether
M
halts or not on
w
.If
M
H
says that
M
does not halt,
M
∗
accepts
w
.If
M
H
says that
M
does halt,
M
∗
simulates
M
on input string
w
and rejects
w
if
M
accepts it and accepts
w
if
M
rejects it. Thus, if
L
∗
=
{
ρ
(
M
)
,
w
|
w
is not accepted by
M
}
L
∗
.
The procedures described in Section
5.6
can be used to design a Turing machine
M
that determines for which integer
i
the input string
w
is lexicographically the
i
th string,
w
i
,
and also produce the description
ρ
(
M
i
)
of the
i
th Turing machine
M
i
.
To decide
L
H
is decidable, so is
1
we use
M
to translate an input string
w
=
w
i
to the string
ρ
(
M
i
)
,
w
i
.
Given the presumed existence of
M
∗
, we can decide
L
L
∗
. However, by
L
1
by deciding
L
∗
is not
L
1
is not decidable (it is not even recursively enumerable). Thus,
Theorem
5.7.4
,
L
H
is also not decidable.
decidable which implies that
The second unsolvable problem we consider is the
empty tape acceptance problem
:given
aTuringmachine
M
, we ask if we can tell whether it accepts the empty string. We reduce the
halting problem to it. (See Fig.
5.13
.)
L
ET
=
{
ρ
(
M
)
|
L
(
M
)
contains the empty string
}
THEOREM
5.8.2
The language
L
ET
is not decidable.
Proof
To s h ow t h a t
L
ET
is not decidable, we assume that it is and derive a contradiction.
The contradiction is produced by assuming the existence of a TM
M
ET
that decides
L
ET
and then showing that this implies the existence of a TM
M
H
L
H
.
Givenanencoding
ρ
(
M
)
for an arbitrary TM
M
and an arbitrary input
w
,theTM
M
H
constructs a TM
T
(
M
,
w
)
that writes
w
onthetapewhenthetapeisemptyand
simulates
M
on
w
,haltingif
M
halts. Thus,
T
(
M
,
w
)
accepts the empty tape if
M
halts
on
w
.
M
H
decides
that decides
L
H
by constructing an encoding of
T
(
M
,
w
)
and passing it to
M
ET
.
(See Fig.
5.13
.) The language accepted by
T
(
M
,
w
)
includes the empty string if and only
ρ
(
M
)
T
(
M
,
w
)
“Ye
s”
Decide
Empty String
w
“No”
Decide Halt
Figure 5.13
Schematic representation of the reduction from
L
H
L
ET
.
to
Search WWH ::
Custom Search