# The Theory of Computation

## ADDITIONAL ERRATA FOR THE FIRST PRINTING

Note that these errata apply to the first printing only; all are corrected in the second printing, which came out in December 1997.
• Front matter, List of Notations, p. xiv, first two lines: the up arrow and down arrow are reversed; an up arrow indicates divergence and a down arrow convergence.
• Chapter 2:
• p. 26, second paragraph, 3 lines from bottom of paragraph:
cL: L -> {0,1} should be cL: Sigma* -> {0,1}
• p. 30, Figure 2.9:
the first row of numbers inside the frame reads 1 2 3 4 but should read 1 2 4 7
• Chapter 3:
• p. 56, middle of the paragraph:
The statement "in particular, the empty state is always unreachable" makes the implicit assumption that every state in the automaton has at least one defined transition. If the automaton has a state reachable from the start state and with no defined transition, then the conversion will create a deterministic automaton where the empty state is reachable.
• p. 61, last line, and p. 62, first three lines:
parts (i) and (ii) are reversed.
• p. 69, first and second paragraphs:
the words "vertex" and "vertices" should be replaced by "state" and "states"
• p. 75, third paragraph, 6 lines from bottom of paragraph:
"Although L2 does not need it" should read "Although L6 does not need it"
• p. 88, Exercise 3.13 should be starred.
• p. 90, Exercise 3.22 should not be starred, but Exercise 3.24 should be.
• Chapter 4:
• p. 113, middle of the page. The division requires time proportional to the square of the number of digits of the operand and thus also to the square of the space used by the Turing machine. The second relationship below that should then read
TimeRAM=O(TimeTM*Space2TM)
• p. 114, first paragraph, just before polynomial relatedness:
to clarify, add to the end of the previous sentence
(unless the machine is oversimplified, as in a RAM limited to incrementing)
• p. 119, Exercise 4.19:
• Chapter 6:
• p. 177, middle paragraph, 8 lines from the bottom of the paragraph:
• p. 179, item numbered "4.", second line:
• p. 186, first line below Theorem 6.3:
"for deterministic space" should read "for deterministic time"
• p. 187, Section 6.2.2, penultimate sentence of first paragraph:
• p. 188, first paragraph, second and fourth lines:
• p. 190, fifth line:
• p. 198: Figure 6.7 should be at the top of p. 198
• p. 211, first line:
"to set c to true" should read "to set d to true"
• Chapter 7:
• p. 229, second paragraph, fifth line:
"With these two problems" should read "With these problems"
• p. 238, Figure 7.5:
vertices of degree 2 should be added at each side (two in all)
• p. 240, Figure 7.8:
vertices of degree 2 should be added between the variable components (two in all)
• p. 248, second line:
a space is needed after the footnote symbol
• p. 257, last line of first paragraph:
• Chapter 8:
• p. 339, first and second bullets:
a space is missing between the class name (PP, then BPP) and the verb "is".
• p. 354, last paragraph, 7th line:
"Holyer [1908]" should read "Holyer [1980]"
• Chapter 9:
• p. 364, third line of penultimate paragraph:
"from Section 4" should read "from Chapter 4"
• p. 375, second line from the bottom:
the capitalization of "Says" is spurious
• p. 389, in the paragraph preceding Exercise 9.9:
the end of the second line reads "ambitious results" but should read "ambitious result"
• Appendix:
• p. 425, third line:
the expression should be placed in parentheses

 Back to The Theory of Computation