Information Technology Reference
In-Depth Information
THEOREM
5.8.5
(Rice)
Let
C⊂
RE
,
C
=
∅
.Thelanguage
L
C
is not decidable.
Proof
To p r o v e t h a t
L
C
is not decidable, we assume that it is decidable by the TM
M
C
and
show that this implies the existence of a TM
M
H
that decides
L
H
, which has been shown
previously not to exist. Thus,
M
C
cannot exist.
We consider two cases, the first in which
B
∗
is in not
C
and the second in which it is in
C
. In the first case, let
L
be a language in
C
.Inthesecond,let
L
be a language in
RE
−C
.
Since
is a proper subset of
RE
and not empty, there is always a language
L
such that one
of
L
and
C
B
∗
is in
.
Givenanencoding
ρ
(
M
)
for an arbitrary TM
M
and an arbitrary input
w
,theTM
M
H
constructs a (four-tape) TM
T
(
M
,
w
)
that simulates two machines in parallel (by al-
ternatively simulating one step of each machine). The first,
M
0
, uses a phrase-structure
grammar for
L
to see if
T
(
M
,
w
)
's input string
x
is in
L
;itholds
x
on one tape, holds the
current choice inputs for the NDTM
M
L
of Theorem
5.4.2
on a second, and uses a third
tape for the deterministic simulation of
M
L
. (See the comments following Theorem
5.4.2
.)
T
(
M
,
w
)
halts if
M
0
generates
x
. The second TM writes
w
on the fourth tape and sim-
ulates
M
on it.
T
(
M
,
w
)
halts if
M
halts on
w
.Thu ,
T
(
M
,
w
)
accepts the regular
language
C
and the other is in its complement
RE
−C
B
∗
if
M
halts on
w
and accepts
L
otherwise. Thus,
M
H
can be implemented by
constructing
T
(
M
,
w
)
and passing it to
M
C
L
C
, which is presumed to decide
.
Our last problem is the
self-terminating machine problem
. The question addressed is
whether a Turing machine
M
given a description
ρ
(
M
)
of itself as input will halt or not. The
problem is defined by the following language. We give a direct proof that it is undecidable;
that is, we do not reduce some other problem to it.
L
ST
=
{
ρ
(
M
)
|
M
is self-terminating
}
THEOREM
5.8.6
The language
L
ST
is recursively enumerable but not decidable.
Proof
To s h ow t h a t
L
ST
is recursively enumerable we exhibit a TM
T
that accepts strings
L
ST
.
T
makes a copy of its input string
ρ
(
M
)
and simulates
M
on
ρ
(
M
)
by passing
(
ρ
(
M
)
,
ρ
(
M
))
to a universal TM that halts and accepts
ρ
(
M
)
if it is in
in
L
ST
.
L
ST
is not decidable, we assume that it is and arrive at a contradiction.
To s h ow t h a t
L
ST
.WedesignaTM
M
∗
that does the following:
M
∗
simulates
M
ST
on
the input string
w
.If
M
ST
halts and accepts
w
,
M
∗
enters an infinite loop. If
M
ST
halts
and rejects
w
,
M
∗
accepts
w
.(
M
ST
halts on all inputs.)
The new machine
M
∗
is either self-terminating or it is not. If
M
∗
is self-terminating,
then on input
ρ
(
M
∗
)
, which is an encoding of itself,
M
∗
enters an infinite loop because
M
ST
detects that it is self-terminating. Thus,
M
∗
is not self-terminating. On the other
hand, if
M
∗
is not self-terminating, on input
ρ
(
M
∗
)
it halts and accepts
ρ
(
M
∗
)
because
M
ST
detects that it is not self-terminating and enters the rejecting halt state. But this con-
tradicts the assumption that
M
∗
is not self-terminating. Since we arrive at a contradiction
in both cases, the assumption that
Let
M
ST
decide
L
ST
is decidable must be false.
5.9 Functions Computed by Turing Machines
In this section we introduce the partial recursive functions, a family of functions in which
each function is constructed from three basic function types, zero, successor, and projection,
Search WWH ::
Custom Search