**Name**

(Please do not forget to put your name on all extra sheets of paper)

1. *Primitive recursive functions*

(a) Prove, from scratch, that the functions a^{n}, a - b (funny
minus that never goes below 0), and the relation a = b are
primitive recursive.

(b) Start by giving a definition of a primitive recursive function, and explain how your procedure for a - b 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 a - b.

2. *Mu-recursive functions*

(a) Prove that the functions a^{n}, a - b, and a = b are
mu-recursive.

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

(c) Since subtraction is an inverse operation to addition, it may seem reasonable to define the subtraction a - 5 as the following expression: mu m.(m + 5 = 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 = 0 and a = 6. Describe a correct way of describing a - 5 by using mu-recursion.

3. *Turing machines (TM)*

(a) Describe a TM that computes a - 2 (in unary notation).

(b) Trace your TM for a = 3.

(c) Use your TM to design a new TM for computing composition (a - 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) Is the union of two r.e. sets always r.e.? If your answer is "yes", provide
a proof. If your answer is "no", provide a counterexample.

(b) Is a complement to a r.e. set always r.e.? If your answer is "yes", provide a proof. If your answer is "no", provide a counterexample.

(d) Is the intersection of a r.e. set and a decidable set always decidable? If your answer is "yes", provide a proof. If your answer is "no", provide a counterexample.

6. Briefly describe a research project on which you are working for this class.