(Elements of the Theory of Computation 2nd Ed.)Harry R. Lewis, Christos H. Papadimitriou 编著 张立昂 刘田 译　计算理论是计算机科学的理论基础。本书介绍了计算理论最核心、最基本的内容，包括形式语言与自动机、可计算性和计算复杂性三大部分。全书共分七章，分别为：集合、关系和语言；有穷自动机；上下文无关语言；Turing机；不可判定性；计算复杂性；NP完全性。本书突出了算法，从而使计算机专业的学生更易于接受，也更有收益。　译者在译者序中写道：“我之所以愿意翻译这两本书，一是因为它们确实是两本关于计算理论的优秀教材；二是因为国内太缺乏这样的书了，尽管计算机类书刊极其繁多，可是计算理论的书却难觅踪影。”“特别希望立志致力于计算机科学技术事业的青年学生都来认真地学一点计算理论，那将可能是终身受益的。”　本书适合作为计算机专业及数学专业本科生或研究生的教材，也可供从事计算机科学的教学与研究人员参考。

看看你的周围，计算无处不在，无时不在，每一个人都计算，计算影响着所有的人。所以能够如此，是因为在过去的几十年中计算机科学家发现了很复杂的方法用来管理计算机资源，实现通讯，翻译程序，设计芯片和数据库，创造更快、更廉价、更容易使用、更安全的计算机和程序。 和所有的主要学科一样，计算机科学的成功实践建立在优美和坚实的基础之上。自然科学有一些基本问题，如物质的本质是什么?有机体生命的基础和起源是什么?计算机科学同样有它自己的基本问题：什么是算法?什么是能计算的?什么是不能计算的?什么时候可以认为一个算法是实际可行的?６０多年来(甚至从电子计算机出现之前就开始了)计算机科学家一直在考虑这些问题并且给出充满智慧的回答，这一切对计算机科学产生了深刻的影响。 本书的目的是介绍渗透在计算机科学中的这些基本思想、模型和结果，它们都是该领域的基本范例，它们有很多理由是值得学习的。首先，现代计算机科学中的很多东西直接或间接地以它们为基础——而其余的应该……。其次，这些思想和模型是漂亮、有力的，是数学建模的杰出例子，是有长久价值的。此外，它们更是历史的一部分，是我们这个领域的“共同潜意识”。不首先了解它们，是很难理解计算机科学的。 这些思想和模型在本质上是数学的，这大概不会让人感到奇怪。虽然计算机肯定是一个物理实体，但是同样肯定的是关于它的物理方面，如它的分子和它的形状，能够值得说的很少；对计算机最有用的抽象显然是数学的，论证这些抽象所必需的手段也一定同样是数学的。此外，实际的计算工作需要只有数学才能提供的铁的保证(希望我们的编译程序正确地翻译，应用程序最终停机，等等)。但是，在计算理论中使用的数...