On this page, we list some errata that were noticed as we used the text at various times between Fall, 2010 and Fall, 2015. In addition, the author has alerted us to some other errata in the textbook.
Please let me know about additional errors as you discover them. I will share all of these with the author at the end of the semester.
Page 27: The statement of Lemma 5.2, although true, is misleading. The range of the reduction will be {0,1}, but the reduction reduces A to {1}.
Page 64: The notation "|A->B|" 5-7 lines from the bottom of the page, is not clear. The author means to refer to the size of the set of all functions with domain A and co-domain B. That is, one could express this as |{f : A->B}|.
Page 85: The discussion in lines 5-10 is correct if one is considering z_1,...,z_m to be a set. But then the right-hand side of the inequality in line 11 should be (2^m choose m), instead of the number of bitstrings of length m^2. This complicates the exposition somewhat. Simple proofs can be found elsewhere, such as on Wikipedia.
Page 130: Under the list of examples of well-formed terms, the example:
g(f(g(x),c),f(d,g(y)))
should be:
f(f(g(x),c),f(d,g(y)))
Page 142: 7 lines from the bottom of the page, change "and and" to "and".
Page 143: In items (i), (ii), and (iii), the words "a rational number" cannot be justified, unless the k-tuple "a" (as in the statement of Lemma 22.4) is chosen to be a k-tuple of rational numbers, instead of being a k-tuple of reals, as it is currently stated. When Lemma 22.4 is used, in the proof of Theorem 22.6, one can, in fact, restrict attention to rational numbers. One way to correct this is outlined here.
Also, on page 143, 2 lines before the end of the proof of Lemma 22.4, instead of h \in A^k_{2m+1}, it should be h \in A^k_{2m^2}.
Page 148: In the first line of the proof of Lemma 23.1, change "sum" to "given expression".
Page 149: In the first line of the definition of INTDIV_n, replace "I_n(q)" by "I_n(y)". (This is because I_n(y) must hold in order to use the formula MULT_n(u,q,y), which appears in this line.)
Page 149: In the second bullet, change "x,y in I_n" to "y in I_n". (See the comment below about page 152 for an explanation.)
Page 152: In the definition of L_n(x) (line 9), the use of DIV_n is problematic, because as defined informally on page 149, I_n(x) must hold, although in the formal definition on page 149 as REM_n(x,y,0), there is no such restriction on x. The formal definition (as REM_n(x,y,0)) is OK to use here on page 152.
Page 152: 2 lines after (24.1), change "I_n(q)" to "I_n(y)". (See comments above about the definition of INTDIV_n on page 149.)
Page 248: 4 lines before Theorem 37.1, the text refers to the "least" m-degree. There is a minor technical point here; the class of recursive sets consists of three m-degrees. (1) the empty set. (2) \Sigma*, and (3) the degree containing all non-trivial recursive sets.
On page 256, equation 38.1 would be a bit clearer if it was re-arranged, so that it was more obvious which equalities follow immediately from the definitions.
Further down page 256, item (b) is not written clearly. It should state that if there is any n < m such that running \phi_n(n) with oracle A_t halts in t steps, where this computation queries the string x, then continue with the simulation.
Also, in item (c), it would help the reader if the text mentioned that when M_m is "crossed off the list", this means that requirement P_m is satisfied.
Page 291: The statement of Exercise 13 is not quite right. The set {a}* is a language, whereas NSPACE(log n) is a set of languages. Thus the intersection is empty. Instead, the intersection should be with the power set of {a}* (or the problem should be stated in terms of the "unary" languages in DSPACE(log n) and NSPACE(log n).
Page 306: In problem 90, when definining programs in this language, you also need to describe how input and output are provided. I assume that output should be a tuple of some (but not necessarily all) variables.
Pages 319-322: The statement of Problem 2 talks about k-counter automata, but (much of) the solution talks about k-head DFAs.
Page 341: in lines 4 and 7, all occurrences of "k" should be "n".
Page 397: in reference [103], the correct pages are 304-308.