Page 1 of 1

COSC 4111 3.0—Fall 2002

Posted: Sep 28, 2002 Due: End of October [Exact date TBA]

Problem Set No. 1

(1) Express each of the functions max(x, y) and min(x, y) by substitution \underline{using only}

the functions x + y and x −^{·} y.

(2) Prove that the function f(z) that returns the number of distinct primes in the factorization of z is in PR.

(3) Prove that λxy.lcm(x, y) is in PR, where “lcm” denotes least common multiple, i.e., the smallest number z that is divided by both x and y.

(4) Page 81, problems 18, 22.

(5) Regarding the function λix.g_{i}(x) of Theorem 3 (p. 78–79 of text): It is proved there that 1 −^{·} g_{x}(x) = 0 is not in PR_{∗}.

How about 1 + g_{x}(x) = 0? Why?

(6) Write a loop program which computes λx.rem(x, 3). 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!

(7) Write a loop program which computes λxyz.if x = 0 then y else z. The program must only allow instruction-types X = 0, X = X + 1, X = Y and Loop X … end.

(8) Prove that the predicate Q(z) that is true iff z = 2^{x} + 2^{y} where x > y > 0 for appropriate x and y is in PR_{∗}.

COSC 4111. George Tourlakis. Fall 2002