本书由计算理论领域的知名权威Michael Sipser所撰写。他以独特的视角，系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。本书可作为计算机专业高年级本科生和研究生的教材，也可作为教师和研究人员的参考书。

本书由计算理论领域的知名权威Michael Sipser所撰写。他以独特的视角，系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。绝大部分内容是基本的，同时对可计算性和计算复杂性理论中的某些高级内容进行了重点介绍。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。同样，对于算法描述，均以直观的文字而非伪代码给出，从而将注意力集中于算法本身，而不是某些模型。新版根据多年来使用本书的教师和学生的建议进行了改进，并用一节的篇幅对确定型上下文无关语言进行了直观而不失严谨的介绍。此外，对练习和问题进行了全面更新，每章末均有习题选答。
本书还配有双语电子教案，需要者可登录华章网站（www.hzbook.com）下载。

作者简介
迈克尔·西普塞（Michael Sipser） 美国麻省理工学院应用数学系教授，计算机科学和人工智能实验室（CSAIL）成员。他从事理论计算机科学与其他数学课程的教学工作三十多年，目前为数学系主任。他痴迷于复杂性理论，喜欢复杂性理论的教学工作。

本版新增了关于确定型上下文无关语言的一节。我选择这个主题有以下几个原因。首先，它填补了我之前对自动机理论和语言处理之间的明显空白。以前的版本介绍了有穷自动机以及图灵机在确定型和非确定型上的变形，但却只包含了下推自动机的非确定型变形。因此，增加关于确定型下推自动机的讨论正如同找到完成拼图游戏所缺的那块。
其次，确定型上下文无关文法理论是LR(k)文法的基础，同时也是自动机理论在编程语言和编译器设计上重要且非平凡应用的基础。这个应用将一些关键概念，包括确定型和非确定型有穷自动机的等价性、上下文无关文法和下推自动机之间的相互转换，汇聚一起得到一个高效且漂亮的语法分析方法。这里我们实现了理论和实践的相互联系。
最后，虽然该主题作为自动机理论一个真实的应用非常重要，但它在现有理论教科书中却没有得到足够重视。我研究LR(k)文法多年但一直没有完整理解它们如何工作，也没有看到它们与确定型上下文无关语言理论的完美契合。我写作这一节旨在为理论学者和实践者提供关于这个领域直观而不失严谨的介绍，并由此对该领域做出贡献。需要注意的是：这一节的部分内容非常具有挑战性，因此基础理论课程的教师可考虑将其作为补充读物。之后的章节不依赖于这部分内容。
在撰写本版的过程中，很多人给了我直接或间接的帮助。我很感激两位审阅者Christos Kapoutsis和Cem Say。他们阅读了这一版新内容的初稿，并提供了很有价值的反馈意见。在Cengage Learning的一些人协助了本书的出版工作，特别是Alyssa Pratt和Jennifer FeltriGeorge。Suzanne Huizenga编辑了文字，ByteGraphics的Laura Segel绘制了新的图片并修改了以前版本中的图片。
感谢我在MIT的助教：Victor Chen, Andy Drucker, Michael Forbes, Elena Grigorescu, Brendan Juba, Christos Kapoutsis, Jon Kelner, Swastik Kopparty, Kevin Matulef, Amanda Redlich, Zack Remscrim, Ben Rossman, Shubhangi Saraf, Oren Weimann。他们都给予了我帮助，包括：讨论新的问题并给出解决方法，提出如何让学生理解课程内容的见解。我非常享受与这群有天赋、有热情的年轻人一起工作。
我很高兴收到了来自世界各地的邮件，非常感谢你们的建议、问题和思路。这里有一个相关人员列表，他们的意见对这个版本产生了影响：
Djihed Afifi, Steve Aldrich, Eirik Bakke, Suzanne Balik, Victor Bandur, Paul Beame, Elazar Birnbaum, Goutam Biswas, Rob Bittner, Marina Blanton, Rodney Bliss, Promita Chakraborty, Lewis Collier, Jonathan Deber, Simon Dexter, Matt Diephouse, Peter Dillinger, Peter Drake, Zhidian Du, Peter Fejer, Margaret Fleck, Atsushi Fujioka, Valerio Genovese, Evangelos Georgiadis, Joshua Grochow, Jerry Grossman, Andreas Guelzow, Hjalmtyr Hafsteinsson, Arthur Hall III, Cihat Imamoglu, Chinawat Isradisaikul, Kayla Jacobs, Flemming Jensen, Barbara Kaiser, Matthew Kane, Christos Kapoutsis, Ali Durlov Khan, Edwin Sze Lun Khoo, Yongwook Kim, Akash Kumar, Eleazar Leal, Zsolt Lengvarszky, ChengChung Li, Xiangdong Liang, Vladimir Lifschitz, Ryan Lortie, Jonathan Low, Nancy Lynch, Alexis Maciel, Kevin Matulef, Nelson Max, HansRudolf Metz, Mladen Mika, Sara Miner More, Rajagopal Nagarajan, Marvin Nakayama, Jonas Nyrup, Gregory Roberts, Ryan Romero, Santhosh Samarthyam, Cem Say, Joel Seiferas, John Sieg, Marc Smith, John Steinberger, Nuri Ta瘙
塂demir, Tamir Tassa, Mark Testa, Jesse Tjang, John Trammell, Hiroki Ueda, Jeroen Vaelen, Kurt L. Van Etten, Guillermo Vázquez, Phanisekhar Botlaguduru Venkata, Benjamin BingYi Wang, Lutz Warnke, David Warren, Thomas Watson, Joseph Wilson, David Wittenberg, Brian Wongchaowart, Kishan Yerubandi, Dai Yi。
最重要的是，我要感谢我的家人——我的妻子Ina以及我们的孩子Rachel和Aaron。时光荏苒，岁月如梭，你们的爱就是一切。

