Theory of Computations,
Test 1 for the course
CS 5315, Spring 2012

1-2. Prove, from scratch, that the remainder function a % b is primitive recursive? μ-recursive? To answer the first question, 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. To answer the second question, start similarly with the definition of a μ-recursive function.

3-4. Is every primitive recursive function μ-recursive? Is every everywhere defined μ-recursive function primitive recursive? For each of these questions:

5. Design a μ-recursive function f(a, b) that represent disjunction limited to truth values: f(0, 0) = 0, f(1, 0) = f(0, 1) = f(1, 1) = 1, and f(a, b) is undefined for all other pairs (a, b).

6. Is the union of two decidable sets decidable? If yes, prove; if no, give a counter-example and explain why this is a counterexample.

7. Is the union of two recursively enumerable sets recursively enumerable? If yes, prove; if no, give a counter-example and explain why this is a counterexample.

8-9. Design a Turing machine that computes a function f(n) = n - 1 (in unary code, with bounded subtraction). 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.

10. A student produced a program, and claims that this program always halts. Is there a general way of checking whether this program always halts? If yes, explain how, if no, prove that this is not possible.

11. What is the Kolmogorov complexity of a sequence 100100 ... 100 (repeated 2,012 times)?