1. Primitive recursive functions
(a) Prove, from scratch, that the functions a + b, 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 the sum 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 the product.
2. Mu-recursive functions
(a) Prove that the functions a + b, 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 - 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 = 2 and b = 3. Describe a correct way of describing a - b by using mu-recursion.
3. Turing machines (TM)
(a) Describe a TM that computes a - 1 (in unary notation).
(b) Trace your TM for a = 2.
(c) Use your TM to design a new TM for computing composition (a - 1) - 1.
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. Kolmogorov complexity
What is Kolmogorov complexity? provide a definition.
6. Briefly describe a research project on which you are working for this class.