本书由该领域著名专家兼教育家所著。作者以独特的直觉及广阔的视角向读者展现了计算机科学理论。作者将其清晰而生动的研究建立在广泛的数学规律的基础上．而不是拘泥于低水平的技术细节。比如：对每个论据均提供了“论点“，该论点揭示了数学公式的概念。同样为使读者注重算法本身而不是具体模型，本书用语言而不是伪代码讲述了算法。本书在MIT的讲义的基础上增加了一些内容，如空间复杂性(第3章)．可证明的难题(第9章)和关于计算理论的高级话题(第10章)。关于本书的详细内容，可访问网站：http：／／www-math．mit．edu／～sipser／book.html。

TO THE STUDENT
　　Welcome !
　　Yon are about to embark on the study of a fascinating and important subject: the theory of compuation. It comprises the fundamental mathematical properties of computer hardware, software, and certain applications thereof. In studying this subject we seek to determine what can and cannot be computed, how quickly, with how muck memory, and on which type ofcompuational model. The subject has obvious connections with engineering practice, and, as in many sciences, it also has purely philosophial aspects.
　　I know that many ofyou are lookiog forward to studying this material but some may not be here out of choice. You may want to obtain a degree in compater science or engineering, and a course in theory is required-God knows why. After all, isn't theory arcane, boring, and worst of all, irrelevant?
　　To see that theory is neither arcane nor boring, but instead quite understandable and even interesting, read on. Theoretical computer science does have many fascinating big ideas, but it also has many small and sometimes dull details that can be tiresome. Learning any new subject is hard work but it becomes easier and more enjoyable if the subject is properly presented. My primary objective in writing this book is to expose you to the genuinely exciting aspects of computer theory, without getting bogged down in the drudgery. Of course, the only way to determine whether theory interests you is to try learning it.
　　Theory is relevant to practice. It provides conceptual tools that practitioners use in computer engineeting. Designing a new pro cialized application? What you learned about gr handy. Dealing with string searching and pattern .matching? Rememberfinite automata and regular expressions. Confronted with a problem that seems to require more computer time than you can afford? Think back to what you learned about NP-completeness. Various application areas, such as modem cryptographic protocols, rely on theoretical principles that you will learn here.
　　Theory also is relevant to you because it shows you a new, simpler, and more elegant side of computers, which we normally consider to be compliated'machines. The best computer designs and appliations are conceived with elegance in mind. A theoretical course can heighten your aesthetic sense and help you build more beautiful systems.
　　Finally, theory is good for you because studying it expands your mind. Computer technology changes quickly. Specific technical knowledge, though useful-today, becomes outdated in just a few years. Consider instead the abilities to think, to express yourself clearly and precisely, to solve problems, and to know when you haven't solved a problem. These abilities have lasting value. Studying theory trains you in these areas.
　　Practical considerations aside, nearly everyone working with computers is curious aboot these amazing creations, their apabilities, and their limitations. A whole new branch of mathematics has grown up in the past 30 years to answer certain basic questions. Here's a big one that remains unsolved: If I give you a large number, say, with 500 digits, can you find in factors (the numbers that divide it evenly), in a reasonable amount of time? Even using a supercomputer, no one presently knows how to do that in all cases witbin the lifetime of the universe!
　　The factoring problem is connected to certain secret codes in modern cryptosystems. Find a fast way to factor and fame is yours!
　　
TO THE EDUC.ATOR
　　This book is intended as an upper-level undergraduate or introductory graduate text in computer science theory. It conains a mathematical treatment ofthe subject, designed around theorems and proofs. I have made some effort to accommodate students with little prior experience in proving theorems, though more experienced students will have an easier time.
　　My primary goal in presenting the material has been to make it clear and interesting. In so doing, I have emphasized intuition and "the big picture" in the subject over some lower level details.
　　For example, even though I present the method ofproofby induction in Chapter O along with other mathematial preliminaries preliminaries, it doesn't play an important role subsequently. Generally I do not present the usual induction proofs of the correctness of various constructions concerning automata. If presented clearly, these constructions convince and do not need further argument An induction may confuse rather than enlighten because induction itself is a rather sophisticated technique that many and mysterious. Belaboring the obvioas with an induction risks teaching students that mathematical proof is a formal manipulation instead of teaching them what is and what is not a cogent argument.
　　A second example occurs in Parts II and III, where I describe algorithms in prose instead of pseudocode. I don't spend much time programming Turing machines (or any other formal model). Students today come with a pro background and find the Church-Turing thesis to be self-evident. Hence I don't present lengthly simulations of one model by another to establish their equivalence.
　　Besides giving extra intuition and suppressing some details, I give what might be called a classical presentation of the subject material. Most theorist will find the choice of material, terminology, and order of presentation consistent with that of other widely used textbooks. I have introduced original terminology only a few places, when I found the standard terminology particularly obscure or confusing. For example I introduce the term mapping reducibility instead of many-one reducibility.
　　Practice through solving problems is essential to learning any mathematical subject In this book, the problems are organized into two main categories called Exercises and Problems. The Exercises review definitions and concepts. The Problems require some ingenuity. Problems marked with a sar are more difficult. I have tried to make both the Exercises and Problems interesting challenges.
　　
THE CURRENT EDITION
　　Introduction to the Theory of computation first appeared as a Preliminary Edition in paperback The current edition differs from the Preliminary Edition in several substantial ways. The final three chapters are new: Chapter 8 on space complexity Chapter 9 on provable intractability; and Chapter 10 on advanced topics in complexity theory. Chapter 6 was expanded to include several advanced topics in computability theory. Other chapters were improved through the inclusion of additional example and exercises.
　　Comments from instructors and students who used the Pre
were helpful in polishing Chapters 0-7. Of course, the errors they reported have been corrected in this edition.
　　Chapters 6 and 10 give a survey of several more advanced topics in computability and complexity theories. They are not intended to comprise a cohesive unit in the way that the remaining chapters are. These chapters are included to allow the instructor to select optional topics that may be of interest to the serious student The topics themselves range widely. Some, such as Turing reducibility and alternation, are direct extensions of other concepts in the book Others, such as decidable logical theories and cryptography, are brief introductions to large fields.
　　
FEEDBACK TO THE AUTHOR
　　The internet provides new opportunities for interaction between authors and readers. I have received much e-mail offering suggestions, praise, and criticism, and reporting errors for the Preliminary Edition. Please continue to correspond!I try to respond to each message personally, as time permits. The e-mail address for correspondence related to this book is sipserbook@math . mit . edu .
　　A web site that contains a list of errata is maintained. Other material may be added to that site to assist instructors and students. Let me know what you would like to see there. The location for that site is http : //www-math . mit . edu/sipser/book. html .

