Recursion Theory 2003/2004; 1st Semester Institute for Logic, Language & Computation Universiteit van Amsterdam

This course will cover the basic notions of computability: Turing machines, recursivity and computer programs. The Equivalence Theorem will lead to Church's Thesis. Having a formalization of computability allows us now to investigate the boundaries of computation: what problems are not computationally solvable? This question will lead us to Turing's Halting Problem and the Decidability. We discuss several notions of recursion theoretic reducibility, their derived degree structures, and mathematical properties of these structures.

We shall mostly follow Part A of the textbook

• Recursive Functions (Soare, Chapter I): Primitive Recursive Functions, Turing Machines, Kleene Normal Form Theorem, Enumeration Theorem, s-m-n Theorem, The Halting Problem, Reducibilities, Rice's Theorem, Myhill's Isomorphism Theorem
• Fundamentals of Recursively Enumerable Sets (Soare, Chapter II): Basic Properties, Indices, The Recursion Theorem, Completeness
• Turing Reducibility (Soare, Chapter III): Relative Computability, Turing Degrees, the Jump operator, Delta⁰₂ sets
• The Arithmetical Hierarchy (Soare, Chapter IV): Definitions and Techniques, Post's Theorem, the Hierarchy Theorem, Sigma⁰_n complete sets, the relativized arithmetical hierarchy
• Gödel's Incompleteness Theorem

Topics covered so far:

