Page 1 of 1

COSC 4111 3.0—Fall 2002

Posted: Nov 18, 2002 Due: End of term (before exams) [Exact date TBA]

Problem Set No. 3

(1) Do problem #25, p.126 without using the normal form theorems.

(2) Without using Rice’s theorem, show that the set A = {x : ran(ϕ_{x}) has exactly three elements} is not recursive. (I.e., “x ∈ A is unsolvable”).

(3) Is the “proof” below correct? If not, where exactly does it go wrong?

“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.”

(4) Ch.7. #3 parts (1) and (2) only.

COSC 4111. George Tourlakis. Fall 2002