Page 1 of 1

COSC 4111/5111 3.0—Winter 2002

Posted: Jan. 19, 2002 Due: Following the reading week [Exact date TBA]

Problem Set No. 1

(1) Answer the “why” in the note following the corollary on p.79.

(2) Problem 1 (p.80).

(3) Prove that λx, y. gcd(x, y) is in PR.

(4) Problems 14, 16, p.81.

(5) Prove that if a class of functions C is closed under (μ^{∘}y)_{≤z} and substitution, then its corresponding class of relations C_{∗} is closed under (∃y)_{≤z}.

(6) Problems 18, 19, 20, p.81.

(7) Write a loop program which computes λx.rem(x, 5). The program must only allow instruction-types X = 0, X = X + 1, X = Y and Loop X … end. It must not nest the Loop-end instruction!

(8) Write a loop program which computes λx.⌊x/4⌋. The program must only allow instruction-types X = 0, X = X + 1, X = Y and Loop X … end. It must not nest the Loop-end instruction!

(9) Problem 34, p.83.

COSC 4111/5111. George Tourlakis. Winter 2002