Course catalogue
All courses, including the specialized courses that do not belong to a main track. The search covers titles, summaries, objectives and lesson titles. The learning tracks show the main sequences and their prerequisites.
24 courses
- Models of computationTuring machines, register machines, partial recursive functions and the λ-calculus, and the equivalence of these models.
- Countability and diagonalizationComparison of infinite sets, the Cantor–Bernstein theorem, countable sets, the diagonal argument and the continuum, with their first applications to computation.
- Fundamentals of computabilityThe enumeration of the partial computable functions, the universal function and the SMN theorem, the halting problem and reductions, c.e. sets, Kleene's fixed point theorem and Rice's theorem.
- Oracles and Turing degreesComputation relative to an oracle, Turing reducibility and degrees, the jump, limit computability, the finite extension method, and low and high sets.
- The arithmetic hierarchyClassifying sets by the quantifier complexity of their definitions, Post's theorem linking it to the jump, the classification of index sets, arithmetic definability, and codes for sets.
- Post's problem and the priority methodSimple and creative sets, the Friedberg–Muchnik theorem, a low simple set, and the Sacks splitting theorem, by finite injury priority arguments.
- Π⁰₁ classesComputable trees, König's lemma, computable members of Π⁰₁ classes, the low, computably dominated and cone avoidance basis theorems, PA degrees, and finitely branching trees.
- Kolmogorov complexityThe length of the shortest description of a string, prefix-free machines, the coding theorem, and Chaitin's halting probability.
- Martin-Löf randomnessEffective null sets, the Levin–Schnorr theorem, and the randomness of Chaitin's Ω.
- Second-order arithmeticThe language and models of second-order arithmetic, the base system RCA₀, and the formalization of analysis.
- The Big FiveACA₀, WKL₀, ATR₀ and Π¹₁-CA₀, their ω-models, and the theorems equivalent to each.
- Ramsey's theorem for pairsThe computability-theoretic analysis of Ramsey's theorem, cohesiveness and stable colorings, and Seetapun's theorem.
- Computable ordinalsWell-orders, ordinal notations, the Church–Kleene ordinal ω₁ᶜᵏ, well-founded trees and Π¹₁ sets.
- Hyperarithmetic setsIterating the jump along computable ordinals, Kleene's theorem Δ¹₁ = HYP, and Σ¹₁ classes.
- Cohen genericityEffective forcing with finite strings; weakly generic and n-generic sets, their degrees and their jumps.
- Immunity and growth of functionsImmune and hyperimmune sets, computably dominated degrees, diagonally non-computable functions, and dominant functions.
- Structure of the Turing degreesExact pairs, embeddings of partial orders, and minimal degrees.
- Infinite injury priority argumentsMinimal pairs of c.e. degrees and a high incomplete c.e. degree, by priority arguments on trees of strategies.
- Effective descriptive set theoryNorms on Π¹₁ sets, the reduction and separation properties, Kreisel's uniformization, and the effective perfect set theorem for Σ¹₁ classes.
- K-trivial setsSets of minimal prefix-free complexity, cost functions, and their coincidence with the sets that are low for randomness.
- Notions of randomnessRelative randomness and van Lambalgen's theorem, 2-randomness and weak 2-randomness, Schnorr and Kurtz randomness.
- Higher randomnessRandomness with respect to hyperarithmetic and Π¹₁ null classes, the Sacks–Tanaka theorem and its consequences.
- Induction and conservationThe hierarchy of induction and collection schemes, the pigeonhole principle and Σ⁰₂ collection, and the conservation theorems of Friedman and Harrington.
- Reducibilities between problemsTheorems as problems, compared by ω-reducibility, computable reducibility and Weihrauch reducibility.