In this appendix we introduce the basic ideas of computability theory (the study of which problems are, and which problems are not, computationally solvable), and provide some background information on complexity theory (the study of the computational resources required to solve problems).

For detailed discussions of computability, see Rogers [391] or Odifreddi [343]. For accessible introductions to the subject, see Boolos and Jeffrey [70], or Cutland [103]. But the single most useful source is probably the (second edition of) Lewis and Papadimitriou [301]; this introduces computability theory, and then goes on to treat computational complexity. For more on computational complexity, try Garey and Johnson [163] and Papadimitriou [352]. Garey and Johnson's book is a source for information on NP-complete problems, but it discusses the basic ideas of computational complexity lucidly, and gives background information on other complexity classes. Papadimitriou's book is a well-written introduction to computational complexity covering far more than is needed to understand Chapter 6; if you want to go deeper into computational complexity, it is a good place to start.

Computability and Uncomputability

To prove theorems about computability — and in particular to prove that some problem is not computable — we need a robust mathematical model of computability. One of the most widely used models is the Turing machine. A Turing machine is a device which manipulates symbols written on a tape. The symbols are taken from some alphabet fixed in advance (often the alphabet simply consists of the two symbols 0 and 1).