Page 1 of 1

COSC 4111/5111 3.0—Fall 2001

Date: Oct 26, 2001 Due: TBA in class and Web page.

Problem Set No. 2

Problems are from “Computability”, Chapter 3.

(1) For all. Nos. 3, 7, 18, 22, 23, 26, 29, 30.

In #29 note that you cannot say “by identification of the two variables we obtain {x : ϕ_{x}(x) ↓} which is not recursive, etc.”. There are no two variables, but only one, as in: {z : ϕ_{Kz}(Lz) ↓}. In other words, do not confuse ⟨…⟩ with (…).

(2) Additional problems for the graduate students. Nos. 1, 10, 12, 37.

COSC 4111/5111. George Tourlakis. Fall 2001