**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^b, 3 - a (funny minus that
never goes below 0),
"a and b", and "not a"
are primitive recursive.

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

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

2. *Mu-recursive functions*

(a) Prove that the functions a^b, 3 - a, "a and b", "not a", and
a nowhere defined function
are mu-recursive.

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

(c) Since division 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=2 and b=3.

3. *Turing machines (TM)*

(a) Describe a TM that computes a + b.

(b) Trace your TM for a=2 and b=1.

(c) Use your TM to design a new TM for computing composition (n1 + n2) + n3.

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?

(c) Use the known fact that halting problem is undecidable to prove that zero-checker is not possible.

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. *Kolmogorov complexity*

(a) What is Kolmogorov complexity? Give an exact definition.

(b) Estimate the Kolmogorov complexity
of a string 011011...01011 (011 repeated 2,006 times).
*For extra
credit:* prove that Kolmogorov complexity is not computable.

7. *NP*

(a) Define what it means for a problem to be from the class
P, from the class NP, to be NP-hard.

(b) Use a general algorithm to transform a Boolean
expression *x1+0.3*x2<0.2+5*x1* into DNF and CNF forms.

(c)-(f) Reduce the satisfiability problem for the formula
(x1 \/ x2) & (x1 \/ -x2 \/ -x3) to:

(c) 3-coloring

(d) clique

(e) subset problem

(f) interval computations.

8. *Parallelism*

(a) Describe, step by step, how to compute the dot product a1*b1+...+an*bn of two given vectors a1,...,an and b1,...,bn in parallel.

(b) Does this problem belong to the class NC? explain your answer.

(c) Is NC a subset of P? explain your answer.

(d) Is NC equal to P? Explain the relationship between this equation and linear programming problems. Give an example of a linear programming problem.

(e) What will be the computation time if we take communication time into consideration? Where is a related argument used in the proof that satisfiability is NP-hard?

9. *Non-standard physical models*:
Describe two possible physical schemes that would enable us to compute
faster than by using traditional physics.

10. * Research project:* Briefly describe the research project on
which you worked for this class.