Michael Sipser
马萨诸塞州，剑桥
2012年4月

计算机\计算理论

本书由计算理论领域的知名权威Michael Sipser所撰写。他以独特的视角，系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。绝大部分内容是基本的，同时对可计算性和计算复杂性理论中的某些高级内容进行了重点介绍。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。同样，对于算法描述，均以直观的文字而非伪代码给出，从而将注意力集中于算法本身，而不是某些模型。新版根据多年来使用本书的教师和学生的建议进行了改进，并用一节的篇幅对确定型上下文无关语言进行了直观而不失严谨的介绍。此外，对练习和问题进行了全面更新，每章末均有习题选答。

[美]迈克尔·西普塞（Michael Sipser）著：Michael Sipser　美国麻省理工学院应用数学系教授，计算机科学和人工智能实验室（CSAIL）成员。他从事理论计算机科学与其他数学课程的教学工作三十多年，目前为数学系主任。他痴迷于复杂性理论，喜欢复杂性理论的教学工作。

加作者照片

段磊　唐常杰 等译：暂无简介

计算机改变并持续改变着世界，如今，计算技术已把人们带进了云（云计算）、物（物联网）、人（社会计算）、海（海量数据、大数据）的新时代。
在变革的时代里，计算机系统也改变着自己，在进步和进化中遵循了一组潜规则——计算理论，这套理论描述和论证了计算机的能与不能，界定了计算能力的极限。
业内人士常评说某人为某问题设计了一个比较快的算法，好到什么程度？用专业术语描述，线性时间内能完成的比较快，多项式时间能完成的次之，不能在多项式时间内完成的就是不现实的。但是，大数据时代的来临修正了这一观念，对于大数据问题，线性时间也嫌太长，因为需要“等它一千年”，人们呼唤亚线性、亚亚线性的算法。
有些问题，人们已经找到快的算法；有些问题，还没有找到快的算法，也许是等一个聪明程序员的出现。但有一类问题，没有找到好算法不是因为人们不够聪明，而是根本就不存在这样的算法。
计算理论将描述算法的本质，揭示计算机算法的能与不能、快与慢以及足够快的近似技巧。从这个角度来看，计算理论是计算机的灵魂，是应用计算机成功解决实际问题的保障。
这本由麻省理工学院名师Michael Sipser编撰的名著是计算理论领域的优秀书籍之一，对于非纯理论专业的人士，也许是深浅程度最合适的。自1996年第1版问世，该书历经近二十年，获得了学术界的公认和教育界的好评。该书具有如下优点：
第一，内容丰富，编排合理，展现了计算机科学研究的广度和深度。该书以理论计算机科学的知识框架为脉络，系统地讲述了自动机与形式语言、可计算性理论和计算复杂性理论等计算理论的重要内容。总体编排上，难度由浅入深、循序渐进，易于学习。
第二，文字清晰，语言生动。作者以引导、举例为叙述手段，对计算理论领域的重要定理、性质等不仅给出证明，而且讲述证明思路，着力让读者在学习理论的同时掌握证明的技巧，彰显了作者在此领域的深厚造诣和娴熟的教学手法。
第三，各章设有练习和问题，并提供了部分习题的解答。通过作答习题，能够锻炼读者的逻辑推导思维，加深读者对关键知识点的理解。
我以切身体会向计算机专业的高年级本科生、硕士生和博士生推荐此书。我在本科阶段第一次接触了该书的第1版。差不多10年前，在刚开始博士阶段学习时，参与了本书第2版的翻译工作。如今，我又引导我的学生学习这本书，并承担了第3版的翻译工作。作为多重身份的“过来人”，我有独特的体会。一方面，该书写作规范，研究生可以学习到规范的定义、性质、证明的表述方式，学习该书内容有助于提升计算理论素养，增强学习能力；另一方面，研究生多苦于论文理论深度不够，也不知如何分析问题，认真领会该书讲述的证明思路和解题思路，常会让我们有豁然开朗之感，问题分析能力随之增强，进而提高研究论文的水平。
相较于本书第2版，第3版的内容更新主要在于增加了关于确定型上下文无关语言的阐述，这使得本书关于自动机理论和语言处理的介绍更为完整。此外，第3版对每章后的习题进行了增补和重新编排。除了对第3版新增和修正内容进行翻译以外，我们还对第2版译文的错误进行了更正。同时，我们尽可能保持新版译文的文风与第2版译文一致。
本书由段磊、唐常杰主译，王文韬、王怡宁、杨皓、王梦洁也付出了艰辛的努力。如同我们在完成本书第2版翻译工作时所言，本书第3版的翻译工作是在先行者们工作的基础上，再次接过接力棒，把接力赛再推进一程。借此机会，向本书第1版译者（北京大学的张立昂教授、王捍贫教授和黄雄老师）表示衷心的感谢，也向本书第2版译者表示衷心的感谢。同时，机械工业出版社华章分社的姚蕾、朱劼编辑在翻译过程中给予了我们大力支持，向她们表示衷心的感谢。特别向阅读本书第2版译文并给予我们翻译指正的读者表示衷心的感谢。
由于水平有限，译文难免有错误和不妥之处，恳请读者批评指正。
段磊
2015年6月于四川大学

