Information Technology Reference
In-Depth Information
ρ
(
M
1
)
ρ
(
M
2
)
ρ
(
M
k
)
...
...
w
reject
accept
reject
1
...
...
w
2
accept
accept
reject
...
...
w
k
accept
reject
?
Figure 5.11
A table whose rows and columns are indexed by input strings and Turing ma-
chines, respectively. Here
w
i
is the
i
th input string and
ρ
(
M
j
)
is the encoding of the
j
th Turing
machine. The entry in row
i
,column
j
indicates whether or not
M
j
accepts
w
i
.Thelanguage
L
1
consists of input strings
w
j
for which the entry in the
j
th row and
j
th column is
reject
.
Proof
We use proof by contradiction; that is, we assume the existence of a TM
M
k
that
L
1
.If
w
k
is in
L
1
,then
M
k
accepts it, contradicting the definition of
L
1
.This
accepts
implies that
w
k
is not in
L
1
. On the other hand, if
w
k
is not in
L
1
, then it is not accepted
by
M
k
. It follows from the definition of
L
1
that
w
k
is in
L
1
.Thus,
w
k
is in
L
1
if and only
L
1
. We have a contradiction and no Turing machine accepts
L
1
.
if it is not in
This proof uses
diagonalization
.(SeeFig.
5.11
.) In effect, we construct an infinite two-
dimensional matrix whose rows are indexed by input words and whose columns are indexed
by Turing machines. The entry in row
i
and column
j
of this matrix specifies whether or not
input word
w
i
is accepted by
M
j
. The language
L
1
contains those words
w
j
that
M
j
rejects,
that is, it contains row indices (words) for which the word “reject” is found on the diagonal.
If we assume that some TM,
M
k
, accepts
L
1
,wehaveaproblembecausewecannotdecide
whether or not
w
k
is in
L
1
. Diagonalization is effective in ruling out the possibility of solving
a computational problem but has limited usefulness on problems of bounded size.
5.7.3 Recursively Enumerable but Not Decidable Languages
We show the existence of a language that is recursively enumerable but not decidable. Our
approach is to show that the complement of a recursive language is recursive and then exhibit
a recursively enumerable language
L
2
whose complement
L
1
is not recursively enumerable:
L
2
=
{
w
i
|
w
i
is accepted by
M
i
}
THEOREM
5.7.5
Thecomplementofadecidablelanguageisdecidable.
Proof
Let
L
be a recursive language accepted by a Turing machine
M
1
that halts on all
input strings. Relabel the accepting halt state of
M
1
as non-accepting and all non-accepting
halt states as accepting. This produces a machine
M
2
that enters an accepting halt state only
when
M
1
enters a non-accepting halt state and vice versa. We convert this non-standard
machine to standard form (having one accepting halt state) by adding a new accepting halt
Search WWH ::
Custom Search