Home
Computability notes
These handouts were used in a course I gave at Birmingham University in the winter term of 2014. They provide skeletal notes for an introduction to computability and complexity theory.
Whilst they are fit for purpose for mathematics students, they do not cover a number of topics essential for computer science students. In particular, I would recommend a CS student using these notes to supplement them with material on regular languages and finite state automata, push down automata and context-free languages. These will give exposure to models of computation weaker than Turing machines, and demonstrate the stratified nature of computation. Furthermore, Random Access Machines and the lambda calculus, in addition to demonstrating models of computation equivalent to Turing machines, are closely related to real computers in the case of the former, and closely related to functional programming in the case of the latter.