Nigel Cutland, Computability: An introduction to recursive function theory, Cambridge University Press, 1980.

再帰関数論の定評ある入門書。素晴らしい本だった。何をどこまで説明して、何を説明しないかや、議論のポイントの示し方がとてもうまい。無味乾燥と言われがちな再帰関数論だが、すんなりと理解できる。不完全性定理も再帰集合の話を介してやれば、当たり前のように帰結するのが見て取れる（numerical representationの話を飛ばしていることもあるが）。再帰関数論にはあまり入門書がないという印象があったが、たしかにこの本があれば十分な気がする。参考文献表が古いのが難ではあるが。