Computation Theory

Lectures will be delivered live, as timetabled (first lecture is Tuesday 24 Jan, not Thursday 19 Jan).

• Lecture notes [pdf updated 2023-03-26], containing the material from Andrew Pitts' lecture slides, plus additional material by Tobias Kohn.
• All slides [pdf]
• Slides for individual lectures:
  • Introduction: algorithmically undecidable problems.

    lecture 1 (24 Jan) [pdf]

  • Register machines.

    lecture 2 (26 Jan) [pdf]

  • Universal register machine.

    lecture 3 (31 Jan) [pdf]
    lecture 4 (2 Feb) [pdf]

  • Undecidability of the halting problem.

    lecture 5 (7 Feb) [pdf]

  • Turing machines.

    lecture 6 (9 Feb) [pdf]
    lecture 7 (14 Feb) [pdf]

  • Primitive and partial recursive functions.

    lecture 8 (16 Feb) [pdf]
    lecture 9 (21 Feb) [pdf]

  • Lambda-Calculus.

    lecture 10 (23 Feb) [pdf]
    lecture 11 (28 Feb) [pdf]
    lecture 12 (2 Mar) [pdf]

• Exercise sheet [pdf]
• Additional material:
  • Scooping the Loop Snooper (© Mathematical Association of America), a poetic proof of the undecidability of the halting problem in the style of Dr Seuss by Geoffrey K. Pullum.
  • A real Turing machine.
  • Some videos from Hackers at Cambridge explaining partial recursive functions:
    • What's a Function
    • The Basic Functions
    • Composition
    • Primitive Recursion
    • Minimisation
  • An article about the Church-Turing Thesis in Communications of the ACM.
  • Some notes on how to use the lambda calculus Y combinator by Chi Ian Tang.