CS 5315, Final Exam, Spring 2007


(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 + c, 1 - a (funny minus that never goes below 0), "a or b", and "not a" are primitive recursive.

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

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

2. Mu-recursive functions
(a) Prove that the functions a * b + c, 1 - a, "a or b", "not a", and a function that is defined only for n = 1 and is equal to 0 for this n are mu-recursive.

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

(c) Since a - 1 is an inverse operation to a + 1, it may seem reasonable to define a - 1 as the following expression: mu m.(m + 1 = 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.

3. Turing machines (TM)
(a) Describe a TM that computes n1 + n2 + n3.

(b) Trace your TM for n1 = 1, n2 = 1, and n3 = 1.

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

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) Prove that the halting problem is undecidable.

Turn over, please

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 101101...101 (101 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 0.9*x1+0.3*x2<0.2+4.6*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 a1*...*an of n given numbers 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.