Information Technology Reference
In-Depth Information
φ 1
x
φ 1 ( x )= φ 2 ( f ( x ))
f
φ 2
Figure 5.12 The characteristic function φ i of L i , i = 1, 2 has value 1 on strings in L i and
0 otherwise. Because the language L 1 is reducible to the language L 2 , there is a function f such
that for all
x
, φ 1 ( x )= φ 2 ( f ( x )) .
Reducibility is a fundamental idea that is formally introduced in Section 2.4 and used
throughout this topic. Reductions of the type defined above are known as many-to-one re-
ductions .(SeeSection 8.7 for more on this subject.)
The following lemma is a tool to show that problems are unsolvable. We use the same
mechanism in Chapter 8 to classify languages by their use of time, space and other computa-
tional resources.
LEMMA 5.8.1 Let L 1 be reducible to L 2 .If L 2 is decidable, then L 1 is decidable. If L 1 is
unsolvable and L 2 is recursively enumerable, L 2 is also unsolvable.
Proof Let T be a Turing machine implementing the algorithm that translates strings over
the alphabet of L 1 to strings over the alphabet of L 2 .If L 2 is decidable, there is a halting
Turing machine M 2 that accepts it. A multi-tape Turing machine M 1 that decides L 1 can
be constructed as follows: On input string w , M 1 invokes T to generate the string z ,which
it then passes to M 2 .If M 2 accepts z , M 1 accepts w .If M 2 rejects it, so does M 1 .Thus,
M 1 decides L 1 .
Suppose now that L 1 is unsolvable. Assuming that L 2 is decidable, from the above con-
struction, L 1 is decidable, contradicting this assumption. Thus, L 2 cannot be decidable.
The power of this lemma will be apparent in the next section.
5.8.2 Unsolvable Problems
In this section we examine six representative unsolvable problems. They range from the classi-
cal halting problem to Rice's theorem.
We beg in by cons i de r ing the halting problem for Turing machines. The problem is to
determine for an arbitrary TM M and an arbitrary input string x whether M with input x
halts or not. We characterize this problem by the language
L H shown below. We show it is
L H is recursively enumerable but not decidable. No Turing machine exists
to decide this language.
unsolvable, that is,
L H =
{
ρ ( M ) , w
|
M halts on input w
}
 
Search WWH ::




Custom Search