Course pages 2018–19
Computation Theory
- Lecture notes.
- Slides [pdf]:
- lecture 1 (17 Jan)
- lecture 2 (22 Jan)
- lecture 3 (24 Jan)
- lecture 4 (29 Jan)
- lecture 5 (31 Jan)
- lecture 6 (5 Feb)
- lecture 7 (7 Feb)
- lecture 8 (12 Feb)
- lecture 9 (14 Feb)
- lecture 10 (19 Feb)
- lecture 11 (21 Feb)
- lecture 12 (26 Feb)
- Exercise sheet.
- Additional material:
- On-line tools from Robert Kovacsics: a register machine emulator an a lambda calculus interpreter.
- 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:
- A recent article about the Church-Turing Thesis in Communications of the ACM.