Page 3: Two typos in one list. The word "is" is missing from both the first and second items at the top of the page. These lines should read determine whether or not the query name is in the list and determine whether or not it is possible to reach t starting from s.
Found by Jon Paul Simonelli.
 

Page 45: To make the AcceptsUsingUseless program consistent with the proof of Rice's Theorem, source should be set to:
    "DoNotRunThis(x):
         if Execute(P,w) returns Yes
          then if x is 01 return Yes else rerturn No
          else return No"

 

Page 47: The last sentence in the definition of the NON-REGULARITY TESTING PROBLEM reads: "In other words, is it impossible to design a finite automaton, M, such that M recognizes the same language ..." To this point in the book, we have not talked about what it means for a finite automaton to recognize a language. Instead we have used the term decides because the finite automaton we have defined always halts. To avoid confusion, this sentence should read: "In other words, is it impossible to design a finite automaton, M, such that M decides the same language ..."
 

Page 59: The heading of the third bullet of Definition 5.1, should read: CORRECT YES ANSWER IS POSSIBLE
 

Page 138-139: An additional case must be added for t < 0 because we check MinCost[i-1,t-v(i)] in the last case and t-v(i) could be less than 0. Add the following case prior to the first case:

Page 143: In the second sentence of the caption for Figur 8.9, "The parameter scaleFactor..." should be replaced by The parameter F...
 

Page 170: A "b" is missing from the third line of Exercise 10.3. The sentence should read: Show that the problem can be solved using ...
 

Page 172: ExecuteBounded also needs to return No if the simulated machine runs forever. For the simulated machine to run forever without using more than n² tape squares, it must enter the same configuration over and over again. The maximum number of distinct configurations that the simulated machine can enter if it uses less than n² space will depend on:

• the number of possible positions of the tape head on the input tape, which is n ;
• the number of possible positions of the tape head on the work tape, which is n²;
• the number of possible lines in the source code, which is n since the source code is the input;
• and the number of possible strings of characters the can appear on the work tape -- assuming the tape alphabet consists of only 0, 1, and β, this is 3 ⁿ² because each of the n² squares can hold three different symbols.

Page 214: In the first sentence of the third paragraph, there is a comma missing after L(M).
 

Page 219: The first line on the page is missing the word "know". The line should read: ..., however, the Turing machine does not know when to stop simulating E.
 

Page 219: There is a question mark missing from the first sentence of the first full paragraph. The sentence should read: We have proven that recursively enumerable languages are recognizable, but are recognizable languages necessarily recursively enumerable?
 

Page 266: Check on this one In the sixth line of the first paragraph "was prior to the move" should read: was after the move..
 

Page 170: In the third line of the second paragraph "of a that process" should read: of that process.
Found by Dick Stearns.
 

Page 283: Ironically, in the next to last line of the paragraph under the heading Asymptotics, there is a space missing after the words Space Hierarchy Theorem. The line should read: in the proof of the Space Hierarchy Theorem in Chapter 10.
 

Page 290: I inadvertently neglected to thank Adam Cornachione, who read a draft of the book soon after he graduated and provided me with helpful comments. Sorry, Adam.