Course pages 2019–20
Computation Theory
- Lecture notes (uncorrected version here).
- List of corrections to the notes [pdf].
- Slides [pdf]:
- lecture 1 (16 Jan)
- lecture 2 (21 Jan)
- lecture 3 (23 Jan)
- lecture 4 (28 Jan)
- lecture 5 (30 Jan)
- lecture 6 (4 Feb)
- lecture 7 (6 Feb)
- lecture 8 (11 Feb)
- lecture 9 (13 Feb)
- lecture 10 (18 Feb)
- lecture 11 (20 Feb)
- lecture 12 (25 Feb)
- Exercise sheet.
- 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.