• 1st Lecture (September 11, 2003). Basics of the history of computing. Alternative models of computation. Primitive recursive functions. The diagonalization theorem. (Up to p.10 in Soare's book.)
• 2nd Lecture (September 18, 2003). The mu operator. Recursive functions. Derivations of recursive functions. Turing machine architecture. Coding of the Turing machine architecture as natural numbers. (Up to p.14 in Soare's book.)
• (September 25, 2003). Cancelled due to illness.
• 3rd Lecture (October 2nd, 2003). Equivalence of recursive and Turing-computable functions. Padding Lemma. Kleene Normal Form Theorem. Enumeration Theorem. s-m-n Theorem. (Up to p.16 in Soare's book.)
• 4th Lecture (October 9th, 2003). Recursively enumerable sets. The Halting Problem. Undecidability of the Halting Problem. Recursion-theoretic reductions. 1-degrees and m-degrees. Index sets. Rice's Theorem. (Up to p.21 in Soare's book.)
• 5th Lecture (October 16th, 2003). Structure of the 1-degrees and m-degrees. Myhill's Isomorphism Theorem. Co-r.e. sets. Finite approximations. The degrees of Inf and Fin. The Recursion Theorem. (Completing Chapter I, with some parts of II.1 and II.3.)
• (October 23rd, 2003). Exam week. No classes.
• 6th Lecture (October 30th, 2003). Proof of the Recursion Theorem. The formal language of arithmetic and its Gödelization. Sigma⁰₁ and recursive enumerability. Uniformization Theorem. (Pages 27-29 and 60-61 in Soare's book.)
• 7th Lecture (November 6th, 2003). Listing Theorem. Reduction Principle for r.e. sets. Provability. Complexity of Truth. Gödel's First Incompleteness Theorem. (Pages 29-30 in Soare's book plus additional material.)
• 8th Lecture (November 13th, 2003). Upper complexity bounds for concrete sets. Relative computation. Turing reducibility. Oracle machines. (Pages 61-63 and pages 46-48 in Soare's book.)
• 9th Lecture (November 20th, 2003). Relativized Normal Form Theorem. Relativized Enumeration Theorem. Relativized s-m-n Theorem. Finite Approximations to oracles. Use Principle. Master Enumeration Theorem. The upper-semilattice of Turing Degrees. The upper-semilattice of r.e. degrees. (Pages 48-50 and pages 52-53 in Soare's book.)
• 10th Lecture (November 27th, 2003). Relativized Normal Form Theorem for Sigma⁰₁ sets. Jump Theorem. The jump operator on the Turing degrees. (Pages 53-54 in Soare's book.)
• 11th Lecture (December 4th, 2003). Relativized Arithmetical Hierarchy. Post's Theorem. Hierarchy Theorem. Equivalence of Fin and 0''. High and low degrees. (Pages 64-66 and 69-71 in Soare's book.)
• 12th Lecture (December 11th, 2003). Productive Sets. Immune Sets. Simple Sets. Post's Problem. Post's Solution. (Pages 40-43 and 77-78 in Soare's book.)
• (December 18th, 2003). Exam week. No classes.

Homework:

• Homework Assignment #1 (Primitive recursive functions). Deadline: September 18th, 2003. Soare, Exercises I.2.4 and I.2.7 (p.13).
• Homework Assignment #2 (Turing Machines). Deadline: September 25th, 2003. Soare, Exercises I.2.9 and I.2.10(b) (p.13/14).
• Homework Assignment #3 (Kleene's Basic Results). Deadline: October 9th, 2003. PDF-File.
• Homework Assignment #4 (1-degrees and m-degrees). Deadline: October 16th, 2003. Soare, Exercises I.4.17, I.4.18, and I.4.23 (a)-(b) (p.22/23).
• Homework Assignment #5 (Unsolvable problems and the Recursion Theorem). Deadline: October 30th, 2003. PDF-File [including Soare, Exercises I.4.24 and I.4.27 (p.23)].
• Homework Assignment #6 (Separability and recursive images and preimages). Deadline: November 6th, 2003. Soare, Exercises I.4.22(a) (p.23), II.1.17 and II.1.23 (p.32).
• Homework Assignment #7 (Coding language into arithmetic). Deadline: November 13th, 2003. PDF-File.
• Homework Assignment #8 (Calculating complexities). Deadline: November 20th, 2003. Soare, Exercises IV.1.10 and IV.1.12 (p.63).
• Homework Assignment #9 (Turing degrees). Deadline: November 27th, 2003. Soare, Exercises III.2.6 and III.2.7 (p.54-55).
• Homework Assignment #10 (The Turing jump). Deadline: December 4th, 2003. PDF-File.
• Homework Assignment #11 (High and Low degrees). Deadline: December 11th, 2003. Soare, Exercises IV.4.5 (a) and (b) and IV.4.6 (b) (p.72).

Extra Credit Assignments:

The idea of Extra Credit Assignments is to give you an opportunity to develop mathematical ideas of your own beyond the limited scope of a homework exercise. They are vaguely formulated and give you the chance to develop the proper definitions needed to prove the desired results.

The extra credit assignments are supposed to be an exercise in mathematical writing as well, so please try to hand them in in the style of textbook mathematics: definitions, lemmas, claims and theorems should be clearly marked as such, proofs should be marked by the word ``Proof'' and some marker that tells the reader that the proof is finished. LaTeXed solutions are strongly preferred for the extra credit assignments.

Extra Credit Assignments have no effect on the question whether you pass or fail the course. They can have a positive effect on your final grade, though.

• Extra Credit Assignment #1 (Primitive recursive functions). Deadline: Thursday, October 16, 2003. In an informal way, primitive recursive relations are ``closed under propositional connectives''. Give a formal definition of that notion and prove the corresponding theorem.
• Extra Credit Assignment #2 (WHILE computability). Deadline: Tuesday, October 28, 2003. You hear very often that recursive functions are equivalent to something called ``WHILE computability'' (referring to an unbounded search loop in usual programming languages). Give a proper formalization of WHILE computability by inventing a syntax for an artificial programming language and prove that this notion is equivalent to recursiveness.
• Extra Credit Assignment #3 (Relativized Normal Form Theorem). Deadline: Thursday, December 4, 2003. Develop a coding of oracle machines as natural numbers and a relativized Kleene T-predicate and prove the relativized Normal Form Theorem. If you don't like Soare's version of oracle machines, feel free to give your own definition, but make sure that you properly state it before you start the formalization. If you're interested, you can go on and use your version of the Normal Form Theorem to prove the relativized Enumeration Theorem and the relativized s-m-n Theorem.

Written Exam. The following is a possible written exam designed for 120 to 180 minutes. If you want, you can do it for training purposes: PostScript File.