Computation Theory

First lecture is Tuesday, 28 January. Recordings of the lectures will be available from Moodle after each lecture.

• Lecture notes [comt-notes-2023-03-26.pdf updated 2023-03-26], containing the material from the lecture slides, plus additional material by Tobias Kohn.
• Lecture slides [ct_handout.pdf]
  Additional slides./
  • pop_push.pdf
  • re_S0_S1.pdf
  • Why_Y.pdf
• Exercise sheet [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.
  • Some interesting links.
    • Fixed point combinators
    • The lambda calculus
    • Church encodings
    • McCarthy's 91 function
    • SKI combinators
    • Ackermann's function!
    • A short proof that Ackermann's function is not in PRIM
    • Don't forget to donate to Wikipedia!
  • Byron Cook on deciding undecidable problems.
    • The Entscheidungsproblem revisited
    • Automatically Proving That Computer Programs Do What They are Supposed to Do
    • On Making Mathematic Proof a Business
  • 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.