出版者的话
译者序
第3版前言
第2版前言
第1版前言
第0章绪论
01自动机、可计算性与复杂性
011计算复杂性理论
012可计算性理论
013自动机理论
02数学概念和术语
021集合
022序列和多元组
023函数和关系
024图
025字符串和语言
026布尔逻辑
027数学名词汇总
03定义、定理和证明
04证明的类型
041构造性证明
042反证法
043归纳法
练习
问题
习题选解
第一部分自动机与语言
第1章正则语言
11有穷自动机
111有穷自动机的形式化定义
112有穷自动机举例
113计算的形式化定义
114设计有穷自动机
115正则运算
12非确定性
121非确定型有穷自动机的形式化定义
122NFA与DFA的等价性
123在正则运算下的封闭性
13正则表达式
131正则表达式的形式化定义
132与有穷自动机的等价性
14非正则语言
练习
问题
习题选解
第2章上下文无关文法
21上下文无关文法概述
211上下文无关文法的形式化定义
212上下文无关文法举例
213设计上下文无关文法
214歧义性
215乔姆斯基范式
22下推自动机
221下推自动机的形式化定义
222下推自动机举例
223与上下文无关文法的等价性
23非上下文无关语言
24确定型上下文无关语言
241DCFL的性质
242确定型上下文无关文法
243DPDA和DCFG的关系
244语法分析和LR(k)文法
练习
问题
习题选解
第二部分可计算性理论
第3章丘奇图灵论题
31图灵机
311图灵机的形式化定义
312图灵机的例子
32图灵机的变形
321多带图灵机
322非确定型图灵机
323枚举器
324与其他模型的等价性
33算法的定义
331希尔伯特问题
332描述图灵机的术语
练习
问题
习题选解
第4章可判定性
41可判定语言
411与正则语言相关的可判定性问题
412与上下文无关语言相关的可判定性问题
42不可判定性
421对角化方法
422不可判定语言
423一个图灵不可识别语言
练习
问题
习题选解
第5章可归约性
51语言理论中的不可判定问题
52一个简单的不可判定问题
53映射可归约性
531可计算函数
532映射可归约性的形式化定义
练习
问题
习题选解
第6章可计算性理论的高级专题
61递归定理
611自引用
612递归定理的术语
613应用
62逻辑理论的可判定性
621一个可判定的理论
622一个不可判定的理论
63图灵可归约性
64信息的定义
641极小长度的描述
642定义的优化
643不可压缩的串和随机性
练习
问题
习题选解
第三部分复杂性理论
第7章时间复杂性
71度量复杂性
711大O和小o记法
712分析算法
713模型间的复杂性关系
72P类
721多项式时间
722P中的问题举例
73NP类
731NP中的问题举例
732P与NP问题
74NP完全性
741多项式时间可归约性
742NP完全性的定义
743库克列文定理
75几个NP完全问题
751顶点覆盖问题
752哈密顿路径问题
753子集和问题
练习
问题
习题选解
第8章空间复杂性
81萨维奇定理
82PSPACE类
83PSPACE完全性
831TQBF问题
832博弈的必胜策略
833广义地理学
84L类和NL类
85NL完全性
86NL等于coNL
练习
问题
习题选解
第9章难解性
91层次定理
92相对化
93电路复杂性
练习
问题
习题选解
第10章复杂性理论高级专题
101近似算法
102概率算法
1021BPP类
1022素数性
1023只读一次的分支程序
103交错式
1031交错式时间与交错式空间
1032多项式时间层次
104交互式证明系统
1041图的非同构
1042模型的定义
1043IP=PSPACE
105并行计算
1051一致布尔电路
1052NC类
1053P完全性
106密码学
1061密钥
1062公钥密码系统
1063单向函数
1064天窗函数
练习
问题
习题选解
参考文献
索引