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." should read "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" should read "Clearly, this is the stronger notion, for it is possible". page 33, line -9: "This occurs if and only every computation path..." should read "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: should read '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," should read "tape alphabet contains that of C." page 109, line 20: "that M is an S'(n) space-bounded Turing machine" should read "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".