256 COMPUTABILITY THEORY
Exercises 5.4
1. Assume that AU B = (0, 1}* and An B # (8. Show that if A and B are
re., then A srn A n B.- If g : {0,1} + {0,1} is one-to-one, then we define g-l(x) = (miny)
b(Y) = x]. Show that there exists a recursive function f such that for
all one-to-one functions q&, qQ(m) = +;l. - Show that there exists a recursive function ~(5, y) such that &(z,Y)(z) =
Mw)* - (a) Show that for every partial recursive function f, there exists a
recursive function g such that w,(,) = f -’ (Wx).
(b) Show that there is a recursive function g such that for all x1, y,
w,(x,,) = K1(wy) = 1x1 4x(4 E wy}** 5. (Rice’s theorem for r.e. index sets) For any finite set D = {xl,... , x,},
we say [xl,..., ’.
x,] (in any order) is a code of D. Show that an index
set A is r.e. if and only if
(i) x E A and Wx C - WY imply y E A;
(ii) x E A implies that there exists y E A such that WY is a finite
subset of Wx; and
(iii) There exists an r.e. set B that contains codes of all and only finite
sets Wx such that x E A (i.e., for each x E A such that Wx is finite,
B contains at least one of its code, and for every [xl,... , x,] E B
andevery~suchthatW~={x~,...,x,},xEA).- For any partial recursive function f : (0, 1} + (0, l}, we write Df to
denote its domain {x 1 f(x) 4). Let f,g, h : {O,l} + {O,l} be three
partial recursive functions.
(a) Show that th ere exists a partial recursive function p : (0, l} +
(0, i} such that DP = Df U D, U Dh, and for each x E Dp,
P(X) = f (4 Or P(X) = s(x) Or P(X) = h(x)
(b) Show that there does not always exist a partial recursive function
q : (0, 1)’ -+ (0, l} such that D, = Df U D, U Dh, and for each
x f D,, q(x) = f(x) or q(x) = g(x) or q(x) = h(x), and for each
x E Df f-J D, i-3 Dh, q(x) = m~~{f(~>,s(~),q~)}~ - Define
f(n) = { T
min{VI&} if Wn # 0,
otherwise.
Is f a partial recursive function? Prove your answer.
- (a) Show that th ere exists an r.e. set B such that nnEB Wn is not r.e.