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

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 ^{2}* 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

- 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*;^{2} - 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^{n2}*n*squares can hold three different symbols.^{2}

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.