CS 5315, Test 1, Tuesday, March 2, 2010

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 n!, not(n), 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 n! fits this general definition.

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

2. Mu-recursive functions
(a) Prove that the functions n!, not(n), and the relation a > b are mu-recursive.

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

(c) Since division is an inverse operation to multiplication, it may seem reasonable to define the division a / b as the following expression: mu m.(m * b = 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 = 6 and b = 4. Describe a correct way of describing a / b 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 = 1.

(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 intersection 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.

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

(d) Is the union 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.