ITOC: Introduction to the Theory of Computation
- 书本信息：豆瓣，官网
- 第三版勘误：Errata
- 相关视频：MIT 18.404J Theory of Computation, Fall 2020
- 对应课程: 18.404/6.5400
- 第三版中文译本：计算理论导引
什么是可以计算的，什么是不可判定的，在计算理论的 topic 中，这是绕不开的话题。 把握时间复杂度，空间复杂度，理解自动机，正则表达式，上下文无关文法，图灵机等等，都是计算理论的基础。
最有名的 P/NP 问题，是现代密码学的理论核心，我们不能在有限的计算能力下，找到一个多项式时间的算法来解决 NP 问题，如果有，我们几乎谈不上数据安全了，而这个问题的答案至如今仍未被证明出来。
国内很多学校会把提取这本书的部分内容，作为一门课("计算理论"或者"自动机与形式语言") ，甚至提取出部分塞给"编译原理"，压缩了许多编译原理中有趣的内容(在 SCNU 是这样的)。
《Introduction to the Theory of Computation》由 Michael Sipser 撰写，是计算理论领域的经典教材，非常适合计算机科学学生和研究人员。这本书详细介绍了自动机、可计算性以及复杂性理论三大核心主题。其内容不仅系统全面，而且条理清晰，能够循序渐进地引导读者深入理解计算的本质和限制。国内的黑书也有它的翻译("计算理论导引")，豆瓣评分很高，读不惯英文可以去看看中文翻译后的版本。
MIT 在 Youtube 公开了 20fa 的课程视频，b 站也有相关资源的搬运。
我在学习 ITOC 时，主要就是跟着CS 172 Computability and Complexity的 Lecture 视频学习，页面上也有很多不错的资源，推荐看一看。
在谈到这本书时，不得不拿出另一本书，《Computational Complexity: A Modern Approach》，这本书是计算复杂性理论的经典教材，由 Sanjeev Arora 和 Boaz Barak 合著。这本书详细介绍了计算复杂性理论的基本概念、方法和技术，涵盖了多项式时间可解问题、NP 完全性、随机化算法、交互式证明系统等内容。
Sipser 的书更适合初学者，而 Arora 和 Barak 的书则更适合进阶学习。两本书结合起来，可以帮助读者全面系统地掌握计算理论的核心知识。