Theory of Computations, Test 1 for the courseCS 5315, Spring 2011

1. Prove, from scratch, that the bounded subtraction a -- 3 is primitive recursive. Start with the definition of a primitive recursive function, and use only this definition in your proof -- do not use results that we proved in class.

2. Is every primitive recursive function computable? If yes, prove, if no, give a counterexample. Hint: to prove that something is computable is easy: just show how to compute it.

3. Is every computable function primitive recursive? If yes, prove, if no, give a counterexample.

4. Design a μ-recursive function f(n) that represent negation: f(0) = 1, f(1) = 0, and f(n) is undefined for all n > 1.

5. Is every decidable set recursively enumerable (r.e.)? If yes, prove; if no, give a counter-example.

6. Is every r.e. set decidable? If yes prove, if no, give a counterexample.

7-8. Design a Turing machine that computes a function f(n) = n + 1 (in unary code). Use the general algorithm for generating a Turing machine for the composition to design a Turing machine that computes the function f(f(n))= f(n) + 1 = (n + 1) + 1= n + 2.

9. A student produced a program that claim to provide a new way of computing n3 + n. He has proven that this program always halts. Is there a general way of checking whether this program always produced the correct result? If yes, explain how, if no, prove that this is not possible.

10. What is the Kolmogorov complexity of a sequence 001001 ... 001 (repeated 10,000 times)?