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

1) Prove that the power function a^n is primitive recursive.

2) In class, we proved that if the predicate P(n) and the functions f(n) and g(n) are primitive recursive, then the function

if P(n) then f(n) else g(n)
is also primitive recursive. 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.

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

4) Prove that the following function is mu-recursive: f(1)=2, f(2)=3, and f(n) is undefined for all other n.

5) Since every primitive recursive function is mu-recursive, and we know that division is primitive recursive, we can thus conclude that division is mu-recursive. For subtraction, in class, we came up with a simpler proof that subtraction is mu-recursive. Produce a similar simplified proof that integer division is mu-recursive.

6) Our objective is to describe computable functions. In class, we proved that there exists a function which is computable but not primitive recursive. One example of such function is the Ackermann function A(n). What if instead of adding a new construct (mu-recursion, which corresponds to while loop), we add this new function A(n) to the list of basic function, will be get all computable functions? In other words, what if we define a new notion of an A-primitive recursive function as a function which can be obtained from 0, sigma, pi, and A(n) by using composition and primitive recursion. Modify our proof to show that there exists a computable function which is not A-primitive recursive.

7) Design a Turing machine for computing the previous natural number (in unary notation).

8) Design a Turing machine for computing pi^2_2, a function which, given a pair of natural numbers, returns the second number from this pair.

9) Design a Turing machine for computing pi^3_2, a function which, given a triple of natural numbers, returns the second number from this pair.

10) Reproduce the proof that halting problem is algorithmically undecidable.

11) Let us call a program a square-checker if, given an arbitrary program p, it checks whether this program p always returns the square n^2 of the input n. Prove that square-checkers do not exist.

12) Take a propositional formula of at least 3 variables and use the algorithms described in class to convert it to CNF and DNF.

13) In class, we traced the general proof that satisfiability is NP-hard on a simple example in which we have one input bit x, one output bit y, and the desired relation is x = y. Trace the same proof on an example where we have a different desired relation between the input and output bits.

14) Reproduce the proof that we had in class, that the main problem of interval computations is NP-hard.

15) Use calculus-based techniques to find the range of a function of two variables that we had in class: f(x1,x2)=(1-x1+x1*x2)*(1-x2+x1*x2), when both x1 and x2 are in [0,1].

16) Take an example of a propositional formula and show how it can be reduced to the problem of finding a clique in a graph.

17) Take an example of a propositional formula and reduce checking its satisfiability to checking 3-coloring problem.

18) Take an example of a formula in CNF and reduce checking its satisfiability to checking satisfiability of a 3-CNF formula.

19) Prove that 4-coloring is NP-hard. Hint: this problem can be reduced to 3-coloring.

20) Take an example of a propositional satisfiability problem and reduce it to the corresponding example of a subset problem.

21) Show how to compute the product of 16 numbers in parallel; describe how many processors we need and how much time we spend.

22) Show how to multiply two 4 x 4 matrices in parallel; describe how many processors we need and how much time we spend.