Information Technology Reference
In-Depth Information
state and making a transition to it from all accepting halt states. This new machine halts on
all inputs and accepts the complement of
L
.
THEOREM
5.7.6
The language
L
2
is recursively enumerable but not decidable.
Proof
To establish the desired result it suffi
ces
to exhibit a Turing machine
M
that accepts
each string in
L
L
2
=
L
2
, because the complement
1
, which is not recursively enumerable,
as shown above.
Given a string
x
in
B
∗
,let
M
enumerate the input strings over the alphabet
L
2
until it finds
x
.Let
x
be the
i
th string where
i
is recorded in binary on one of
M
's t ape s .
The strings over the alphabet
Λ
used for canonical encodings of Turing machines are enu-
merated and tested to determine whether or not they are canonical encodings, as described
in Section
5.6
. When the encoding
ρ
(
M
i
)
of the
i
th Turing machine is discovered,
M
i
is
simulated with a universal Turing machine on the input string
x
. This universal machine
will halt and accept the string
x
if it is in
B
of
L
2
.Thus,
L
2
is recursively enumerable.
5.8
Reducibility and Unsolvability
In this section we show that there are many languages that are unsolvable (undecidable). In the
previous section we showed that the language
2
is unsolvable. To show that a new problem
is unsolvable we use reducibility: we assume an algorithm
A
exists for a new language
L
and
then show that we can use
A
to obtain an algorithm for a language previously shown to be
unsolvable, thereby contradicting the assumption that algorithm
A
exists.
We begin by introducing reducibility and then give examples of unsolvable languages.
Many interesting languages are unsolvable.
L
5.8.1 Reducibility
A new language
L
new
can often be shown unsolvable by assuming it is solvable and then
showing this implies that an older language
L
old
has been previously
shown to be unsolvable. Since this contradicts the facts, the new language cannot be solvable.
This is one application of
reducibility
. The formal definition of reducibility is given below
and illustrated by Fig.
5.12
.
L
old
is solvable, where
DEFINITION
5.8.1
The language
L
1
is
reducible
to the language
L
2
if there is an algorithm
computing a total function
f
:
C
∗
→D
∗
that translates each string
w
over the alphabet
C
of
L
1
into a string
z
=
f
(
w
)
over the alphabet
D
of
L
2
such that
w
∈
L
1
if and only if
z
∈
L
2
.
In this definition, testing for membership of a string
w
in
L
1
is reduced to testing for
membership of a string
z
in
L
2
, where the latter problem is presumably a previously solved
problem. It is important to note that the latter problem is no easier than the former, even
though the use of the word “reduce” suggests that it is. Rather, reducibility establishes a link
between two problems with the expectation that the properties of one can be used to deduce
properties of the other. For example, reducibility is used to identify
NP
-complete problems.
(See Sections
3.9.3
and
8.7
.)
Search WWH ::
Custom Search