What Is A Computer and What Can It Do?
An Algorithms-Oriented Introduction to the Theory of Computation

Thomas C. O'Connell

College Publications

"Perfection may be ideal, but it is the death of done."1

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:
         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:

When t < 0, MinCost[i,t] = ∞


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 n2 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 n2 space will depend on:

The product of these values, n43 n2, is the maximum number of distinct configurations the simulated machine can enter. To determine whether the simulated machine cycles, ExecuteBounded can keep a count of the number of configurations entered; ExecuteBounded returns No if the count goes above n43 n2. The amount of space that ExecutedBounded uses to keep track of this count in binary is 4 log(n) + n2log(3). Therefore, even with this modification, ExecutedBounded uses O(n2) space.

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.

1. [Quote from: Style: The Basics of Clarity and Grace (4th Edition) by Williams and Colomb, Longman, 2012]