(针对2018年10月第1版第1次印刷)
第13页第3-4行：“并且读写头停在……读写头停在0上）”改为“并且读写头停在\(y\) 串的 最后一个 1 （如果有的话，不然 \(y = 0\) ，停在隔开原 \(x + 1\) 串与 \(y + 1\) 串的 0 ） 的右侧。”
第158页第一段：\(x,y\) 统一分别改为 \(\sigma,\tau\)。
第162页第三段开头：“对0-1串\(\sigma\)”，改为“对0-1串\(\tau\)”。
第164页第9行：“\(C(\sigma)\leq |\sigma|-|\mu|…\)”改为“\(C(\sigma)\leq |\sigma|-|\nu|…\)”。
第169页倒数第5行：“对每个 \(\mu\)”改为“对每个 \(\tau\)”。
第177页，定理5.2.35证明中，把出现的“\(c_0\)”统一改为“\(c_e\)”更合适。
第178页倒数第9行：改为\(\lambda(U_n)\leq\frac{(\mathrm{e}^{-2\varepsilon^2})^n}{1-\mathrm{e}^{-2\varepsilon^2}}\)，即指数由\(m\)改为\(n\)。