List of Corrections

Page 2, line -10 should say:
Applying this definition to $L = \Sigma$

page 10, line -9:
">" should be ">="

page 11, line (A5):
"commutative" should be "associative"

page 15, lines -12 and -2:
"< Zm,+,0>" should be "< Zm,+,[0]>."

page 15, line 19:
(A9) should be  "1a = a1 = a"

page 17, line 6
"< Zp,+,0>" should be "< Zp,+,[0]>."

page 17, line 8:
"< Zp-{[0]},.,1>" should be "< Zp-{[0]},.,[1]>.

page 26, line 9:
"recognizer" should be "decider."

page 27, line 20:
The line should read "\phi(w_1,...,w_n) exists."

page 31, 1st paragraph:
"N accepts its input word if and only the new state of M is accepting."
"N accepts its input word if and only if the new state of M is
accepting."

page 31, line 13:
"Clearly, this is the stronger notion, for it possible"
"Clearly, this is the stronger notion, for it is possible".

page 33, line -9:
"This occurs if and only every computation path..."
"This occurs if and only if every computation path..."

page 39, line -8:
"l<=t" should be "l<=i<=t"

Page 40, line 4:
Replace "third cell on cell to the left"  with "third
cell one cell to the left"

page 47, line 3:
"a nonempty set is S is enumerable" should be
"a nonempty set S is enumerable"

page 48, Lemma 3.1:
'The graph of a TOTAL computable function is decidable. "

page 48, line -4:
"otherwise halts without accepting." should be
"otherwise rejects."

page 49,  line 4:
Should read, "S is the range of a total computable function f."

Page 53, line 13 (and similarly on line -4):
The equation should read, "lambda y. (x * y)."
For those unfamiliar with the "lambda notation", this simply means we
are thinking of the function of one variable g(y)=x*y, where the x is
considered a constant.

page 64, line 10:
"is is" should be "is."

page 64,  line -16 and -13:
Should be" z is an accepting computation of M on x. "

page 67, line -12:
"phi_0" should be "phi_i."

page 69, line -9: " F(phi_e;e,x1,x2,...,xn) should be "F(phi_e;x1,x2,...,xn)."

page 80, line2:
"c log n < n log n" should be "c n < n log n".

page 85, line 11:
"tape k+3" should be "tape k+2".

page 87, line 1,
"then so are are" should be "then so are ".

page 89, line -1:
"running time of N is" should be "running time of N in".

Page 96, line 3:
"as" should be "at".

Page 98 line -3:
"we need to to observe" should be "we need to observe".

page 99, line -6 and line -5:
"tape 3" should be "tape k+1".

page 101, line -11:
Insert "so that 0 is the number of the initial configuration of $M$ on
input $x$" after the phrase "are ordered in some canonical way."

page 109, line 7:
"tape alphabet is the same as C,"
"tape alphabet contains that of C."

page 109, line 20:
"that M is an S'(n) space-bounded Turing machine"
"that M is a one-tape, S'(n) space-bounded Turing machine"

page 110, line -17:
"L" should be "L'".

page 111, line 1:
"Now let show" should be "Now let us show".

page 118, line 5:
D := 0; (add the semicolon)

page 118, line 20:
"us" should be "use".

page 123, line -12:
The "P" in "NP" should not be in italics.

page 124, line  -3 :
"billion" should be "million".

page 124, line 10:
"}]}" should be "]}".

page 126, line -9:
"in" should be "is".

page 127, line 8:
"F(DM_i,w)" should be "F(i,w)".

page 127 line 17:
"in" should be "is".

page 127, line -1:
The formula should start with a "{".

page 130, line 9:
"is" should be "in".

page 132, line -4:
"p(n+1)" should be "p(n)+1".

page 141, line 13:
"G of size \leq j" should be "G of size \geq j".

page 157, line 3:
"a finte sets" should be "a finite set".

Page 159, line -7:
Should be, "multiplicative group of nonzero elements".

page 169, line -8:
"x \in B" should be "x \in L".

page 173, line -3:
Each occurrence of "B" should be "A".