Computation Theory
Lectures will be delivered live, as timetabled (first lecture is Tuesday 23 Jan, not Thursday 18 Jan). Recordings of the lectures will be available from Moodle after the lecture.
- Lecture notes [pdf updated 2023-03-26], containing the material from the lecture slides, plus additional material by Tobias Kohn.
- All slides [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.
- An article about the Church-Turing Thesis in Communications of the ACM.
- Some videos from Hackers at Cambridge explaining partial recursive functions:
- Some notes on how to use the lambda calculus Y combinator by Chi Ian Tang.