ERRORS IN BOOK
replaceg from g'withg' from g line -8, p. 10
replaceno terminalwithonly terminal line -6, p. 10
interchange3 and 4 p. 13 fig. 1.2.2
addin := 0aftercount := 0 p. 28
in := 1afterif x=median then do
in := 1afteror
if in=1 thenafterfar. */
note

At the end of the paragraph that precedes, each nondeterministic instruction `x:=?' takes its values from a finite domain Example 1.4.4.

Note: Without such a constraint, the Hilbert's 10th problem would be solvable. 

read Q(x_1,...,x_n) 
x_1:=? 
. 
. 
. 
x_n:=? 
 
if Q(x_1,...,x_n)=0 then if eof then accept

(Example provided by Romas Alonderis.)

 p. 33
replaceiin `ith' withwith italic ch l. -9, p. 50
insert(aabbaq0,11)instead of(aabbaq0,1) second paragraph p.56
insertfinite-state transducerinstead ofTuring transducer Figure 2.2.7 p.58
deleteand infinitely many non halting computations l. -19 p. 59
insertlanguage L(M1) /~\ L(M2)instead ofrelation R(M1) /~\ R(M2) last line p. 88
insert prefix of xinstead ofprefix of L 3rd line p. 89
insertRP(state,top)instead ofRP(top) p. 110
insert<Q,S,d,q0,Z0,F>instead of<Q,S,d,q0,F>
insertmissing line figure 3.3.6, p. 125
insertY(R)instead ofY Exercise 3.5.1(c) p. 142
insert(b) figure 4.2.2
replace machine M2 with transducer M2 Proof Th 4.5.4 p. 177
remove

Landweber (1963) showed that there are languages that cannot be accepted by any deterministic linear bounded automaton but that can be accepted by a linear bounded automaton.

(Wan Fokkink pointed the error and pointed out that the question whether DLBA and NLBA are equally expressive is still wide open. References: [1] Burkhard Monien: On the LBA Problem. In Proc. FTC'81, LNCS 117, pp 265-280, 1981. [2] Hartmanis and Hunt: The LBA problem and its importance in the theory of computing. SIAM-AMS Proceedings 7, pp 1-26, 1974.)

 p. 198
replaceX, Y, Z, Wwithslanted chrs l. 1 p. 240
insertPippenger, N.instead ofPippenger, E. p. 306, 311
moveHong, J. ...up p. 304, l. -10
removecommaafterLaaser, W. p. 304, l. -4
replaceMillewithMiller p. 305, l. 7
replacecircutwithcircuit p. 306, l. -6
removeff.after280 p. 314, c. 1, l. 2