Computability theory is a branch of mathematics concerned with the limits of algorithmic reasoning. It asks a very basic question: What is computable?
Emerging in the 1930s from the independent work of Turing, Church, and Gödel, computability theory arose at a moment when mathematicians were working on the foundations of their field—in particular, Hilbert's Entscheidungsproblem, which sought a mechanical procedure capable of deciding the truth of any mathematical statement within a formal system. The answer, it turned out, was a definitive no.
Through the formalisation of computation—via Turing machines or recursive functions—one can prove that certain problems are undecidable: no algorithm, no matter how clever or powerful, can ever solve them. There are, therefore, provable limits on what machines and indeed human reasoning can achieve, with profound consequences in logic, complexity theory, philosophy of mind, and the theoretical foundations of programming.
The goal of this project is to develop a solid understanding of the theory of computability, transitioning from fundamental principles—which will be largely dealt with in the group project—to some of its applications, in particular in the individual project.
The group project will revolve around learning basic concepts and results in computability theory. By the end of the group project we will have studied the following topics:
The project will revolve around learning through reading with focus on the underlying theory and the development of conceptual understanding. Students will demonstrate their understanding by solving relevant problems, exploring examples and theoretical applications of the material, and clearly communicating it in both written and oral formats.
The individual project will build on the knowledge gained in the group project and will explore additional advanced topics. Potential directions include:
The project will revolve around learning through reading with focus on the underlying theory and the development of conceptual understanding. Students will demonstrate their understanding by solving relevant problems, exploring examples and theoretical applications of the material, and clearly communicating it in both written and oral formats.
The only prerequisite for this project is mathematical maturity—being comfortable with rigorous proof and abstract reasoning of the kind developed in, e.g., Analysis 1.