Learn Computability Theory

Above the halting problem: the primitive recursive schemes and why Ackermann escapes them, minimisation and the mu-recursive functions, register machines, Godel numbering and the universal machine, the s-m-n and recursion theorems, index sets and Rice-Shapiro, creative, productive and simple sets, the classification of TOT, FIN and COF in the arithmetical hierarchy, Post's problem and the finite-injury priority method, the Shoenfield limit lemma, and the concrete undecidable problems: Post correspondence, the domino problem, Hilbert's tenth, Presburger arithmetic and the busy beaver.

Free to start · adaptive placement finds your level · reviews timed so it stays learned.

What you'll learn

18 lessons in Computability Theory

The primitive recursive schemesAckermann's functionMinimisation and the mu-recursive functionsRegister machinesGodel numbering and the universal machineThe s-m-n theoremKleene's recursion theoremIndex sets and Rice-ShapiroCreative sets, productive sets, and Myhill's theoremPost's simple setsTOT, FIN and COF in the arithmetical hierarchyPost's problem and finite injuryThe Shoenfield limit lemmaThe Post correspondence problemWang tiles and the domino problemHilbert's tenth problemPresburger arithmeticThe busy beaver function

How Erudia teaches

Built to be understood — and remembered.

Every idea is taught with motivation and a worked example before the drills, and an FSRS spaced-repetition engine schedules each review for the moment just before you'd forget it. A short placement check finds what you already know, so you start Computability Theory exactly where it's useful.

Start Computability Theory →