Page 1 of 1

COSC 4111/5111 3.0—Fall 2004

Posted: Sep 26, 2004 Due: End of October [Exact date TBA]

Problem Set No. 1

NOTE: This is the full problem set (originally I thought I would be bringing it out in two parts). Problems marked “Grad” are only required by students who enrolled in the 5111 version of the course.

(1) “Dress” the primitive recursion of Example 13, p. 38, in the rigid notation. After that (and mindful of the rigid definitions of “add” and “multiply”) write down a shortest derivation for λxy.x^{y}.

(2) Prove that Euler’s function λx.ϕ(x) that returns the number of terms in the sequence 0, 1, 2, …, x − 1 that are relatively prime^{∗} to x is in PR.

(3) (Grad) Prove that ϕ(p^{a}) = p^{a} − p^{a−1} if p is prime.

(4) Prove Lemma 1 on p.47.

(5) Page 81, do problems 18, 22.

(6) (Grad) 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?

(7) Write a “nice clean” loop program which computes λx.⌊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! It is required that you give a convincing general argument (not a “trace”) as to why your program works as specified.

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

(9) (Grad. This requires some research; the reference is given in the problem, p.82. Your answer must be thorough and complete, not just a sketch) Do problem 25, p.82.

(10) Do problem 34, p.83.

COSC 4111/5111. George Tourlakis. Fall 2004

∗a and b are relatively prime means that their greatest common divisor is 1.