Page 1 of 1

COSC 4111/5111 3.0—Winter 2002

Date: Feb 24, 2002 Due: TBA in class and Web page.

Problem Set No. 2

Problems are from “Computability”, Chapter 3, 7.

(1) Ch.3. Nos. 5, 6, 22, 29, 30.

(2) Ch.3. Can you do problem 25 without using the Kleene Normal Form theorem? (Whichever way you answer, please give full justification).

(3) Ch.7. Nos. 2, 5, 6.

(4) Ch.7—optional bonus. No. 13.

COSC 4111/5111. George Tourlakis. Winter 2002