Computation Theory
- Lecture notes [pdf], containing the material from Andrew Pitts' lecture slides, plus additional material by Tobias Kohn.
- All slides [pdf]
- Slides and videos for individual lectures:
- Introduction: algorithmically undecidable problems.
- Register machines.
- Universal register machine.
lecture 3 (28 Jan) [pdf, video]
lecture 4 (2 Feb) [pdf, video] - Undecidability of the halting problem.
- Turing machines.
lecture 6 (9 Feb) [pdf, video]
lecture 7 (11 Feb) [pdf, video] - Primitive and partial recursive functions.
lecture 8 (16 Feb) [pdf, video]
lecture 9 (18 Feb) [pdf, video] - Lambda-Calculus.
lecture 10 (23 Feb) [pdf, video]
lecture 11 (25 Feb) [pdf, video]
lecture 12 (2 Mar) [pdf, video]
- 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.