Page 1 of 1

COSC 4111 3.0/5111 3.0—Fall 2004

Posted: Nov. 19, 2004 Due: End of term [Exact date TBA]

Problem Set No. 3

(1) “W_{i}” is the symbol Rogers uses for “the i-th semi-recursive set”, that is,

x ∈ W_{i} ≡ (∃z)T (i, x, z)

Question: Is there a partial recursive function λx.f(x) such that for all i

W_{i} ≠ ∅ ⇒ f(i) ↓ ∧f(i) = min{y : y ∈ W_{i}}

If you think that “yes”, then you must give a proof.

If you think that “no”, then you must give a definitive counterexample.

(2) Without using Rice’s theorem, prove that

(a) the set A = {x : ran(ϕ_{x}) has exactly five distinct elements} is not recursive. (I.e., “x ∈ A is unsolvable”).

(b) the set B = {x : ϕ is 1-1} is not recursive. (I.e., “x ∈ B is unsolvable”).

(c) the set C = {x : ϕ_{x} is onto} is not recursive. (I.e., “x ∈ C is unsolvable”).

(d) the set D = {x : ϕ_{x} is the characteristic function of some set} is not r.e.

(e) the set ℕ − D (i.e., \overline{D}) is not r.e. either.

(f) the set E = {x : ran(ϕ_{x}) contains only prime numbers} is not r.e.

(3) (a) (Eaaasyyy!) Give a careful and complete proof (no hand-waiving!) that if λyx⃗_{n}.y = f(x⃗_{n}) is in P_{∗} then f ∈ P

(b) (A bit tricky) Is the “proof” given below for the above question correct? If not, \underline{where exactly} does it go wrong? Proof. Let y = f(x⃗_{n}) be r.e. Then y = f(x⃗_{n}) ≡ ψ(y, x⃗_{n}) = 0 for some ψ ∈ P. Thus g = λx⃗_{n}.(μy)ψ(y, x⃗_{n}) is in P. But g = f, since the unbounded search finds the y that makes y = f(x⃗_{n}) true, if f(x⃗_{n}) ↓. Thus, f ∈ P. □

COSC 4111/5111. George Tourlakis. Fall 2004