Computation Theory 2008–09
Principal lecturer: Prof Andrew Pitts Taken by: Part IB
- Syllabus.
- Lecture notes for printing (2up):
- Front matter (including suggested exercises) [pdf, 120KB]
- Introduction: algorithmically undecidable problems [pdf, 1.5MB]
- Register machines [pdf, 2.1MB]
- A universal register machine [pdf, 2.5MB]
- The halting problem [pdf, 1.2MB]
- Turing machines and the Church-Turing thesis [pdf, 3.0MB]
- Primitive recursive functions [pdf, 2.8MB]
- Partial recursive functions [pdf, 2.9MB]
- Recursive and recursively enumerable sets [pdf, 1.9MB]
- Glossary of mathematical notation and terminology [pdf, 36KB]
- Lecture notes as slides (colour,
landscape). [pdf, 44.7MB]
- List of corrections to the notes
[pdf].
- Past
exam questions.
Comments on the
relevance of recent Tripos questions to the course.
- Scooping the Loop Snooper [pdf,
50KB] (© Mathematical
Acssociation of America), a poetic proof of the
undecidability of the halting problem in the style of Dr Seuss by Geoffrey
K. Pullum.
- Feedback: Please provide feedback through the online lecture course
feedback form.
|