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 S^{m}_{n} 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. |