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

Attention:

• Extra credit will only be counted if you solve all the problems.
• You can use as many extra pages as you need but please put your name on all the pages.
• In all the problems, show work, do not just give answers.
• Please do not waste your time copying unrelated things from your notes into the test sheets. Only answers to the test questions will bring points.

1-3. Primitive recursive functions:

• What is a primitive recursive function?
• Prove, "from scratch" (i.e., using only the definitions), that the functions prev(n) (n-1 if n>0 and 0 otherwise), diff(a,b) (a-b if a>b and 0 otherwise), and A&B ("and") are primitive recursive functions.
• It is known that primitive recursion is a formal description of a for-loop. Reformulate your expression for addition in terms of primitive recursion by using for-loops (if necessary, embedded for-loops).

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:

• Prove that there exists a computable function which is not primitive recursive.
• Formulate Church's thesis and tell whether your proof depends on it being true.

9-10. Kolmogorov complexity:

• What is Kolmogorov complexity?
• Estimate the Kolmogorov complexity of a string 10101...010 (10,000 times).
• For extra credit: prove that Kolmogorov complexity is not computable.

11-12. NP-hard:

• Define what it means for a problem to be from the class P, from the class NP, to be NP-hard.
• Formulate the problems about which we proved NP-hardness: satisfiability, interval computations, 3-coloring.

13-14. Checking program correctness:

• A "diff-checker" is, by definition, a program which checks whether a given program p always returns diff(a,b) for all inputs a and b. Prove that prev-checkers do not exist.
• Does there exist a "and-checker" that checks whether the value of and(a,b) is correct for all a and b from the set {true,false}={0,1}?

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:

• A min-plus version of dot product of two vectors a=(a1,...an) and b=(b1,...,bn) is defined as c=min(a1+b1,...,an+bn). Describe how to compute this operation in parallel if we have unlimited number of processors. How many processors do you need? How many steps?
• In general, does this problem belong to the class NC? explain your answer.
• 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?

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.