Page 1 of 1

COSC 4111 3.0—Fall 2002

Posted: Oct 24, 2002 Due: In about four weeks [Exact date TBA]

Problem Set No. 2

(1) Prove that λx.A_{x}(2) ∉ PR, where λnx.A_{n}(x) is our version of the Ackermann function. Your proof must follow this path:

(a) Prove that A_{n}(x) < A_{x}(2) a.e. with respect to x.

(b) Using the previous result, prove that if λx.f(x) ∈ PR, then f(x) < A_{x}(2) a.e.

(c) Conclude the argument.

(2) Prove that if λy⃗.f(y⃗) ∈ P and Q(x⃗, z) ∈ P_{∗}, then Q(x⃗, f(y⃗)) ∈ P_{∗}. Keep in mind the definition (“1-point-rule”)

Q(x⃗, f(y⃗)) ≡^{Def}(∃z)(z = f(y⃗) ∧ Q(x⃗, z))

(3) Prove that if the graph of f is r.e. then f ∈ P. Is the converse true? Why?

(4) Using the above and closure properties of P_{∗} (cf. posted “Kleene” paper) prove that P is closed under definition by so-called “positive cases” (these are r.e. cases). That is, if all the f_{i} are in P, all the Q_{i} are in P_{∗} and g below is a function, then g ∈ P.

g(x⃗) = \begin{cases}f_{1}(x⃗) & & if Q_{1}(x⃗) \\ f_{2}(x⃗) & & if Q_{2}(x⃗) \\ ⋮ & ⋮ \\ f_{k}(x⃗) & & if Q_{k}(x⃗) \\ ↑ & & otherwise \end{cases}

Hint. Use the previous exercise and work with the graph of g.

(5) Do #22 and #23, p.126 of text.

(6) Prove that there is an e ∈ ℕ such that ϕ_{e}(x) = e for all x. That is, “program e outputs itself for every input value x”.

Hint. Use the recursion theorem.

(7) For your amusement: Can you write a “self-reproducing” program, such as e above, in your favourite programming language? This program, on every input, just prints itself—exactly, i.e., prints nothing else—and halts.

(Actually, I am inviting you to write and fully test one; I am not just looking for a yes/no answer :-)