THEORY OF COMPUTATION
Homeworks for the course CS 5315, Spring 2007

1) Prove that if the predicates P(n) and Q(n) and the functions f(n), g(n), and h(n) are primitive recursive, then the function

if P(n) then f(n) elseif Q(n) then g(n) else h(n)
is also primitive recursive.

2) Prove that remainder is primitive recursive.

3) (for extra credit) Prove that division is primitive recursive.

4) Write down, in detail, the proof that there exists a computable function which is not primitive recursive (the proof that we had in class).

5) Prove that the following function f(n) is mu-recursive: f(n) = 1 if n is even, and undefined otherwise.

6) Use mu-recursion to get a simple proof that the integer division is mu-recursive.

7) Design a Turing machine for computing the the function sigma(n) = n + 1.

8) For extra credit: Design a Turing machine for computing pi^2_1, a function that takes a pair (n1,n2) and returns the first component of this pair.

9) Design a Turing machine for computing pi^3_2, a function that takes a triple (n1,n2,n3) and returns the second component of this triple.

10) For extra credit: Use a general algorithm for designing Turing machine for computing a composition of two functions to produce a Turing machine for computing sigma(sigma(n)) = n + 2.

11) Let A(n) denote an Ackermann function. Let us define an A-primitive recursive function as any function that can be obtained from 0, projections pi, and the function sigma(n) = n + 1 by using composition and primitive recursion. Prove that there exists a computable function which is not A-primitive recursive.

12) Use our proofs that zero-checkers and square-checkers do not exist to prove that cube-checkers do not exist.

13) Once we fix an oracle O, we can define algorithm relative to this oracle, and we can define O-decidable and O-r.e. sets if we use O-algorithms instead of regular algorithms. Check which of the results we had in class about decidable and r.e. sets can be extended to O-decidable and O-r.e. sets.

14) Report on the progress of your project.

15) For extra credit: show to covert a given formula into CNF and DNF.

16) Illustrate the proof that satisfiability is NP-hard on a simple example which is different from what we had in class.

17) For the following 4 problems, illustrate reductions to Satisfiability on simple examples which are different from what we had in class: clique, interval computations, 3-coloring, and subset sum.

18) Describe, step by step, how we can multiply two 4 by 4 matrices in parallel if we have an unlimited number of processors.

19) For extra credit: solve problems from last year's Test 2.