Problem Solving in Automata, Languages, and Complexity

240

(b

( c

COMPUTABILITY THEORY

) Construct a DTM that simulates the three DTM’s accepting sets

A, B, and C by the dovetailing method and accepts D.

) Find a recursive predicate R such that D = { 2 1 (3.~) R(x, y)}.

2. Design two dovetailing algorithms for set B of Example 5.11, the first
   based on the intuitive algorithm given in the solution, and the second
   based on the last line of the proof by the projection theorem.


3. Assume that A, B, C C (0, 1}* and A n B = B n C = C n A = 8. Also
   assume that there exi% three partial recursive functions fl, f2, f3 that
   have the following properties:
   1 ifzEAUB,
   f&) =^2 if 32 EC, f0 2x = {

T ifzEAUC,

0 otherwise,

and

f otherwise,

f3(x) = {

T ifxEBUC,

0 otherwise.

(a) Prove that sets A, B, C are all recursive.

(b) Let Ml, M2 and M3 be three DTM’s that compute functions fr , f2

and f3, respectively. Construct DTM’s that simulate Ml, M2 and

M3 to compute XA, XB and XC.

4. Show that every infinite r.e. set has an infinite subset that is recursive.


5. (a) Assume that f : {O,l} + {O,l} is a partial recursive function,
   and A is an r.e. set. Show that f(A) and f-l(A) are r.e. (Recall
   that f(A) = {f(x) I x E 4 f(x) 3-l and f-l (A) = {x I f(x) 3-9
   f(x) E 4.)
   (b) Assume that f is a recursive function and A is a recursive set. Is
   f(A) recursive? Is f -’ (A) recursive?


6. A function f : (0, 1} + (0, l} is strictly increasing if f(x) < f (x + 1)
   for all x E (0, 1)‘. Sh ow that an infinite set A is recursive if and only if
   A is the range of a strictly increasing recursive function f.


7. Show that the following sets are r.e.
   (a) Al = {n 1 {O,l,.. .,n} C Wn}.
   (b) A2 = (71 1 Iwn n (0,iI... , n}l > n/2}. [Hint: Use the Gijdel
   numbering to encode n/2 string&to a single string.]
   0 A3 = {(n,x) \ there exist nl,.. .,nk, k 2 1, such that x E W,,,
   nl E wn2,... y nk-1 E wn~,, nk E wn}*
   (4 A4 = {x I there exists an integer n such that &(y) = 0 for all
   Y c (0, w).
   (e) As = {n I during th e computation of Mn (11 l), Mn has a configu-
   ration that contains a substring 000).