Computation Theory

Lectures will be delivered live, as timetabled (first lecture is Tuesday 27 Jan). Recordings of the lectures will be available from Moodle after the lecture.

• Lecture notes [pdf containing the material from the lecture slides, plus additional material by Tobias Kohn.
• Lecture slides
1. Lecture 1
• 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:
    • What's a Function
    • The Basic Functions
    • Composition
    • Primitive Recursion
    • Minimisation
  • Some notes on how to use the lambda calculus Y combinator by Chi Ian Tang.