Page 1 of 1

COSC 4111/5111 3.0—Fall 2004

Date: Nov 6, 2004 Due: TBA in class and Web page. (Approx. shelf life=3 weeks)

Problem Set No. 2

Most problems are from “Computability”, Chapters 3, 7, 8. All relate to material in said chapters.

(1) Ch.3. Nos. 6, 26, 29, and 30.

(2) Prove that if f is total and λx⃗y.y = f(x⃗) is in ℜ_{∗}, then f ∈ R.

(3) Prove that there exists a partial recursive h that satisfies

h(y, x) = \begin{cases}y & if x = y + 1 \\ h(y + 1, x) & otherwise \end{cases}

Which function is λx.h(0, x)?

(4) Given λyx⃗.f(y, x⃗) ∈ 𝔓. Prove that there exists a partial recursive g that satisfies

g(y, x⃗) = \begin{cases}y & if f(y, x⃗) = 0 \\ g(y + 1, x) & otherwise \end{cases}

How can you express λx.g(0, x) in terms of f?

(5) (Grad) Express the projections K and L of J(x, y) = (x + y)^{2} + x in closed form—that is, without using (μy)_{<z} or bounded quantification. (Hint. Solve for x and y the Diophantine equation z = (x + y)^{2} + x. The term ⌊\sqrt{z}⌋ is involved in the solution.)

(6) Ch.7. Nos. 5, 6 (Do not use Rice theorems).

(7) (Grad) Prove that a recursively enumerable set of sentences T over a finitely generated language (e.g., like that of arithmetic) admits a recursive set of axioms, i.e., for some recursive Γ, T = Thm_{Γ}. (Hint. Note that for any A ∈ T , any two sentences in the sequence

A, A ∧ A, A ∧ A ∧ A, …

are logically equivalent. Now see if Theorem 1 and its corollaries (section 8.2 in “Computability”) can be of any help.)

COSC 4111/5111. George Tourlakis. Fall 2004