246 COMPUTABILITYTHEORY
Figure 5.2: The reduction function f cannot cross the dotline.
- Show that the set {(i, j) ) VVi = wj} is not an r.e. set.
- We say two sets A and B are recursively separable if there exists a
recursive set C such that A C C and B C c. Show that for any
n # m. E N, sets K, and h-,- are not recursively separable, where
A-f-& = {X 1 &(x) is defined and is equal to n}.
- are not recursively separable, where
- Give a formal proof that set S defined in Example 5.23 is r.e. That
is, let h(e) be the string printed out in stage e by the algorithm for S
(h(e) f if it does not output any string in stage e). Prove that h is
partial recursive (without using the Church-Turing Thesis).
- Show that there exists a set A such that both A and A are infinite but
neither has an infinite r.e. subset.
- Show that there exists a set A such that both A and A are infinite but
5.4 Reducibility
The second proof technique for proving languages not recursive or not r.e. is
the technique of reducibility. Intuitively, we say a language A is reducible to a
language B if the membership problems of the form “x E?A” can be reduced
to the membership problems of the form “y E?B.” Therefore, an algorithm
for problem B could be converted to an algorithm for problem A. Technically,
there are several different types of reducibility, with different applications. We
will study only the simplest type of reducibility here, namely, the many-one
reducibility.
Assume that A and B are two languages over the alphabet C. We say that
A is many-one reducible to B, denoted by A srn B, if there exists a recursive
function f : C* + C* such that for every string x E C*,x E A e f(x) E f?-
The function f is called the reduction function (see Figure 5.2).
Proposition 5.24 The following hold for cdl sets A, B, C C - C*:
(a) A <rn A.
(b)A<n-&B&X 3 A<,C. -