ACKNOWLEDGMENTS
　　I could not have written this book without the help of many friends, colleagues, and my family.
　　I wish to thank the teachers who helped shape my scientific viewpoint and educational style. Five of them stand out. My thesis advisor, Manuel Blum, is due a special note for his unique way of inspiring students through clarity of thought enthusiasm, and caring. He is a model for me and for many others. I am grateful to Richard Karp for introducing me to complexity theory, to John Addison for teaching me logic and assigning those wonderful homework sets, to Juris Hart-　manis for introducing me to the theory of computation, and to my father for introducing me to mathematics, computers, and the art of teaching.
　　This book grew out of notes from a course that I have taught at MIT for the past 15 years. Students in my classes took these notes from my Iectures. I hope they will forgive me for not listing them all. My teaching assistants over the years, Avrim Blum, Thang Bui, Andrew Chou, Benny Chor, Stavros Cosmadakis, Aditi Dhagat Wayne Goddard, Parry Husbands, Dina Kravets, Jakov Kucan. Brian O'Neill, loana Popescu, and Alex Russell, helped me to edit and expand these notes and provided some of the homework problems.
　　Nearly three years ago, Tom Leighton persuaded me to write a textbook on the theory of compuation. I had been thinking　of doing so for some time, but it took Tom's persuasion to turn theory into practice. I appreciate his generiys advice on book writing and on many other things.
　　I wish to thank Eric Bach, Peter Beebee, Cris Calude, Marek Chrobak Anna Chefter, Guang-len Cheng, Elias Dahlhaus, Michael Fischer, Steve Fisk, Lance Fortnow, Henry J. Friedman, Jack Fu, Seymour Ginsburg, Oded Goldreich, Brian Grossman, David Harel, Micha Hofri, Dung T Huynh, Neil Jones, H. Chad Lane, Kevin Lin, Michael Loui, Silvio Micali, Tadao Murata, Christos Papadimitriou, Vaughan Pratt Daniel Rosenband, Brian Scassellati, Ashish Sharma, Nir Shavit Alexander Shen, Ilya Shlyakhter, Matt S Susskind, Y C. Tay, Joseph Traub, Osamu Watanabe, Peter Widmayer, David Williamson, Derick Wood, and Charles Yang for comments, suggestions, and assistance as the writing progressed.
　　The following people provided additional comments that have improved this book Isam M. Abdelhameed, Eric Allender, Michelle Atherton, Rolfe Blodgett AI Briggs, Brian E. Brooks, Jonathan Buss,Jin Yi Cai, Steve Chapel, David Chow, Michael Ehrlich, Yaakov Eisenberg, Farzan Fallah, Shaun Flisakowski, Hjalmtyr Hafsteinsson, C. R. Hale, Maurice Herlihy, Vegard Holmedahl, Sandy Irani, Kevin Jiang, Rhys Price Jones, James M. Jowdy, David M. ManinJr., Manrique Mata-Montero, Ryota Matsuura, Thomas Minka, Farooq Mohammed, Tadao Murata,Jason Murray, Hideo Nagahashi, Kazuo Ohta, Consantine Papageorgiou, Joseph Raj, Rick Regan, Rhonda A. Reumann, Michael Rintzler, Arnold L. Rosenberg, Larry Roske, Max Rozenoer, Walter L. Ruzzo, Sanatan Sahgal, Leonard Schulman, Steve Seiden, Joel Seiferas, Ambuj Singh, David J. Stucki, Jayram S. Thathachar, H. Venkateswaran, Tom Whaley, Christopher Van Wyk, Kyle Young, and Kyoung Hwan Yun.
　　Robert Sloan used an early version of the manuscript for this book in a class that he taught and provided me with invaluable commentary and ideas from his experience with it. Mark Herschberg, Kazuo Ohta, and Latanya Sweeney read over parts of the mannscript and suggested extensive improvements. Shafi Gold-wasser helped me with material in Chapter 10.
　　I received expert technical support from William Baxter at Superscript, who wrote the LATEX macro package implementing the interior design, and from Larry Nolan at the MIT mathematics department, who keeps everything running.
　　It has been a pleasure to work with the folks at PWS Publishing in creating the final product. I mention Michael Sugarman, David Dietz, Elise Kaiser, Monique Calello, Susan Garland and Tanja Brull beause I have had the most contact with them, but I know that many others have been involved, too. Thanks to Jerry Moore for the copy editing, to Diane Levy for the cover design, and to Catherine Hawkes for the interior design.
　　I am grateful to the National Science Foundation for support provided under grant CCR-9503322.
　　My father, Kenneth Sipser, and sister, Laura Sipser, converted the book diagrams into electronic form. My other sister, Karen Fisch, saved us in various computer emergencies, and my mother, Justine Sipser, helped out with motherly advice. I thank them for contributing under difficult circumstances, including insane deadlines and recalcitrant software.
　　Finally, my love goes to my wife, Ina, and my daughter, Rachel. Thanks for putting up with all of this.
　　
Cambridge,Massacbusetts
Micbael Sipser
October,1996

