Computability, Unsolvability, Randomness Math 497A: Questions for the Oral Final Exam

Stephen G. Simpson

December 10–14, 2007

Each student will undergo a 1-hour oral final exam. The exam will consist of one QUESTION, one PROBLEM, and a brief report on the student’s research project. The QUESTIONS will be chosen from the list below. The PROBLEMS will be similar to homework problems or midterm exam problems.

1. Briefly explain oracle programs, partial recursive functionals, and the idea of finite approximation. Explain why the domain of a partial recursive functional Φ : ⊆ ℕ^{ℕ} → ℕ is necessarily an open set in ℕ^{ℕ}.

2. State the Parametrization Theorem in its most general form. State and prove some instances of the Uniformity Principle. For instance, give a precise statement and proof of the Uniformity Principle as it applies to the union of two Σ_{1}^{0} sets in ℕ or in ℕ^{ℕ}.

3. Give a precise statement of Matiyasevich’s Theorem, related to unsolvability of Hilbert’s 10th Problem. Give a precise statement of the Boone/Novikov Theorem, related to unsolvability of the word problem for groups. What can you say about the degrees of unsolvability of these problems?

4. Explain what it means for a real number to be recursive, or left recursively enumerable, or right recursively enumerable. State and prove the relationships among these classes of real numbers. Present some relevant examples.

5. Consider mixed predicates P ⊆ (ℕ^{ℕ})^{m} × (2^{ℕ})^{l} × ℕ^{k}. Define precisely what it means for a mixed predicate to be recursive, or to belong to one of the classes Σ_{n}^{0} or Π_{n}^{0} in the arithmetical hierarchy. State the main closure properties of these classes. State the Magic Lemma.

6. Explain what it means for a set to be many-one complete within one of the classes Σ_{n}^{0} or Π_{n}^{0} in the arithmetical hierarchy. Give examples of such sets. Explain the relevance of creative sets and simple sets.

7. If C is any class of 1-place partial recursive functions, let I_{C} be the set of indices of functions belonging to C. In other words,

I_{C} = {e ∈ ℕ | φ_{e}^{(1)} ∈ C} .

The set I_{C} is known as an index set. Give some interesting examples of index sets, and classify them in the arithmetical hierarchy.

8. Define precisely the Turing jump operator. Review some properties of the Turing jump operator which we have discussed in the course. State Post’s Theorem and the Jump Inversion Theorem. To what extent is the Turing jump operator order preserving?

9. Use the method of finite approximation to construct two degrees of unsolvability (i.e., Turing degrees) a and b such that inf(a, b) = 0 and sup(a, b) = 0′ and a and b are incomparable.

10. Give an overview of the structure of the degrees of unsolvability, i.e., the Turing degrees. Your overview should include the following features: least upper bounds, greatest lower bounds, relativization, properties of the jump operator, initial segments, final segments.

11. As you know, a recursively enumerable set is the same thing as a Σ_{1}^{0} subset of ℕ. What kinds of recursively enumerable sets are you familiar with? Discuss creative sets and simple sets. Give two different kinds of examples of simple sets.

12. Define precisely what is meant by the Kolmogorov complexity of a bitstring, a.k.a., “plain” complexity. Prove that the complexity of a bitstring is well-defined up to an additive constant.

13. Define precisely what is meant by the prefix-free complexity of a bitstring. Compare and contrast prefix-free complexity with “plain” Kolmogorov complexity. What inequalities hold among them?

14. State and prove some inequalities involving the complexity of bitstrings. For instance, what can you say about the complexity of σ^{⌢}τ in terms of the complexity of σ and the complexity of τ? What about relationships between the complexity of τ and the length of τ?

15. Define precisely what is meant by a test for randomness, in the sense of Martin-Löf. Define Martin-Löf’s concept of randomness. Compare Martin-Löf’s concept with some alternative concepts of randomness.

16. Compare and contrast the following concepts: weak randomness, randomness, strong randomness, 2-randomness, n-randomness.

17. State some statistical properties enjoyed by sequences of 0’s and 1’s which are random in the sense of Martin-Löf. Sketch how to devise tests for randomness corresponding to these statistical properties.

18. Define precisely the concept of a universal test for randomness. State and prove some interesting consequences of the existence of a universal test for randomness.

19. State Schnorr’s Theorem relating randomness to initial segment complexity. Prove at least one direction of Schnorr’s Theorem. Show how Schnorr’s Theorem gives rise to a universal test for randomness.

20. State van Lambalgen’s Theorem concerning relative randomness. Prove at least one direction of van Lambalgen’s Theorem. Show how van Lambalgen’s Theorem implies the existence of a pair of incomparable Turing degrees.

21. Explain in general what is meant by a basis theorem. State precisely the Low Basis Theorem and the Hyperimmune-Free Basis Theorem. State precisely some “anti-basis” theorems, i.e., theorems to the effect that our basis theorems are best possible.

22. State the Kučera/Gács Theorem. Generally speaking, what can you say about the Turing degree of a random sequence of 0’s and 1’s? Which Turing degrees contain random sequences, and which ones do not?

23. What can you say about the relationship between relative prefix-free complexity and relative randomness? What about Turing reducibility versus LR-reducibility versus LK-reducibility?