Computation Theory

Lectures will be delivered live, as timetabled. Recorded lectures will become available under the Recordings tab shortly after each live lecture.

• Lecture notes [pdf], containing the material from Andrew Pitts' lecture slides, plus additional material by Tobias Kohn.
• List of corrections to the slides [pdf]
• All slides [pdf]
• Slides and videos for individual lectures:
  • Introduction: algorithmically undecidable problems.

    lecture 1 (20 Jan) [pdf]

  • Register machines.

    lecture 2 (25 Jan) [pdf]

  • Universal register machine.

    lecture 3 (27 Jan) [pdf]
    lecture 4 (1 Feb) [pdf]

  • Undecidability of the halting problem.

    lecture 5 (3 Feb) [pdf]

  • Turing machines.

    lecture 6 (8 Feb) [pdf]
    lecture 7 (10 Feb) [pdf]

  • Primitive and partial recursive functions.

    lecture 8 (15 Feb) [pdf]
    lecture 9 (17 Feb) [pdf]

  • Lambda-Calculus.

    lecture 10 (22 Feb) [pdf]
    lecture 11 (24 Feb) [pdf]
    lecture 12 (1 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.