Problem Set No. 3

Dept. of Computer Science

Date: Nov 22, 2001
Due: TBA (around Dec. 17)

1. Do Ch. 7 problems #1, 9.

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

3. Prove that y = f(x⃗) is r.e. iff f ∈ P.

4. Do Ch. 8 problems #2, 3, 4.

NB. In #2 there’s a typo: The superscript (m) should be (m+1) throughout. For #4 you may proceed with an easier proof (without selection theorem)

than the one the hint on p.321 implies. Just use the previous problem.

5. Is the “proof” below correct?

“Let y = f(x⃗_{n}) be r.e. Then g = λx⃗_{n}.(μy)(y = f(x⃗_{n})) is in P. But g = f. Thus, f ∈ P.”

6. Is λx.(μ̃y)(y ∈ W_{x}) in P? How about λx.(μy)(y ∈ W_{x})? What does the latter return?

7. (Grad) Show that {x : ϕ_{x}(x) ↓} is not a complete index set.

Hint. Start by showing (using the recursion theorem) that there is an e ∈ ℕ such that

ϕ_{e}(x) = \{ \begin{matrix}0 & if x = e \\ ↑ & otherwise \end{matrix}

8. Do Ch. 9 problems #18, 20, 22.

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