Problem Set No. 3

Dept. of Computer Science

Date: March 17, 2001
Due: TBA

1. Do Ch. 7 problems 5 and 9.

2. Without using Rice’s theorem, show that the set A = {x : 3 ∈ ran(ϕ_{x})} 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. Chapter 8, problem 7.

5. Chapter 13, problems 1, 7, 23, 26, 48.

cs4111/5111 Automata and Computability. Instructor: George Tourlakis. Problem Set#3/W2002.