Preface
To the student
To the educator
The current edition
Feedback to the author
Acknowledgments

0 Introduction
0. l Automata, Computability, and Complexity
Complexity theory
Computability theory
Automata theory
0.2 Mathematical Notions and Terminology
Sets
Sequences and tuples
Functions and relations
Graphs
Strings and languages
Boolean logic
Summary of mathematical terms
O.3 Definitions, Theorems, and Proofs
Finding proofs
0.4 Types of Proof
Proof by construction
Proof by contradiction
Proof by induction
Exercises and Problems

Part One: Automata and
l Regular
l . l Finite Automata
Formal definition of a finite automaton
Examples of finite automata
Formal definition of computation
Designing finite automata
The regular operations
l .2 Nondeterminism
Formal definition of a nondeterministic finite automaton
Equivalence of NFAs and DFAs
Closure under the regular operations
l . 3 Regular Expressions
Formal definition of a regular expression
Equivalence with finite automata
l .4 Nonregular Languages
The pumping lemma for regular languages
Exercises and Problems

2 Context-Free Languages
2 . l Context-free Grammars
Formal definition of a context-free grammar
Examples of context-free grammars
Designing context-free grammars
Ambiguity
Chomsky normal form
2 .2 Pushdown Automata
Formal definition of a pushdown automaton
Examples of pushdown automata
Equivalence with context-free grammars
2 . 3 Non-context-free Languages
The pumping lemma for context-free languages
Exercises and Problems

