Typos in Elements of the Theory of Computation







Page 27, in example 1.5.3, Re={e,f} and Rf={a,c,d,e}

Page 70, after example 2.2.3, in the definition of M', "F'={Q..." not "F={Q..."

Page 70, second to last paragraph, s'={q0,q1,q2,q3}

Page 71, first line, K' should be K.

Page 71, 3rd line of the induction step, "(q,w))" should be "(q,w)"

Page 71, second to last line, the first (r1,a) should be (r1,e)

Page 77, 3 lines before the start of part (b) "(s2,w)" should be "(s2,w)"

Page 80, in the definition of R(i,j,n) replace x with w

Page 81, in Figure 2-15, interchange q2 and q3

Page 91, Exercise 2.4.10 (a), ab should be anbn

Page 95, Example 2.5.1, line (2), abLa should be abLa union a

Page 97, line 5, a * is needed before (q,e).

Page 99, lines 2 and 6, subscript n should be n-1.

Page 132, line 2, (q,y,\zeta) instead of (q,x,\zeta)

Page 133, just below the table, K={s,f} instead of K=(s,f)

Page 139, A --> \beta should be A --> \gamma. Last line, first M should be M'.

Page 140, line 6, the (f,Z,e) should be (f,e,Z) Also, in the displayed transitions, t 1 should be qB1, t n-2 should be qB1B2...Bn-2, t n-1 should be qB1B2...Bn-1,

Page 141, line -10, ((q,a,B),(r,e)) should be ((q,a,B),(r,C)). Also, lines -4, -3, and subsequently: M should be primed.

Page 142, line 6, "sate" should be "state"

Page 142, in the displayed equation of the Claim, a * is needed in the transition symbol.

Page 143, line 4, two missing second |'s.

Page 151, lines -7 and -6, and pages 152 and 153 in the algorithms, the double arrows instead should be single arrows.

Page 164, line -8, {f} should be {q}.

Page 182, line -6, KxSigma should be (K-H)xSigma.

Page 184, in the configuration of the top right Turing machine, a left end symbol is missing

Page 185, last line, q 0 should be q 1; similarly with the page 186, second line, the first occurrence of q 0.

Page 190, the Turing machine C ends up with the scanned symbol being the blank after the copy of w, not between the original w and its copy

Page 190, Example 4.1.9, the displayed Turing machine is the right-shifting machine, not the left-shifting one.

Page 194, line -14, the last component of M (an H ) is missing.

Page 197, end of Example 4.2.3, "head to the right" should be "head to the left", and SR should be SL.

Page 210, in Figure 4-18, the first tape squares should be labeled T(1)T(2)...

Page 216, line 12, R k should be R k-1

Page 222, in line 10, both w's should be v

Many thanks to Carl Smith and his University of Maryland class, as well as to Rocio Guillen, Zhizhang Shen, Charles Wells, Jeremy Dawson, among several others.