CS 5315. Theory of Computation. Spring 2005. Final Exam

May 5, 2005, 7:00 pm - 9:45 pm, COMP 321
Closed book, closed notes, up to 10 pages of notes allowed

Attention:

Name: _______________________________________________________________________
ID #: _______________________________________________________________________

1-3. Primitive recursive functions:

4. Are the functions "prev", "diff", and "and" mu-recursive? totally recursive? Explain your answer.

5. Describe a Turing machine that computes the function prev(n), and trace it for n = 2. Do not forget to rewind the tape.

6. Use the Turing machine designed in Problem 5 and apply a general algorithm for Turing computability of a composition of the two functions to design a new Turing machine that computes the function prev(prev(n)) (n-2 if n>1 and 0 otherwise).

7-8. Computable functions which are not primitive recursive:

9-10. Kolmogorov complexity:

Turn over,
please.

11-12. NP-hard:

13-14. Checking program correctness:

15. Let A be an arbitrary oracle. Prove that the union of two sets which are r.e. with respect to this oracle is also r.e. with respect to it.

16. Use a general algorithm to transform a Boolean expression 0.5*x1^2-0.3*x2>0.2 into DNF and CNF forms.

17-19. Parallelization:

20. Describe, in detail, one possible physical way of solving satisfiability (and other NP-hard problems) in polynomial time: using acausal processes (time machines), using curved space-time, etc.

21. Describe, in detail, what you did for your project in the Theory of Computation class.

22. Describe, in detail, either a report on someone else's project presented in the class or a description of Dr. Bridges' talk. For extra credit: describe both.