CS 5315, Final Exam, Spring 2007

Name

(Please do not forget to put your name on all extra sheets of paper)

1. Primitive recursive functions
(a) Prove, from scratch, that the functions a * b + c, 1 - a (funny minus that never goes below 0), "a or b", and "not a" are primitive recursive.

(b) Start by giving a definition of a primitive recursive function, and explain how your procedure for 1 - a fits this general definition.

(c) The notion of a primitive recursive function is a formalization of the for-loop. Translate your description of 1 - a into a program that uses for-loop(s) to compute the product.

2. Mu-recursive functions
(a) Prove that the functions a * b + c, 1 - a, "a or b", "not a", and a function that is defined only for n = 1 and is equal to 0 for this n are mu-recursive.

(b) Start by giving a definition of a mu-recursive function, and explain how your procedure for computing a partly defined function fits this general definition.

(c) Since a - 1 is an inverse operation to a + 1, it may seem reasonable to define a - 1 as the following expression: mu m.(m + 1 = a). Describe this expression in English and as a while loop, and show, step by step, what happens when we try to compute this expression for a = 0.

3. Turing machines (TM)
(a) Describe a TM that computes n1 + n2 + n3.

(b) Trace your TM for n1 = 1, n2 = 1, and n3 = 1.

(c) Use your TM to design a new TM for computing composition (n1 + n2 + n3) + n4 + n5.

4. Computability in general
(a) Is every computable function primitive recursive? Explain your answer (no need to produce a detailed proof).

(b) Is every computable function mu-recursive? explain your answer. Formulate Church-Turing thesis. Is it a mathematical theorem? a statement about the physical world? can it turn out to be false?

(c) Prove that the halting problem is undecidable.

```

```
5. Decidable and r.e. sets
(a) Prove that the union and intersection of two decidable sets and a complement to a decidable set are decidable.

(b) Prove that the union and intersection of two r.e. sets are r.e.

(c) Is the complement to a r.e. set always r.e.? Explain your answer.

6. Kolmogorov complexity
(a) What is Kolmogorov complexity? Give an exact definition.

(b) Estimate the Kolmogorov complexity of a string 101101...101 (101 repeated 2,006 times). For extra credit: prove that Kolmogorov complexity is not computable.

7. NP
(a) Define what it means for a problem to be from the class P, from the class NP, to be NP-hard.

(b) Use a general algorithm to transform a Boolean expression 0.9*x1+0.3*x2<0.2+4.6*x1 into DNF and CNF forms.

(c)-(f) Reduce the satisfiability problem for the formula (x1 \/ x2) & (x1 \/ x2 \/ -x3) to:
(c) 3-coloring
(d) clique
(e) subset problem
(f) interval computations.

8. Parallelism
(a) Describe, step by step, how to compute the a1*...*an of n given numbers in parallel.

(b) Does this problem belong to the class NC? explain your answer.