Part Two: Computability Theory
3 The Church-Turing Thesis
3 . l Turing Machines
Formal definition of a Turing machine
Examples of Turing　machines
3 .2 Variants of Turing Machines
Multitape Turing machines
Nondeterministic Turing machines
Enumerators
Equivalence with other models
3 .3 The Definition of Algorithm
Hilbert's problems
Terminology for describing Turing machines
Exercises and Problems

4 Decidability
4. l Decidable Languages
Decidable problems concerning regular languages
Decidable problems concerning context-free languages
4.2 The Halting Problem
The diagonalization method
The halting problem is undecidable
A Turing-unrecognizable language
Exercises and Problems

5 Reducibility
5 . l Undecidable Problems from Language Theory
Reductions via computation histories
5.2 A Simple Undecidable Problem
5 . 3 Mapping Reducibility
Computable functions
Formal definition of mapping reducibility
Exercises and Problems

6 Advanced Topics in Computability Theory
6. 1 The Recursion Theorem
Self-reference
Terminology for the recursion theorem
Applications
6.2 Decidability of logical theories
A decidable theory
An undecidable theory
6. 3 Turing Reducibility
6.4 A Definition of Information
Minimal length descriptions
Optimality of the definition
Incompressible Strings and randomness
Exercises and Problems

Part Three: Complexity Theory
7 Time Complexity
7. l Measuring Complexity
Big-O and small-o notation
Analyzing algorithms
Complexity relationships among models
7.2 The Class P
Polynomial time
Examples of problems in P
7.3 The Class NP
Examples of problems in NP
The P versus NP question
7 .4 NP-completeness
Polynomial time reducibility
Definition of NP-completeness
The Cook-Levin Theorem
7. 5 Additional NP-complete Problems
The vertex cover problem
The Hamiltonian path problem
The subset sum problem
Exercises and Problems

8 Space Complexity
8. l Savitch's Theorem
8.2 The Class PSPACE
8 . 3 PSPACE-completeness
The TQBF problem
Winning strategies for games
Generalized geography
8.4 The Classes Land NL
8. 5 NL-completeness
Searching in graphs
8.6 NL equals coNL
Exercises and Problems

9 Intractability
9. l Hierarchy Theorems
Exponential space completeness
9.2 Relativization
Limits of the diagonalization method
9. 3 Circuit Complexity
Exercises and Problems

10 Advanced topics in complexity theory
l0. l Approximation Algorithms
l0.2 Probabilistic Algorithms
The class BPP
Primality
Read-once branching programs
10.3 Alternation
Alternating time and space
The Polynomial time hierarchy
10.4 Interactive Proof Systems
Graph nonisomorphism
Definition of the model
IP = PSPACE
l0.5 Parallel Compuation
Uniform Boolean circuits
The class NC
P-completeness
IO.6 Cryptography
Secret keys
Public-key cryptosystems
One-way functions
Trapdoor functions
Exercises and Problems

Selected Bibliography
Index

无