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

Name: _____________________________________________________

1. Describe the function f = σ(PR(π22, π43)) in normal terms. For this function f, what is the value f(3, 3, 4)?

2-3. Prove, from scratch, that relations < (less than), = (equal), and <= (less than or equal) are primitive recursive. Start with the definitions of a primitive recursive function, and use only this definition in your proof -- do not use results that we proved in class.

4. Is every primitive recursive function μ-recursive? Is every μ-recursive function primitive primitive recursive? If yes, prove; if no, provide a counterexample and explain why this is a counterexample. For extra credit: As a homework, you proved that not every computable function is Ackermann-primitive recursive, by constructing an auxiliary function f(n) which is computable but not Ackermann-primitive recursive. What if, in addition to 0, πki, σ, and the Ackermann function, we also allow this auxiliary function f(n) in our constructions? Will then every computable function be Ackermann-f-primitive recursive?

5. Design a μ-recursive function f(a, b, c) which is true if all three numbers a, b, and c are equal to each other, false if all three are different, and undefined for all other triples (a, b, c) (i.e., when two of them are equal but the third one is different).

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

7. Prove that if a set S and its complement −S are both recursively enumerable, then the set S is decidable. Based on your proof, answer the following question: if number 7 was generated by the algorithm corresponding to the complement −S at moment 3, when will your algorithm decide whether 7 belongs to the set S?

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

9. Prove that the union of a decidable set and a recursively enumerable set is always recursively enumerable. Is such a union always decidable? If yes, prove it; if no, give a counterexample 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 the n-th prime number.

11-12. Design Turing machines that compute a function f(n) = n + 1 and a function g(n) such that g(0) = 0 and g(n) = n − 1 for all other n. Use the general algorithm for generating a Turing machine for the composition to design a Turing machine that computes the function f(g(n)). Trace this composition Turing machine on the example of n = 1.