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

Name: _____________________________________________________

1. Describe the function f = σ(PR(π11, π33)) in normal terms. For this function f, what is the value f(6, 3)?

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

4. Prove that not every μ-recursive function is primitive recursive.

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

6. Prove that the intersection of two recursively enumerable sets A and B is recursively enumerable. Based on your proof, answer the following question: if a number 6 was generated by the algorithm corresponding to the first set at moment 3 and by the second algorithm at moment 5, when will this number be printed by an algorithm corresponding to the intersection?

7. To prove that the the intersection of two recursively enumerable sets A and B is recursively enumerable, a student proposed the following alternative algorithm: "First, we produce all the elements of A; then, we produce all the elements of B; we compare the two lists and print common elements". Give an example when this algorithm will not work. Hint: sets can be infinite.

8. Prove that the halting set is recursively enumerable. If a program p = 1 halts on data d = 2 at moment t = 3, at what moment of time will the pair (p, d) printed by the corresponding algorithm?

9. Prove that the intersection of a decidable set and a recursively enumerable set is always recursively enumerable. Is such an intersection always decidable? If yes, prove it; if no, give a counter-example and explain why this is a counterexample.

10. Prove that it is not possible, given a program that always halts, to check whether this program always computes n + 2.

11-12. Design a Turing machine that computes a function f(n) = n + 1 in binary code (the number n is written starting with its lowest bit; e.g., 610 = 1102 is written as # 0 1 1 # # ...) 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.