Test 1 for the course

CS 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 n^{3} + 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)?