Computability Theory

Course content

Well-formed formulas of Peano arithmetic, Gödel numbering, primitive recursive functions, Gödel’s Incompleteness Theorems, partial recursive functions, Turing machines, Church-Turing Thesis, decidabilitiy, recursion theorem, s-m-n theorem, padding lemma, recursively enumerable sets, computable approximations, halting problem, creative sets, simple sets, Turing reducibility, Turing degrees, properties of Turing degrees, recursively enumerable degrees, joins, Turing jump. Selected topics may include: Arithmetical hierarchy, limit lemma, finite extension method, co-infinite extension method, minimal degrees, splitting threes, jump classes, jump inversion, low and hign degrees, finite injury priority method, r.e. permitting, computable dimination, hyperimmune-free degrees.