Name

1. Primitive recursive functions
(a) Prove, from scratch, that the functions a*b, a mod b, and a div b are primitive recursive.

(b) Start by giving a definition of a primitive recursive function, and explain how your procedure for multiplication fits this general definition.

(c) The notion of a primitive recursive function is a formalization of the for-loop. Translate your description of a*b into a program that uses for-loop(s) to compute the product.

2. Mu-recursive functions
(a) Prove that the functions a*b, a mod b, and a div b are mu-recursive.

(b) Start by giving a definition of a mu-recursive function, and explain how your procedure for computing a div b fits this general definition.

(c) Since a div b is an inverse operation to multiplication, it may seem reasonable to define a div b as the following expression: mu m.(b*m=a). Describe this expression in English and as a while loop, and show, step by step, what happens when we try to compute this expression for a=3 and b=2.

3. Turing machines (TM)
(a) Describe a TM that computes n+2.

(b) Trace your TM for n=1.

(c) Use your TM to design a new TM for computing composition (n+2)+2.

4. Computability in general
(a) Is every computable function primitive recursive? Explain your answer (no need to produce a detailed proof).

(b) Is every computable function mu-recursive? explain your answer. Formulate Church-Turing thesis. Is it a mathematical theorem? a statement about the physical world? can it turn out to be false?

5. Decidable and r.e. sets
(a) Prove that the union and intersection of two decidable sets and a complement to a decidable set are decidable.

(b) Prove that the union and intersection of two r.e. sets are r.e.

(c) Is the complement to a r.e. set always r.e.? Explain your answer.

6. For extra credit: briefly describe the research paper on which you are working for this class.