Topics in Logic: Computability Theory

This class was run at the University of Colorado Boulder in the Spring of 2011. It was a class for advanced graduate students.

We studied the basics of computability theory with an aim to finish with some nice priority arguments. We used a draft of the new book by Robert Soare; this was distributed during the first week of classes.

Lecture 1 We introduce Turing Machines.
Lecture 2 We answer the question how a Turing Machine that works on tapes can compute anything we might care about. (some common conventions and coding ideas are discussed) We also introduce the Church-Turing thesis. We then end with Oracle machines.
Lecture 3 We briefly discuss the lambda-calculus, then define Turing degrees and make some elementary observations.
Lecture 4 We talk about a Universal Turing Machine, the Smn theorem, and then we show the unsolvability of the halting problem.
Lecture 5 We did a 1-1 reduction of the halting problem to the set of indices for total functions, followed by some equivalences on definitions for c.e. sets and basic properties.
Lecture 6 We proved and discussed some consequences of the recursion theorem.
Lecture 7 We discussed an index theorem for finite sets, and started discussion of productive and creative sets.
Lecture 8 Properties of creative and productive sets, and start of discussing the Friedberg splitting theorem.
Lecture 9 We discuss the proof of the Friedberg Splitting Theorem and some basic notions around oracle machine.
Lecture 10 Basic facts on oracle machines and the jump.
Lecture 11 Characterising sets below 0'.
Lecture 12 Modulus Lemma and beginning topology.
Lecture 13 We proved compactness of Cantor space and beginning effective topology (effective open/closed sets).
Lecture 14 We talk about the effective compactness theorem and the low basis theorem.
Lecture 15 We discuss the arithmetical hierarchy, how to prove something occurs at a certain level, and Posts theorem. We finish by showing Cof is Σ3 complete by a movable marker construction.
Lecture 16 We finish the movable marker construction we started during the last lecture, then do the high domination theorem.
Lecture 17 We discuss (effectively) simple sets (definition and existence)
Lecture 18 We talked about permitting, and then hyper(hyper) simple sets.
Lecture 19 We talked more about hypersimple sets, that effectively simple sets are complete, and finished with Arslanovs Completeness Criterion.
Lecture 20 We discussed two constructions using oracles and extending initial segments, first an incomparable pair below 0', then a minimal pair of degrees.
Lecture 21 We proved the jump is onto the cone above 0', and the existence of exact pairs for strictly ascending sequences of degrees.
Lecture 22 We started working on proving the existence of a minimal degree below 0''.
Lecture 23 We finished the proof of the existence of a minimal degree.
Lecture 24 We did the first finite injury proof, showing the existence of a low simple set.
Lecture 25 We proved the existence of incomparable c.e.sets, discussed a little what this would look like on a tree, and started the proof that we can construct a simple set outside of the upper cone determined by any noncomputable c.e.set.
Lecture 26 We discuss two length of agreement arguments.
Lecture 27 An introduction to Infinite Injury and the Thickness Lemma.
Lecture 28 Start of the proof of the thickness lemma.
Lecture 29 We finish the proof of the Thickness Lemma and start with Jump Inversion.
Lecture 30 We finish the Jump Inversion Theorem.
Lecture 31 We worked on the Density Theorem.
Lecture 32 We finished discussion of the Density Theorem.