Math 117b: Computability Theory

Winter 2025

Course Description

Welcome to Math 117! This is a three term course providing an introduction to the basic concepts and results of computability theory and computational complexity theory.

The Fall term will be first devoted to the discussion of various theoretical models of computation, like Turing machines, register machines, Markov algorithms, and recursive functions. We will demonstrate their equivalence and discuss Church's Thesis. Then we will study the basic theory of computable functions and effectively enumerable sets on the integers. We will use this theory to show that certain problems, like the so-called Halting Problem for Turing machines, are undecidable, i.e., cannot be solved algorithmically.

In the Winter term, we will discuss computability in the broader setting of mathematics. Some of the highlights here are a development of the Goedel Incompleteness Theorems, the Boone-Novikov theorem on the undecidability of the word problem for groups, and the basics of the theory of algorithmic randomness. We will also discuss many examples of undecidable problems from logic, number theory, group theory, combinatorics, and computer science. No prior knowledge of any of these subjects is assumed. We will develop all the necessary background.

In the Spring term, we will start with a discussion of decidable problems, i.e., problems for which there are actually algorithms for their solution. Then we will introduce the basic concepts of the theory of computational complexity of algorithms. We will study the concept of feasible (polynomial time) computation and the relationship between deterministic polynomial (P) and nondeterministic polynomial (NP) computations, including NP-complete problems and the famous "P = NP" problem. We will also discuss probabilistic algorithms and derandomization.

Lecture Notes

  1. Lecture 1
  2. Lecture 2
  3. Lecture 3
  4. Lecture 4
  5. Lecture 5
  6. Lecture 6
  7. Lecture 7
  8. Lecture 8
  9. Lecture 9
  10. Lecture 10
  11. Lecture 11
  12. Lecture 12
  13. Lecture 13
  14. Lecture 14
  15. Lecture 15
  16. Lecture 16
  17. Lecture 17

Homeworks

  1. HW1
  2. HW2
  3. HW3
  4. HW4
  5. HW5