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:
 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.
Name:
_______________________________________________________________________
ID #:
_______________________________________________________________________
13. Primitive recursive functions:
 What is a primitive recursive function?
 Prove, "from scratch" (i.e., using only the
definitions), that the functions
prev(n) (n1 if n>0 and 0 otherwise),
diff(a,b) (ab 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 forloop. Reformulate your expression for
addition in terms of primitive recursion
by using forloops (if necessary, embedded forloops).
4. Are the functions "prev", "diff", and "and"
murecursive? 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)) (n2 if n>1 and 0 otherwise).
78. 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.
910. 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.
Turn over,
please.
1112. NPhard:
 Define what it means for a problem to be from the class
P, from the class NP, to be NPhard.
 Formulate the problems about
which we proved NPhardness: satisfiability, interval computations,
3coloring.
1314. Checking program correctness:

A "diffchecker" 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 prevcheckers do not exist.
 Does there exist a "andchecker" 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^20.3*x2>0.2 into DNF and CNF forms.
1719. Parallelization:
 A minplus 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
NPhard?
20. Describe, in detail,
one possible physical way of solving
satisfiability (and other NPhard problems) in polynomial time: using
acausal processes (time machines), using curved spacetime, 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.