Information Technology Reference
In-Depth Information
if
M
halts on
w
.Thus,
M
H
decides the halting problem, which as shown earlier cannot be
decided.
The third unsolvable problem we consider is the
empty set acceptance problem
:Givena
Turing machine, we ask if we can tell if the language it accepts is empty. We reduce the halting
problem to this language.
L
EL
=
{
ρ
(
M
)
|
L
(
M
)=
∅}
THEOREM
5.8.3
The language
L
EL
is not decidable.
Proof
We reduce
L
H
to
L
EL
, assume that
L
EL
is decidable by a TM
M
EL
,andthenshow
that a TM
M
H
exists that decides
L
H
, thereby establishing a contradiction.
Givenanencoding
ρ
(
M
)
for an arbitrary TM
M
and an arbitrary input
w
,theTM
M
H
constructs a TM
T
(
M
,
w
)
that accepts the string placed on its tape if it is
w
and
M
halts on it; otherwise it enters an infinite loop.
M
H
can implement
T
(
M
,
w
)
by entering an
infinite loop if its input string is not
w
and otherwise simulating
M
on
w
with a universal
Turing machine.
It follows that
L
(
T
(
M
,
w
))
is empty if
M
does not halt on
w
and contains
w
if it does
halt. Under the assumption that
M
EL
decides
L
H
by constructing
T
(
M
,
w
)
and passing it to
M
EL
, which accepts
ρ
(
T
(
M
,
w
))
if
M
doesnothalton
w
and
rejects it if
M
does halt. Thus,
M
H
decides
L
EL
,
M
H
can decide
L
H
, a contradiction.
The fourth problem we consider is the
regular machine recognition problem
.Inthis
case we ask if a Turing machine exists that can decide from the description of an arbitrary
Turing machine
M
whether the language accepted by
M
is regular or not:
L
R
=
{
ρ
(
M
)
|
L
(
M
)
is regular
}
THEOREM
5.8.4
The language
L
R
is not decidable.
Proof
We assume that a TM
M
R
exists to decide
L
R
and show that this implies the exis-
tence of a TM
M
H
that decides
L
H
, a contradiction. Thus,
M
R
cannot exist.
Givenanencoding
ρ
(
M
)
for an arbitrary TM
M
and an arbitrary input
w
,theTM
M
H
constructs a TM
T
(
M
,
w
)
that scans its tape. If it finds a string in
0
n
1
n
{
|
n
≥
}
,it
accepts it; if not,
T
(
M
,
w
)
erases the tape and simulates
M
on
w
,haltingonlyif
M
halts
on
w
.Thus,
T
(
M
,
w
)
accepts all strings in
0
B
∗
if
M
halts on
w
but accepts only strings
0
n
1
n
B
∗
if
M
halts
{
|
n
≥
}
otherwise. Thus,
T
(
M
,
w
)
accepts the regular language
in
0
0
n
1
n
on
w
and accepts the context-free language
otherwise. Thus,
M
H
can be
implemented by constructing
T
(
M
,
w
)
and passing it to
M
R
, which is presumed to decide
L
R
.
{
|
n
≥
}
0
The fifth problem generalizes the above result and is known as
Rice's theorem
.Itsaysthat
no algorithm exists to determine from the description of a TM whether or not the language it
accepts falls into any proper subset of the recursively enumerable languages.
Let
RE
be the set of recursively enumerable languages over
B
C
.Foreachset
that is a
proper subset of
RE
, define the following language:
L
C
=
{
ρ
(
M
)
|
L
(
M
)
∈C}
Rice's theorem says that, for all
C
such that
C
=
∅
and
C⊂
RE
, the language
L
C
defined above
is undecidable.
Search WWH ::
Custom Search