基本信息
- 作者： （美）迈克尔·西普塞(Michael Sipser)
- 译者： 段磊 唐常杰
- 丛书名： 计算机科学丛书
- 出版社：机械工业出版社
- ISBN：9787111499718
- 上架时间：2015-7-29
- 出版日期：2015 年8月
- 开本：16开
- 页码：296
- 版次：1-1
- 所属分类：计算机 > 计算机科学理论与基础知识 > 计算理论 > 综合
教材
编辑推荐
《计算理论导引(原书第3版)》由机械工业出版社出版。
内容简介
作译者
作者：（美国）迈克尔·西普塞（Michael Sipser） 译者：段磊 唐常杰
目录
Introduction to the Theory of Computation,3e
出版者的话
译者序
第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定义、定理和证明
出版者的话
译者序
第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定义、定理和证明
译者序
Introduction to the Theory of Computation,3e
计算机改变并持续改变着世界，如今，计算技术已把人们带进了云（云计算）、物（物联网）、人（社会计算）、海（海量数据、大数据）的新时代。
在变革的时代里，计算机系统也改变着自己，在进步和进化中遵循了一组潜规则——计算理论，这套理论描述和论证了计算机的能与不能，界定了计算能力的极限。
业内人士常评说某人为某问题设计了一个比较快的算法，好到什么程度？用专业术语描述，线性时间内能完成的比较快，多项式时间能完成的次之，不能在多项式时间内完成的就是不现实的。但是，大数据时代的来临修正了这一观念，对于大数据问题，线性时间也嫌太长，因为需要“等它一千年”，人们呼唤亚线性、亚亚线性的算法。
有些问题，人们已经找到快的算法；有些问题，还没有找到快的算法，也许是等一个聪明程序员的出现。但有一类问题，没有找到好算法不是因为人们不够聪明，而是根本就不存在这样的算法。
计算理论将描述算法的本质，揭示计算机算法的能与不能、快与慢以及足够快的近似技巧。从这个角度来看，计算理论是计算机的灵魂，是应用计算机成功解决实际问题的保障。
这本由麻省理工学院名师Michael Sipser编撰的名著是计算理论领域的优秀书籍之一，对于非纯理论专业的人士，也许是深浅程度最合适的。自1996年第1版问世，该书历经近二十年，获得了学术界的公认和教育界的好评。该书具有如下优点：
第一，内容丰富，编排合理，展现了计算机科学研究的广度和深度。该书以理论计算机科学的知识框架为脉络，系统地讲述了自动机与形式语言、可计算性理论和计算复杂性理论等计算理论的重要内容。总体编排上，难度由浅入深、循序渐进，易于学习。
第二，文字清晰，语言生动。作者以引导、举例为叙述手段，对计算理论领域的重要定理、性质等不仅给出证明，而且讲述证明思路，着力让读者在学习理论的同时掌握证明的技巧，彰显了作者在此领域的深厚造诣和娴熟的教学手法。
第三，各章设有练习和问题，并提供了部分习题的解答。通过作答习题，能够锻炼读者的逻辑推导思维，加深读者对关键知识点的理解。
我以切身体会向计算机专业的高年级本科生、硕士生和博士生推荐此书。我在本科阶段第一次接触了该书的第1版。差不多10年前，在刚开始博士阶段学习时，参与了本书第2版的翻译工作。如今，我又引导我的学生学习这本书，并承担了第3版的翻译工作。作为多重身份的“过来人”，我有独特的体会。一方面，该书写作规范，研究生可以学习到规范的定义、性质、证明的表述方式，学习该书内容有助于提升计算理论素养，增强学习能力；另一方面，研究生多苦于论文理论深度不够，也不知如何分析问题，认真领会该书讲述的证明思路和解题思路，常会让我们有豁然开朗之感，问题分析能力随之增强，进而提高研究论文的水平。相较于本书第2版，第3版的内容更新主要在于增加了关于确定型上下文无关语言的阐述，这使得本书关于自动机理论和语言处理的介绍更为完整。此外，第3版对每章后的习题进行了增补和重新编排。除了对第3版新增和修正内容进行翻译以外，我们还对第2版译文的错误进行了更正。同时，我们尽可能保持新版译文的文风与第2版译文一致。本书由段磊、唐常杰主译，王文韬、王怡宁、杨皓、王梦洁也付出了艰辛的努力。如同我们在完成本书第2版翻译工作时所言，本书第3版的翻译工作是在先行者们工作的基础上，再次接过接力棒，把接力赛再推进一程。借此机会，向本书第1版译者（北京大学的张立昂教授、王捍贫教授和黄雄老师）表示衷心的感谢，也向本书第2版译者表示衷心的感谢。同时，华章公司的姚蕾、朱劼编辑在翻译过程中给予了我们大力支持，向她们表示衷心的感谢。特别向阅读本书第2版译文并给予我们翻译指正的读者表示衷心的感谢。
由于水平有限，译文难免有错误和不妥之处，恳请读者批评指正。
段磊
2015年6月于四川大学
计算机改变并持续改变着世界，如今，计算技术已把人们带进了云（云计算）、物（物联网）、人（社会计算）、海（海量数据、大数据）的新时代。
在变革的时代里，计算机系统也改变着自己，在进步和进化中遵循了一组潜规则——计算理论，这套理论描述和论证了计算机的能与不能，界定了计算能力的极限。
业内人士常评说某人为某问题设计了一个比较快的算法，好到什么程度？用专业术语描述，线性时间内能完成的比较快，多项式时间能完成的次之，不能在多项式时间内完成的就是不现实的。但是，大数据时代的来临修正了这一观念，对于大数据问题，线性时间也嫌太长，因为需要“等它一千年”，人们呼唤亚线性、亚亚线性的算法。
有些问题，人们已经找到快的算法；有些问题，还没有找到快的算法，也许是等一个聪明程序员的出现。但有一类问题，没有找到好算法不是因为人们不够聪明，而是根本就不存在这样的算法。
计算理论将描述算法的本质，揭示计算机算法的能与不能、快与慢以及足够快的近似技巧。从这个角度来看，计算理论是计算机的灵魂，是应用计算机成功解决实际问题的保障。
这本由麻省理工学院名师Michael Sipser编撰的名著是计算理论领域的优秀书籍之一，对于非纯理论专业的人士，也许是深浅程度最合适的。自1996年第1版问世，该书历经近二十年，获得了学术界的公认和教育界的好评。该书具有如下优点：
第一，内容丰富，编排合理，展现了计算机科学研究的广度和深度。该书以理论计算机科学的知识框架为脉络，系统地讲述了自动机与形式语言、可计算性理论和计算复杂性理论等计算理论的重要内容。总体编排上，难度由浅入深、循序渐进，易于学习。
第二，文字清晰，语言生动。作者以引导、举例为叙述手段，对计算理论领域的重要定理、性质等不仅给出证明，而且讲述证明思路，着力让读者在学习理论的同时掌握证明的技巧，彰显了作者在此领域的深厚造诣和娴熟的教学手法。
第三，各章设有练习和问题，并提供了部分习题的解答。通过作答习题，能够锻炼读者的逻辑推导思维，加深读者对关键知识点的理解。
我以切身体会向计算机专业的高年级本科生、硕士生和博士生推荐此书。我在本科阶段第一次接触了该书的第1版。差不多10年前，在刚开始博士阶段学习时，参与了本书第2版的翻译工作。如今，我又引导我的学生学习这本书，并承担了第3版的翻译工作。作为多重身份的“过来人”，我有独特的体会。一方面，该书写作规范，研究生可以学习到规范的定义、性质、证明的表述方式，学习该书内容有助于提升计算理论素养，增强学习能力；另一方面，研究生多苦于论文理论深度不够，也不知如何分析问题，认真领会该书讲述的证明思路和解题思路，常会让我们有豁然开朗之感，问题分析能力随之增强，进而提高研究论文的水平。相较于本书第2版，第3版的内容更新主要在于增加了关于确定型上下文无关语言的阐述，这使得本书关于自动机理论和语言处理的介绍更为完整。此外，第3版对每章后的习题进行了增补和重新编排。除了对第3版新增和修正内容进行翻译以外，我们还对第2版译文的错误进行了更正。同时，我们尽可能保持新版译文的文风与第2版译文一致。本书由段磊、唐常杰主译，王文韬、王怡宁、杨皓、王梦洁也付出了艰辛的努力。如同我们在完成本书第2版翻译工作时所言，本书第3版的翻译工作是在先行者们工作的基础上，再次接过接力棒，把接力赛再推进一程。借此机会，向本书第1版译者（北京大学的张立昂教授、王捍贫教授和黄雄老师）表示衷心的感谢，也向本书第2版译者表示衷心的感谢。同时，华章公司的姚蕾、朱劼编辑在翻译过程中给予了我们大力支持，向她们表示衷心的感谢。特别向阅读本书第2版译文并给予我们翻译指正的读者表示衷心的感谢。
由于水平有限，译文难免有错误和不妥之处，恳请读者批评指正。
段磊
2015年6月于四川大学
前言
第3版前言
Introduction to the Theory of Computation,3e
本版新增了关于确定型上下文无关语言的一节。我选择这个主题有以下几个原因。首先，它填补了我之前对自动机理论和语言处理之间的明显空白。以前的版本介绍了有穷自动机以及图灵机在确定型和非确定型上的变形，但却只包含了下推自动机的非确定型变形。因此，增加关于确定型下推自动机的讨论正如同找到完成拼图游戏所缺的那块。
其次，确定型上下文无关文法理论是LR(k)文法的基础，同时也是自动机理论在编程语言和编译器设计上重要且非平凡应用的基础。这个应用将一些关键概念，包括确定型和非确定型有穷自动机的等价性、上下文无关文法和下推自动机之间的相互转换，汇聚一起得到一个高效且漂亮的语法分析方法。这里我们实现了理论和实践的相互联系。
最后，虽然该主题作为自动机理论一个真实的应用非常重要，但它在现有理论教科书中却没有得到足够重视。我研究LR(k)文法多年但一直没有完整理解它们如何工作，也没有看到它们与确定型上下文无关语言理论的完美契合。我写作这一节旨在为理论学者和实践者提供关于这个领域直观而不失严谨的介绍，并由此对该领域做出贡献。需要注意的是：这一节的部分内容非常具有挑战性，因此基础理论课程的教师可考虑将其作为补充读物。之后的章节不依赖于这部分内容。
在撰写本版的过程中，很多人给了我直接或间接的帮助。我很感激两位审阅者Christos Kapoutsis和Cem Say。他们阅读了这一版新内容的初稿，并提供了很有价值的反馈意见。在Cengage Learning的一些人协助了本书的出版工作，特别是Alyssa Pratt和Jennifer FeltriGeorge。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, ChengChung Li, Xiangdong Liang, Vladimir Lifschitz, Ryan Lortie, Jonathan Low, Nancy Lynch, Alexis Maciel, Kevin Matulef, Nelson Max, HansRudolf Metz, Mladen Mika, 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 BingYi Wang, Lutz Warnke, David Warren, Thomas Watson, Joseph Wilson, David Wittenberg, Brian Wongchaowart, Kishan Yerubandi, Dai Yi。
最重要的是，我要感谢我的家人——我的妻子Ina以及我们的孩子Rachel和Aaron。时光荏苒，岁月如梭，你们的爱就是一切。
Michael Sipser
马萨诸塞州，剑桥
2012年4月
第2版前言
Introduction to the Theory of Computation,3e
大量读者来的电子邮件反映，第1版没有习题解答是一个缺陷。这一版弥补了这一缺陷。每一章现在都增加了“习题选解”小节，给出了该章的练习和问题中有代表性题目的答案。给出了答案的问题就不能再作为有趣的有挑战性的家庭作业，为弥补这一损失，又添加了若干新问题。教师可以和www.course.com上所指定的相应地区的销售代表联系，索取一份教师手册，其中包含了附加的答案。
第2版的国际版是针对国外读者的。尽管涵盖了同样的主题，它和标准第2版还是有所不同，并且不是用来替代标准第2版的。
许多读者更喜欢学习更多的“标准”主题，比如MyhillNerode定理和Rice定理。通过将这些主题展示在给出答案的问题中，我部分地采纳了这些读者的意见。没有将MyhillNerode定理放到书本主体中是因为我认为，这门课程的目标是初步介绍而非深入研究有穷自动机。有穷自动机在这里的角色是使学生通过研究计算的简单形式模型，为了解复杂模型奠定基础，同时为后续的主题提供方便的例子。当然，一些人希望有更全面的内容，同时另一些人觉得应该略去所有对有穷自动机的引用（或者至少是依赖）。尽管Rice定理对于不可判定性的证明是一个有用的“工具”，第2版还是没有将它放到书本主体中，因为一些学生可能只是机械地使用它而没有真正理解其作用。换用归约来证明不可判定性，可以为学习复杂性理论中出现的归约做更好的准备。
我很感谢我的助教Ilya Baran、Sergi Elizalde、Rui Fan、Jonathan Feldman、Venkatesan Guruswami、Prahladh Harsha、Christos Kapoutsis、Julia Khodor、Adam Klivans、Kevin Matulef、Ioana Popescu、April Rasala、Sofya Raskhodnikova和Iuliu Vasilescu，他们帮助我草拟了若干新问题及其答案。Ching Law、Edmond Kayi Lee和Zulfikar Ramzan也为给出答案付出了努力。感谢Victor Shoup提出了一个简洁的方法，用于修整在第1版中出现在概率原始算法分析中的缺陷。
感谢Course Technology出版社的编辑们的努力，尤其是Alyssa Pratt和Aimee Poirier。多谢Gerald Eisman、Weizhen Mao、Rupak Majumdar、Chris Umans和Christopher Wilson所做的审校。感谢Jerry Moore在编辑上的出色工作，还有ByteGraphics的Laura Segel (lauras@bytegraphics.com) 精彩而又精确的图表再现。
Introduction to the Theory of Computation,3e
本版新增了关于确定型上下文无关语言的一节。我选择这个主题有以下几个原因。首先，它填补了我之前对自动机理论和语言处理之间的明显空白。以前的版本介绍了有穷自动机以及图灵机在确定型和非确定型上的变形，但却只包含了下推自动机的非确定型变形。因此，增加关于确定型下推自动机的讨论正如同找到完成拼图游戏所缺的那块。
其次，确定型上下文无关文法理论是LR(k)文法的基础，同时也是自动机理论在编程语言和编译器设计上重要且非平凡应用的基础。这个应用将一些关键概念，包括确定型和非确定型有穷自动机的等价性、上下文无关文法和下推自动机之间的相互转换，汇聚一起得到一个高效且漂亮的语法分析方法。这里我们实现了理论和实践的相互联系。
最后，虽然该主题作为自动机理论一个真实的应用非常重要，但它在现有理论教科书中却没有得到足够重视。我研究LR(k)文法多年但一直没有完整理解它们如何工作，也没有看到它们与确定型上下文无关语言理论的完美契合。我写作这一节旨在为理论学者和实践者提供关于这个领域直观而不失严谨的介绍，并由此对该领域做出贡献。需要注意的是：这一节的部分内容非常具有挑战性，因此基础理论课程的教师可考虑将其作为补充读物。之后的章节不依赖于这部分内容。
在撰写本版的过程中，很多人给了我直接或间接的帮助。我很感激两位审阅者Christos Kapoutsis和Cem Say。他们阅读了这一版新内容的初稿，并提供了很有价值的反馈意见。在Cengage Learning的一些人协助了本书的出版工作，特别是Alyssa Pratt和Jennifer FeltriGeorge。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, ChengChung Li, Xiangdong Liang, Vladimir Lifschitz, Ryan Lortie, Jonathan Low, Nancy Lynch, Alexis Maciel, Kevin Matulef, Nelson Max, HansRudolf Metz, Mladen Mika, 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 BingYi Wang, Lutz Warnke, David Warren, Thomas Watson, Joseph Wilson, David Wittenberg, Brian Wongchaowart, Kishan Yerubandi, Dai Yi。
最重要的是，我要感谢我的家人——我的妻子Ina以及我们的孩子Rachel和Aaron。时光荏苒，岁月如梭，你们的爱就是一切。
Michael Sipser
马萨诸塞州，剑桥
2012年4月
第2版前言
Introduction to the Theory of Computation,3e
大量读者来的电子邮件反映，第1版没有习题解答是一个缺陷。这一版弥补了这一缺陷。每一章现在都增加了“习题选解”小节，给出了该章的练习和问题中有代表性题目的答案。给出了答案的问题就不能再作为有趣的有挑战性的家庭作业，为弥补这一损失，又添加了若干新问题。教师可以和www.course.com上所指定的相应地区的销售代表联系，索取一份教师手册，其中包含了附加的答案。
第2版的国际版是针对国外读者的。尽管涵盖了同样的主题，它和标准第2版还是有所不同，并且不是用来替代标准第2版的。
许多读者更喜欢学习更多的“标准”主题，比如MyhillNerode定理和Rice定理。通过将这些主题展示在给出答案的问题中，我部分地采纳了这些读者的意见。没有将MyhillNerode定理放到书本主体中是因为我认为，这门课程的目标是初步介绍而非深入研究有穷自动机。有穷自动机在这里的角色是使学生通过研究计算的简单形式模型，为了解复杂模型奠定基础，同时为后续的主题提供方便的例子。当然，一些人希望有更全面的内容，同时另一些人觉得应该略去所有对有穷自动机的引用（或者至少是依赖）。尽管Rice定理对于不可判定性的证明是一个有用的“工具”，第2版还是没有将它放到书本主体中，因为一些学生可能只是机械地使用它而没有真正理解其作用。换用归约来证明不可判定性，可以为学习复杂性理论中出现的归约做更好的准备。
我很感谢我的助教Ilya Baran、Sergi Elizalde、Rui Fan、Jonathan Feldman、Venkatesan Guruswami、Prahladh Harsha、Christos Kapoutsis、Julia Khodor、Adam Klivans、Kevin Matulef、Ioana Popescu、April Rasala、Sofya Raskhodnikova和Iuliu Vasilescu，他们帮助我草拟了若干新问题及其答案。Ching Law、Edmond Kayi Lee和Zulfikar Ramzan也为给出答案付出了努力。感谢Victor Shoup提出了一个简洁的方法，用于修整在第1版中出现在概率原始算法分析中的缺陷。
感谢Course Technology出版社的编辑们的努力，尤其是Alyssa Pratt和Aimee Poirier。多谢Gerald Eisman、Weizhen Mao、Rupak Majumdar、Chris Umans和Christopher Wilson所做的审校。感谢Jerry Moore在编辑上的出色工作，还有ByteGraphics的Laura Segel (lauras@bytegraphics.com) 精彩而又精确的图表再现。
序言
出版者的话
Introduction to the Theory of Computation, 3e
文艺复兴以来，源远流长的科学精神和逐步形成的学术规范，使西方国家在自然科学的各个领域取得了垄断性的优势；也正是这样的优势，使美国在信息技术发展的六十多年间名家辈出、独领风骚。在商业化的进程中，美国的产业界与教育界越来越紧密地结合，计算机学科中的许多泰山北斗同时身处科研和教学的最前线，由此而产生的经典科学著作，不仅擘划了研究的范畴，还揭示了学术的源变，既遵循学术规范，又自有学者个性，其价值并不会因年月的流逝而减退。
近年，在全球信息化大潮的推动下，我国的计算机产业发展迅猛，对专业人才的需求日益迫切。这对计算机教育界和出版界都既是机遇，也是挑战；而专业教材的建设在教育战略上显得举足轻重。在我国信息技术发展时间较短的现状下，美国等发达国家在其计算机科学发展的几十年间积淀和发展的经典教材仍有许多值得借鉴之处。因此，引进一批国外优秀计算机教材将对我国计算机教育事业的发展起到积极的推动作用，也是与世界接轨、建设真正的世界一流大学的必由之路。
机械工业出版社华章公司较早意识到“出版要为教育服务”。自1998 年开始，我们就将工作重点放在了遴选、移译国外优秀教材上。经过多年的不懈努力，我们与Pearson，McGraw-Hill，Elsevier，MIT，John Wiley & Sons，Cengage 等世界著名出版公司建立了良好的合作关系， 从他们现有的数百种教材中甄选出Andrew S. Tanenbaum，Bjarne Stroustrup，Brain W. Kernighan，Dennis Ritchie，Jim Gray，Afred V. Aho，John E. Hopcroft，Jeffrey D. Ullman，Abraham Silberschatz，William Stallings，Donald E. Knuth，John L. Hennessy，Larry L. Peterson 等大师名家的一批经典作品，以“计算机科学丛书”为总称出版，供读者学习、研究及珍藏。大理石纹理的封面，也正体现了这套丛书的品位和格调。
“计算机科学丛书”的出版工作得到了国内外学者的鼎力相助，国内的专家不仅提供了中肯的选题指导，还不辞劳苦地担任了翻译和审校的工作；而原书的作者也相当关注其作品在中国的传播，有的还专门为其书的中译本作序。迄今，“计算机科学丛书”已经出版了近两百个品种，这些书籍在读者中树立了良好的口碑，并被许多高校采用为正式教材和参考书籍。其影印版“经典原版书库”作为姊妹篇也被越来越多实施双语教学的学校所采用。
权威的作者、经典的教材、一流的译者、严格的审校、精细的编辑，这些因素使我们的图书有了质量的保证。随着计算机科学与技术专业学科建设的不断完善和教材改革的逐渐深化，教育界对国外计算机教材的需求和应用都将步入一个新的阶段，我们的目标是尽善尽美，而反馈的意见正是我们达到这一终极目标的重要帮助。华章公司欢迎老师和读者对我们的工作提出建议或给予指正，我们的联系方法如下：
华章网站：www.hzbook.com
电子邮件：hzjsj@hzbook.com
联系电话： （010）88379604
联系地址：北京市西城区百万庄南街1号
邮政编码：100037
Introduction to the Theory of Computation, 3e
文艺复兴以来，源远流长的科学精神和逐步形成的学术规范，使西方国家在自然科学的各个领域取得了垄断性的优势；也正是这样的优势，使美国在信息技术发展的六十多年间名家辈出、独领风骚。在商业化的进程中，美国的产业界与教育界越来越紧密地结合，计算机学科中的许多泰山北斗同时身处科研和教学的最前线，由此而产生的经典科学著作，不仅擘划了研究的范畴，还揭示了学术的源变，既遵循学术规范，又自有学者个性，其价值并不会因年月的流逝而减退。
近年，在全球信息化大潮的推动下，我国的计算机产业发展迅猛，对专业人才的需求日益迫切。这对计算机教育界和出版界都既是机遇，也是挑战；而专业教材的建设在教育战略上显得举足轻重。在我国信息技术发展时间较短的现状下，美国等发达国家在其计算机科学发展的几十年间积淀和发展的经典教材仍有许多值得借鉴之处。因此，引进一批国外优秀计算机教材将对我国计算机教育事业的发展起到积极的推动作用，也是与世界接轨、建设真正的世界一流大学的必由之路。
机械工业出版社华章公司较早意识到“出版要为教育服务”。自1998 年开始，我们就将工作重点放在了遴选、移译国外优秀教材上。经过多年的不懈努力，我们与Pearson，McGraw-Hill，Elsevier，MIT，John Wiley & Sons，Cengage 等世界著名出版公司建立了良好的合作关系， 从他们现有的数百种教材中甄选出Andrew S. Tanenbaum，Bjarne Stroustrup，Brain W. Kernighan，Dennis Ritchie，Jim Gray，Afred V. Aho，John E. Hopcroft，Jeffrey D. Ullman，Abraham Silberschatz，William Stallings，Donald E. Knuth，John L. Hennessy，Larry L. Peterson 等大师名家的一批经典作品，以“计算机科学丛书”为总称出版，供读者学习、研究及珍藏。大理石纹理的封面，也正体现了这套丛书的品位和格调。
“计算机科学丛书”的出版工作得到了国内外学者的鼎力相助，国内的专家不仅提供了中肯的选题指导，还不辞劳苦地担任了翻译和审校的工作；而原书的作者也相当关注其作品在中国的传播，有的还专门为其书的中译本作序。迄今，“计算机科学丛书”已经出版了近两百个品种，这些书籍在读者中树立了良好的口碑，并被许多高校采用为正式教材和参考书籍。其影印版“经典原版书库”作为姊妹篇也被越来越多实施双语教学的学校所采用。
权威的作者、经典的教材、一流的译者、严格的审校、精细的编辑，这些因素使我们的图书有了质量的保证。随着计算机科学与技术专业学科建设的不断完善和教材改革的逐渐深化，教育界对国外计算机教材的需求和应用都将步入一个新的阶段，我们的目标是尽善尽美，而反馈的意见正是我们达到这一终极目标的重要帮助。华章公司欢迎老师和读者对我们的工作提出建议或给予指正，我们的联系方法如下：
华章网站：www.hzbook.com
电子邮件：hzjsj@hzbook.com
联系电话： （010）88379604
联系地址：北京市西城区百万庄南街1号
邮政编码：100037
媒体评论
本书由计算理论领域的知名权威Michael Sipser所撰写。他以独特的视角，系统地介绍了计算理论的三个主要内容：自动机与语言、可计算性理论和计算复杂性理论。绝大部分内容是基本的，同时对可计算性和计算复杂性理论中的某些高级内容进行了重点介绍。作者以清新的笔触、生动的语言给出了宽泛的数学原理，而没有拘泥于某些低层次的细节。在证明之前，均有“证明思路”，帮助读者理解数学形式下蕴涵的概念。同样，对于算法描述，均以直观的文字而非伪代码给出，从而将注意力集中于算法本身，而不是某些模型。新版根据多年来使用本书的教师和学生的建议进行了改进，并用一节的篇幅对确定型上下文无关语言进行了直观而不失严谨的介绍。此外，对练习和问题进行了全面更新，每章末均有习题选答。
书摘
现在采用归纳法来证明房产抵押贷款的月付款计算公式的正确性。很多人借钱买房子并且在若干年内应偿还这笔贷款。如果要求在30年内还清贷款，典型的方法是，在还贷条款中规定每个月支付固定偿还款额，其中应包括利息以及部分原贷款金额。计算月付款钱数的公式看起来神秘，其实十分简单。但它关系到大多数人的日常生活，因此你一定对它感兴趣。我们用归纳法来证明这个公式的正确性，这对归纳法是个很好的说明。
首先，给出几个变量的名称及其含义。设P为贷款原始数额，称为本金。I>0为贷款的年利率，1=0.06表示年利率为6%，Y为月付款数。为简便起见，用I定义另一个变量M，它表示月倍增系数。因为有利息的缘故，所以贷款的余额每个月按照比率M会发生变化。因为月利率是年利率的1／12，所以M=1 I／12，并且逐月付利息（按月复利）。
首先，给出几个变量的名称及其含义。设P为贷款原始数额，称为本金。I>0为贷款的年利率，1=0.06表示年利率为6%，Y为月付款数。为简便起见，用I定义另一个变量M，它表示月倍增系数。因为有利息的缘故，所以贷款的余额每个月按照比率M会发生变化。因为月利率是年利率的1／12，所以M=1 I／12，并且逐月付利息（按月复利）。
