Computability, Turing Machines, and Gödel's Incompleteness Theorems

This course is an introduction to computability theory and Gödel's incompleteness theorems.

The first half of the course will focus on computability theory, and will include: Recursive and primitive recursive functions, Turing machines and computable functions, basic results in computability theory including Kleene's Normal Form Theorem, the s-m-n Theorem, Kleene's Recursion Theorem, Recursively enumerable sets, the halting problem and decision problems in general. If time allows, we'll also look at hierarchy theory, relative computability, and Turing degrees.

The second part of the course will focus on Gödel's first incompleteness theorem, and will include: Axiom systems for number theory, representable relations and functions, arithmetization of syntax, the Fixed-Point Lemma, and Gödel's first incompleteness theorem. If time allows, we'll also look at Gödel's second incompleteness theorem.

During the last 3 weeks of the course, the participants will work on an invidivual written project on a topic related to the course content described here. The lecturer will help the students find a relevant topic to focus on for the project part.