## ERRATA for Introduction to the Theory of Computation, second printing

Errata for the first printing.

Ordered by date of discovery. Also available in order of appearance in the text.
Last updated 12/1/07. Don't forget to reload this page to get the most current version.
Send additional errors and comments to: sipserbook@math.mit.edu

Page 71, line 13.
Remove the word form.
Reported 2/2/98 by Jerry Grossman of Oakland University.
Erratum corrected 8/15/98 by Alex Vrenios of the Arizona State University.

Page 87, Exercise 1.20, last line.
Change it's to its, (removing the apostrophe).
Reported 2/9/98 by Jerry Grossman of Oakland University.
Page 89, Exercise 1.34, line 4.
Change x an y to x and y.
Reported 2/9/98 by Jerry Grossman of Oakland University.
Page 88, Exercise 1.27, line 4.
Change all three occurrences of C to D.
Reported 2/15/98 by Susheel M. Daswani of New York University.
Page 110, Figure 2.12.
Should add an extra state between q_start and q_loop so that the PDA can push the \$ and then the S on the stack in separate moves.
Reported 2/15/98 by Joseph N. Wilson of New York University.
Page 121, Exercise 2.8, line 2.
Add leftmost before derivations.
Reported 2/15/98 by Joseph N. Wilson of New York University.
Page 149, Problem 3.12 line 5.
Change in the tape to on the tape.
Reported 2/20/98 by Jerry Grossman of Oakland University.
Page 186, displayed equation following first paragraph.
Change [#/#qo0100] = [t1/b1] to [#/#qo0100#] = [t1/b1].
Reported 2/21/98 by Kanata Kuroda of Clark University.
Page 113, line 13.
Add for some stack symbol t at the end of the sentence.
Reported 2/22/98 by Claude Crepeau of the University of Montreal.
Page 189, sentence beginning "Considering..." in middle of page.
Change the the to the.
Reported 3/6/98 by Jerry Grossman of Oakland University.
Page 196, Problem 5.19.
Add CFG as a subscript to the second AMBIG.
Reported 3/6/98 by Jerry Grossman of Oakland University.
Page 200, Line numbered 4.
Remove quotes at end of line.
Reported 3/6/98 by Jerry Grossman of Oakland University.
Page 16, fourth line from bottom.
Add connected before graph and simple before cycles in the definition of tree.
Reported 3/16/98 by Kevin Trent Bergeson of the University of Utah.
Erratum corrected 1/2/03 by Elizabeth Thompson at the University of Wisconsin.

Page 166, fourth line from bottom.
Italicize letter D.
Reported 4/2/98 by Atsushi Fujioka of NTT.
Page 212, fifth line from bottom of Example 6.17.
Change halt on to accept.
Reported 4/3/98 by Jerry Grossman of Oakland University.
Page 275, step 8 of algorithm, line 1.
Change q_0 to q'_0.
Reported 4/17/98 by Jerry Grossman of Oakland University.
Page 276, Problem 7.38, line 2.
Change polynomial time to polynomial time algorithm.
Reported 4/17/98 by Jerry Grossman of Oakland University.
Page 283, line 13 from bottom.
Change the the to the.
Reported 4/17/98 by Jerry Grossman of Oakland University.
Page 286, bottom line.
Change OR to NOT.
Reported 4/17/98 by Jerry Grossman of Oakland University.
Page 291, line 14 from bottom.
Change the generalized to generalized.
Reported 4/17/98 by Jerry Grossman of Oakland University.
Page 291, line 6 from bottom.
Change player to Player.
Reported 4/17/98 by Jerry Grossman of Oakland University.
Page 304, Problem 8.21.
Change NIM to nim on line four and on the second from the last line.
Reported 4/22/98 by Jerry Grossman of Oakland University.
Page 306, first line in last paragraph.
Remove the first that.
Reported 4/22/98 by Jerry Grossman of Oakland University.
Page 336, line 6 of Definition 10.3.
Change where k be to where k is.
Reported 5/5/98 by Jerry Grossman of Oakland University.
Page 337, line 4 after Definition 10.4.
Change exponential to exponentially.
Reported 5/5/98 by Jerry Grossman of Oakland University.
Page 352, line 3 of proof of Theorem 10.21.
Change computation M to computation of M.
Reported 5/5/98 by Jerry Grossman of Oakland University.
Page 216, line 6 of proof of Theorem 6.23.
Change if this to of this.
Reported 5/6/98 by Alexander Perlis of the University of Arizona.
Erratum corrected 8/15/98 by Alex Vrenios of the Arizona State University.

Page 345, fifth line from bottom.
Add finite before field.
Reported 5/6/98 by Alexander Perlis of the University of Arizona.
Erratum corrected 1/2/03 by Elizabeth Thompson at the University of Wisconsin.

Page 364, line 3.
Change is chosen to chosen.
Reported 5/6/98 by Alexander Perlis of the University of Arizona and 5/8/98 by Jerry Grossman of Oakland University.
Page 369, line 1 of the class NC subsection.
Change log to regular roman font.
Reported 5/6/98 by Alexander Perlis of the University of Arizona and 5/29/98 by Jerry Grossman of Oakland University.
Page 370, line 2 of proof.
Change has been has been to has been.
Reported 5/6/98 by Alexander Perlis of the University of Arizona and 5/29/98 by Jerry Grossman of Oakland University.
Page 358, line 6 before Claim 10.27.
Add the before value.
Reported 5/8/98 by Jerry Grossman of Oakland University.
Page 359, last line of proof of Claim 10.27.
Change theorem to lemma.
Reported 5/8/98 by Jerry Grossman of Oakland University.
Page 361, line 7.
Add for after assignments.
Reported 5/8/98 by Jerry Grossman of Oakland University.
Page 364, second line above proof idea.
Add is before similar.
Reported 5/8/98 by Jerry Grossman of Oakland University.
Page 370, line 3 of proof.
Put parentheses around C0, C1, ....
Reported 5/29/98 by Jerry Grossman of Oakland University.
Erratum corrected 11/30/02 by Simson Garfinkel of MIT.

Page 370, fifth line from end of proof.
Change all to exactly those.
Reported 5/29/98 by Jerry Grossman of Oakland University.
Page 382, reference 22.
The page range should be 449-467.
Reported 5/29/98 by Jerry Grossman of Oakland University.
Page 383, reference 31.
The page range should be 270-299.
Reported 5/29/98 by Jerry Grossman of Oakland University.
Erratum corrected 8/15/98 by Alex Vrenios of the Arizona State University.

Page 384, reference 63.
The page range should be 869-877.
Reported 5/29/98 by Jerry Grossman of Oakland University.
Erratum corrected 8/15/98 by Alex Vrenios of the Arizona State University.

Page 83, second paragraph, third line.
Remove not after cannot.
Reported 6/4/98 by Stephen Louie of York University.
Page 268, 4th paragraph of proof of Theorem 7.36, line 7.
Add be after must.
Reported 7/29/98 by Alexander Perlis of the University of Arizona.
Page 300, Theorem 8.22, proof idea.
Variable m is used in paragraph 3 before it is defined in paragraph 5.
Reported 10/1/98 by Atsushi Fujioka of NTT.
Page 301, algorithm M.
Add new stage 11.1. Let d=0. This stage is NOT indented.
Reported 10/1/98 by Atsushi Fujioka of NTT.
Erratum corrected 1/24/01 by Eric Allender of Rutgers University.

Page 158, line 3.
Change CFLs to CFGs.
Reported 10/5/98 by Roger Khazan of MIT.
Page 273, Problem 7.23, second to last line.
Change clique to clause.
Reported 11/2/98 by Alex C. Snoeren of MIT.
Erratum corrected 11/16/98 by Rostom Aghanian at UCS.

Page 99, fourth line of proof of Theorem 2.6.
Remove hyphen between \emptystring and rule.
Reported 11/5/98 by by Atsushi Fujioka of NTT.
Page 121, Problem 2.18, parts a and b.
Add missing periods at the ends of each line.
Reported 11/5/98 by by Atsushi Fujioka of NTT.
Page 279, fourth line after description of N.
Change Hence N decides ALL_NFA to Hence N decides the complement of ALL_NFA.
Reported 11/12/98 by Xiaolong Mou of MIT.
Page 279, Stage 4 of description of N.
Change Stage 4 to read as follows:
Accept if Stages 2 and 3 reveal some string that M rejects, that is, if at some point none of the markers lie on accept states of M. Otherwise, reject.
Reported 11/18/98 by Adam Klivans of MIT.
Page 134, Stage 1 of Turing machine M3.
Change a*b*c* to aa*bb*cc*.
Reported 11/28/98 by Nihar Mehta of the California State University at San Marcos.
Page 282, line 3.
Change ALL_NFA to the complement of ALL_NFA.
Reported 11/29/98 by Roger Khazan of MIT.
Page 298, last line of proof of Theorem 8.18.
Change need to needs to.
Reported 11/29/98 by Roger Khazan of MIT.
Erratum corrected 1/24/01 by Eric Allender of Rutgers University.

Page 340, line 20 from bottom.
Change passes all Fermat tests to passes Fermat tests for all smaller a relatively prime to it.
Reported 11/30/98 by Guangming Xing of the University of Georgia.
Page 393, entry for "Pratt".
Change Vaughn to Vaughan.
Page 198, third line before SELF-REFERENCE section.
Change Step to statement.
Reported 1/25/99 by Kazuo Ohta of NTT Laboratories.
Page 253, second from last sentence.
Exchange B's and C's (two occurrences of each).
Reported 1/25/99 by Kazuo Ohta of NTT Laboratories.
Page 281, lines 4, 6 and 7 from the bottom of the proof of Theorem 8.5.
Change i to i+1 (three occurrences).
Reported 2/3/99 by Kurt Mehlhorn of the Max Planck Institut.
Erratum corrected 11/27/02 by Cem Say of Bogaziçi University, Istanbul, Turkey.

Page 358, second paragraph before Claim 10.27.
In the sentence beginning with "Here, wt-avg..." the probability should be conditional with the condition M_j is the message history.
Reported 2/3/99 by Kurt Mehlhorn of the Max Planck Institut.
Page 301, algorithm M.
Stage 8: Change i to at most i
Stage 10: Change the first period to a comma and change Go to and go
Stage 14: Change i to at most m
Sentence after algorithm: Remove j.
Discovered 2/25/99.
Page 55, second line of the third paragraph of the proof idea of Theorem 1.19.
Add the before the first DFA.
Reported 4/28/99 by Curtis Oliver of Ohio University.
Page 301, algorithm M.
Exchange Stages 4 and 5, and indent Stage 5 to the level of Stage 6.
Change Stage 10 to go to Stage 5 (instead of to Stage 6).
Reported 6/3/99 by Kazuo Ohta of NTT Laboratories.
Page 365, third display.
Change each Si to Si+1. (three occurrences).
Reported 6/9/99 by Christian Jacobi of the University of Saarland.
Page 369, lines 6 and 7.
Line 6: change n3 to n2.
Line 7: change n to m.
Reported 6/28/99 by Kazuo Ohta of NTT Laboratories.
Page 388-396, index entries.
circuit-satisfiability problem: should be capitalized.
Cook-Levin theorem: change 249-330 to 249-259, 329-330
Levin, Leonid: A. change 249-330 to 249, 329.
SUBSET-SUM: merge the two entries.
Reported 7/7/99 by Hiroki Ueda of NTT Laboratories.
Page 364, lines 5 and 6 from the bottom.
Change both occurrences of Qi to Qi+1.
Reported 9/22/99 by German Muller of MIT.
Page 305, line 12.
Change are provably to have been proven to be.
Reported 11/4/99 by Shaun Cutts of MIT.
Page 95, Figure 2.2, right-hand parse tree.
Add a line connecting <EXPR> (above the 1st "a") and <EXPR> (above the 2nd "a").
Reported 11/6/99 by Edward D. Legenski of Dow Corning.
Erratum corrected 1/24/01 by Eric Allender of Rutgers University.

Page 342, 13th line from the bottom.
The analysis doesn't cover the case when p is a power of a prime. This case can be ruled out by showing such a p will have a Stage 4 witness.
Reported 11/10/99 by Somenath Biswas of the Indian Institute of Technology, Kanpur.
Page 208, line 11 and the 7th line from the bottom.
Change all three occurrences of xi to xi+1.
Reported 11/15/99 by Kazuo Ohta of NTT Laboratories.
Page 354, 8th line in section 10.4.
Change 247 to 243.
Reported 11/15/99 by Kazuo Ohta of NTT Laboratories.
Page 267, second paragraph, line 5.
Change In that occurs to If that occurs.
Reported 11/26/99 by Kenneth Tam of the University of Washington, Seattle.
Page 298, 9th line of proof of Theorem 8.18.
Change B to MB.
Reported 11/23/99 by Lilla Zollei of MIT.
Erratum corrected 1/24/01 by Eric Allender of Rutgers University.

Page 278, line 4 in Example 8.4.
Change any to all.
Reported 12/1/99 by Steven Greenberg of MIT.
Page 279, paragraph following Algorithm N.
Change accepts, accept, and accepted (twice) to rejects, reject, and rejected.
Reported 12/1/99 by Steven Greenberg of MIT.
Page 332, sixth line of Problem 9.18.
Add s \in A and after where.
Reported 12/5/99 by Jinghua Zhang of Michigan State University.
Page 300, fifth line of proof idea of Theorem 8.22.
Change lets to let's.
Reported 1/7/00 by Kazuo Ohta of NTT Laboratories.
Page 307, eleventh line from bottom.
Change page 165 to page 160.
Reported 3/28/00 by Seungjoo Kim of the Korea Information Security Agency.
Page 156, fifth line of proof idea of Theorem 4.6.
Change an recognizer to a recognizer.
Reported 5/5/00 by Jesir Vargas of Universidad de Puerto Rico (Río Piedras).
Page 261 and 268, proofs of Theorems 7.34 and 7.36.
Each proof needs to state why its language is in NP.
Reported 5/20/00 by Sarfraz Khurshid of MIT.
Page 258, first displayed expression.
Under the big AND sumbol, write 1<i<nk instead of 1<i<nk.
Reported 5/23/00 by Sarfraz Khurshid of MIT.
Page 134, Stage 3 of Turing machine M3.
Add the sentence: If all c's are crossed off when b's remain, reject.
Reported 6/5/00 by Anders Martinson of California State Hayward.
Page 169, problems 4.12 and 4.13, second lines.
Remove * following {0,1}.
Reported 10/9/00 by Kim Schioett of Aalborg University, Denmark.
Page 207, fifth line from bottom, and page 208, second line.
Change Sigma_i^* to Sigma_i.
Discovered 10/10/00.
Back Cover, third line from end of first paragraph.
Change computability to complexity.
Reported 10/24/00 by Damon Mosk-Aoyama of MIT,
and 11/19/00 by Meeta Advani of the University of Pennsylvania.

Page 319, tenth line from bottom.
Change machines to machine.
Reported 12/7/00 by Karen Livescu of MIT.
Page 244, proof of Theorem 7.17, stage 1 of algorithm N.
Add at most after length.
Reported 12/15/00 by Thomas M. Oleson, Jr.
Page 331, problem 9.13.
At the end of the second sentence add the phrase , if we ignore small changes in running times.
Change the last two sentences, starting with Show that ... to the sentence Show that for time constructible functions t(n) if A is recognized in time O(t(n)) then A is decided in time O(t(n) log t(n)).
Reported 12/19/00 by Victor Kuncak of MIT.
Page 337, line 2 following Definition 10.4.
Change as long it to as long as it.
Reported 12/19/00 by Karen Livescu of MIT.
Page 360, last sentence of Phase m+1.
Change That complete to That completes.
Reported 12/27/00 by Karen Livescu of MIT.
Page 362, last sentence of second paragraph.
Change The degrees of each to The degree of each.
Reported 12/27/00 by Karen Livescu of MIT.
Page xiv, line 7 from bottom.
Change Stallman to Stallmann.
Page 264, Figure 7.14.
Add an arrowhead on the edge from the upper central node of the x2 diamond to the node on the right (as in the x1 diamond).
Reported 2/17/02 by Doug Burke of the Ohio State University.
Page 343, fourth line before Definition 10.10.
Change we know that the input probably is prime to the input could be prime or composite.
Reported 3/7/02 by Ronald Rivest of MIT.
Page 239, third line from botton.
Change the lesser of log2x and log2y to the lesser of 2log2x and 2log2y.
Reported 3/7/02 by Ronald Rivest of MIT
and 8/12/02 by Michael Manapat of UC Berkeley.

Page 266, Figure 7.18, right-hand part labeled "zag-zig".
Add an arrowhead on the edge from the top node to the left-hand node.
Add another arrowhead on the upper edge from the second to the third node (counting from the left).
Reported 4/20/02 by Radu Stoleru of the University of Virginia.
Erratum corrected 10/14/02 by Cem Say of Bogaziçi University, Istanbul, Turkey.
and 10/30/02 by Simson Garfinkel of MIT.

Page 366, second line of Phase k+1.
Change fm to fk.
Reported 7/17/02 by Holger Petersen of the University of Stuttgart.
Page 219, proof of Theorem 6.28.
Line 11: Change 1/2b+c to 1/2b+c+1 .
Line 14: Change 2n / 2b+c= to 2n+1-1 / 2b+c+1< .
Reported 8/14/02 by Kurt L. Van Etten.
Erratum corrected 11/27/02 and 12/8/02 by Cem Say of Bogaziçi University, Istanbul, Turkey.

Page 242, last paragraph,
Page 272, Problems 7.8 and 7.18,
Pages 339-343, Primality section.
These sections need to be updated due to the paper of Manindra Agrawal, Neeraj Kayal, and Nitin Saxena showing that primality testing is in P.
Inclusion here suggested 8/24/02 by Chittaranjan Tripathy of the Silicon Institute of Technology, India.
Page 84, Exercise 1.5.
Add In all cases the alphabet is {0,1}. after the first sentence.
Reported 9/5/02 by Paul Huff of Brigham Young University.
Page 280, fourth stage of CANYIELD algorithm.
Change the "round up" of t/2 to a "round down".
Reported 9/17/02 by Michael Manapat of UC Berkeley.
Erratum corrected 11/18/07 by Hendrik Klinge of the University of Paderborn.

Page 216, sixth line from bottom.
Change the length of K(x) to K(x), the length of d(x),.
Reported 9/19/02 by Cem Say of Bogaziçi University, Istanbul, Turkey.
Page 314, seventh line of proof idea of Theorem 9.15.
Add the complement of before ALLNFA.
Reported 10/21/02 by Cem Say of Bogaziçi University, Istanbul, Turkey.
Page 332, last line of Problem 9.18.
Change TIME(n2) to TIME(n6)
and TIME(n) to TIME(n3).
Reported 11/25/02 by Christos Kapoutsis of MIT.
Page 279, sixth line after description of N.
Change markers, to markers and the repeat loop counter,
Reported 11/26/02 by Karun Bakshi of MIT.
Page 362, footnote 3.
This remark is now unnecessary because PRIMES \in P.
Reported 11/27/02 by Cem Say of Bogaziçi University, Istanbul, Turkey.
Page 105, second paragraph of example 2.10.
The first line should be indented.
Reported 12/10/02 by Simson Garfinkel of MIT.
Page 247, algorithm V in the proof of Theorem 7.21.
Exchange stages 1 and 2. Add and reject if not at the end of the new step 1.
Reported 12/19/02 by Cem Say of Bogaziçi University, Istanbul, Turkey.
Page 6, end of fourth line before Example 0.1.
Add a period at the end of the sentence.
Reported 1/8/03 by Elizabeth Thompson at the University of Wisconsin.
Erratum corrected 3/25/04 by Cem Say of Bogaziçi University, Istanbul, Turkey.

Page 9, sixth line before Example 0.7.
Add a comma after equivalence relation.
Reported 1/8/03 by Elizabeth Thompson at the University of Wisconsin.
Page 179, fourth line from bottom.
Change a computation history to an accepting computation history.
Reported 1/14/03 by Kurtcebe Eroglu of the Middle East Technical University, Ankara, Turkey.
Erratum corrected 7/5/03 by Sven Waibel of the Georg-Simon-Ohm-Fachhochschule Nürnberg.

Page 25, Exercise 0.1, part b.
Remove final comma.
Reported 1/21/03 by Elizabeth Thompson at the University of Wisconsin.
Page 111, last paragraph before the proof.
In the sentence starting with We simulate ..., delete the first occurrence of symbol and replace the second occurrence of symbol with input. [The reason is that a and b can be the empty string, not just symbols.]
Reported 1/27/03 by Cem Say of Bogaziçi University, Istanbul, Turkey.
Page 217, second line of the proof idea of Theorem 6.24.
Insert w after short description.
Reported 1/27/03 by Cem Say of Bogaziçi University, Istanbul, Turkey.
Page 141, Line 1.
Insert E before starts.
Reported 2/10/03 by Vee Voon Yee of Nanyang Technological University.
Page 11, fourth line from bottom of page.
Change is one that to is a cycle of length 3 or more that.
Reported 2/26/03 by Stephen Smith.
Page 66, expression on line 12.
Change { +, -, \epsilon } to ( + \union - \union \epsilon ).
Reported 2/26/03 by Ronald Rivest of MIT.
Page 133, bottom of page.
At the end of the paragraph, add the sentence For completeness, say that the head moves right in each of these transitions to the reject state.
Reported 5/26/03 by Paul Muir of the University of Utah.
Page 286, fourth line.
At the end of the paragraph, add the sentence Here, let f(n)=nk.
Reported 6/10/03 by Gabriel Nivasch of the Weizmann Institute.
Page 301, fifth line from bottom.
Add u, v, ci+1, after needs to store.
Reported 6/10/03 by Gabriel Nivasch of the Weizmann Institute
and 7/25/03 by Anthony Widjaja of the University of Melbourne.

Page 372, second paragraph, second line.
Change areas to area.
Reported 6/17/03 by Gabriel Nivasch of the Weizmann Institute.
Page 383, reference 45.
Change russian to Russian.
Reported 6/17/03 by Gabriel Nivasch of the Weizmann Institute.
Page 301, algorithm M.
Stage 3: Change Let ci+1 = 0 to Let ci+1 = 1.
Stage 4 (appears as Stage 5 in text but was moved to Stage 4 by an earlier erratum): Change For each node v in G to For each node v \neq s in G.
Reported 6/25/03 by Arnold Beckmann of the University of Muenster.
Page xiii, line seven.
Change lengthly to lengthy.
Reported 8/21/03 by Paul Bondin of the Kann Finch Group.
Page 338, after first displayed \Sum.
Change M2 errs exactly to M1 errs exactly.
Reported 8/22/03 by Robert Robinson of the University of Georgia.
Page 129, last line.
Add or the language recognized by M, before denoted.
Reported 10/20/03 by Detlef Plump of York University.
Page 192, Example 5.18.
Add the following sentence at the end of the example.
When describing a Turing machine that computes a reduction from A to B, if the input is not of the correct form as specified in the input line "On input < M,w>" then the reduction outputs a string that is not in B before halting.
Reported 10/23/03 by Cem Say of Bogaziçi University, Istanbul, Turkey.
Page 379, Problem 10.16.
Add which is relatively prime to p, after Zp.
Reported 11/21/03 by Cheng Yongxi of Tsinghua University.
Page 99, second line from bottom.
Change k > 2 to k = 2.
Reported 12/6/03 by Dr. Hisham M. Sueyllam of Alexandria University, Egypt.
Page 364, line 8.
Add at most before the number of phases.
Reported 12/13/03 by Nick Harvey of MIT.
Page 168, line 6.
Change one of them halts to one of them accepts.
Reported 1/14/04 by Bruce Carneal of UC San Diego.
Page 286, last line.
After end of sentence add Here, for clarity, we use the symbol = for Boolean equality instead of the double arrow symbol used in section 0.2..
Reported 4/19/04 by Bina Reed of the University of Georgia.
Erratum corrected 11/18/07 by Hendrik Klinge of the University of Paderborn.

Page 175, line 8 of proof idea.
Add a comma after does not accept w to improve readability.
Reported 1/14/04 by Ghaith Issa of the American University of Beirut.
Page 298, last line.
Delete the word machine.
Reported 3/25/04 by Cem Say of Bogaziçi University, Istanbul, Turkey.
Page 146, 8th from last line.
Change If w to If the input.
Reported 5/22/04 by Sean Williams of UC San Diego.
Page 40, 10th from last line.
Change if a sequence of states r0, r1, ..., rn exists in Q to if a sequence of states r0, r1, ..., rn in Q exists.
Reported 6/30/04 by Samir Chopra and Scott Dexter of Brooklyn College of CUNY.
Page 360, Phase m and Phase m+1.
Change both occurrences of f to fm.
Reported 10/20/04 by Aaron Kaufman of Harvard University.
Page 184, Theorem 5.11.
Add a period after PCP is undecidable.
Reported 10/26/05 by Lee-kai Wang of MIT.