- P. 113, lines 9, 11: C should be C'.
- P. 113, Example 6.7: both occurrences of "\bar{q}p" should be "\bar{p}q".
- P. 118, line 5: The second 1 \leq i \leq 4 should be 1 \leq j \leq 4.
- P. 118, lines -9, -10: The indices for the formulas below i and j should be: (i+1,j+1), (i+1,j+2), (i+1,j+3), (i+1,j-1), (i+1,j-2), (i+1,j-3).
- p. 139, Definition 7.26: The three occurrences of S should be U. (Thanks to Hagit Shatkay.)
- P. 144-145: "\exists\neg xq(x)" should be "\exists x\neg q(x)". This occurs several times because of cut-and-paste :-(. (Thanks to Jørgen Villadsen.)
- p. 144, line 13: "element c such that c \in R_q" should be "element c such that c \not\in R_q". (Thanks to Hagit Shatkay.)
- P. 145, line 6 of Example 7.34: delete the extra parenthesis in "\exists x\neg p(x))". (Thanks to Andreas Schmidt Jensen.)
- P. 203: In Exercise 10, the reference is to the equivalences in Section 7.4.1. (Thanks to Jørgen Villadsen.)
- P. 224: A two-register machine needs an extra instruction such as an unconditional jump; alternatively, three registers can be used. In either case, the modifications to the proof of Church's Theorem are straightforward. The reference (Section 7.8) given in the proof of Theorem 1.2 is to the 1979 edition of Hopcroft and Ullman; in later editions, the proof is in Section 8.5. (Thanks to Thomas Bolander.)
- P. 332, line 6: x, y, z must be non-zero. (Thanks to Johan Öman.)
- P. 332, line 14: \mathcal{R} should be R. (Thanks to Rouven
Walter.) - P. 333, line 10: \mathcal{S}q should be \mathcal{SQ}.
(Thanks to Rouven Walter and Jørgen Villadsen.) - P. 333, line 17: "cardinality of a S" should be "cardinality of a
set S." (Thanks to Rouven Walter.) - P. 335, line 13: \mathcal{S} should be S. (Thanks to Rouven
Walter.) - P. 335, line -10: "consider" should be "considered".(Thanks to Jørgen Villadsen.)
Last update 5 January 2020.