Computer Laboratory
Computation Theory
Computer Laboratory
>
Course material 2006-07
>
Computation Theory
Computation Theory
2006-07
Principal lecturer:
Prof Andrew Pitts
Taken by:
Part IB
,
Part II (General)
,
Diploma
Syllabus
.
Lecture notes for printing (2up):
Front matter (including suggested exercises) [
pdf
, 125KB]
Introduction: algorithmically undecidable problems [
pdf
, 1.5MB]
Register machines [
pdf
, 1.9MB]
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.9MB]
Partial recursive functions [
pdf
, 2.9MB]
Recursive and recursively enumerable sets [
pdf
, 1.9MB]
Glossary of mathematical notation and terminology [
pdf
, 36KB]
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
.
