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.
- Undecidability of the halting problem.
lecture 5 (3 Feb) [pdf]
- Turing machines.
- Primitive and partial recursive functions.
- Lambda-Calculus.
lecture 10 (22 Feb) [pdf]
lecture 11 (24 Feb) [pdf]
lecture 12 (1 Mar) [pdf]
- Introduction: algorithmically undecidable problems.
- 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:
- 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.