Introduction to the Theory of Computation

by Sipser, Michael

• ISBN13: 9780534947286
• ISBN10: 053494728X
• Format: Hardcover
• Copyright: 1996-12-13
• Publisher: Cengage Learning

Summary

This highly anticipated revision of Michael Sipser's popular text builds upon the strengths of the previous edition. It tells the fascinating story of the theory of computation-a subject with beautiful results and exciting unsolved questions at the crossroads of mathematics and computer science. Sipser's candid, crystal-clear style allows students at every level to understand and enjoy this field. His innovative "proof idea" sections reveal the intuition underpinning the formal proofs of theorems by explaining profound concepts in plain English. The new edition incorporates many improvements students and professors have suggested over the years and offers completely updated, classroom-tested problem sets with sample solutions at the end of each chapter. Book jacket.

Author Biography

Michael Sipser is the head of the Mathematics Department. He enjoys teaching and pondering the many mysteries of complexity theory

Table of Contents

Preface to the First Edition	p. xi
To the student	p. xi
To the educator	p. xii
The first edition	p. xiii
Feedback to the author	p. xiii
Acknowledgments	p. xiv
Preface to the Second Edition	p. xvii
Introduction	p. 1
Automata, Computability, and Complexity	p. 1
Complexity theory	p. 2
Computability theory	p. 2
Automata theory	p. 3
Mathematical Notions and Terminology	p. 3
Sets	p. 3
Sequences and tuples	p. 6
Functions and relations	p. 7
Graphs	p. 10
Strings and languages	p. 13
Boolean logic	p. 14
Summary of mathematical terms	p. 16
Definitions, Theorems, and Proofs	p. 17
Finding proofs	p. 17
Types of Proof	p. 21
Proof by construction	p. 21
Proof by contradiction	p. 21
Proof by induction	p. 22
Exercises, Problems, and Solutions	p. 25
Automata and Languages	p. 29
Regular Languages	p. 31
Finite Automata	p. 31
Formal definition of a finite automaton	p. 35
Examples of finite automata	p. 37
Formal definition of computation	p. 40
Designing finite automata	p. 41
The regular operations	p. 44
Nondeterminism	p. 47
Formal definition of a nondeterministic finite automaton	p. 53
Equivalence of NFAs and DFAs	p. 54
Closure under the regular operations	p. 58
Regular Expressions	p. 63
Formal definition of a regular expression	p. 64
Equivalence with finite automata	p. 66
Nonregular Languages	p. 77
The pumping lemma for regular languages	p. 77
Exercises, Problems, and Solutions	p. 82
Context-Free Languages	p. 99
Context-free Grammars	p. 100
Formal definition of a context-free grammar	p. 102
Examples of context-free grammars	p. 103
Designing context-free grammars	p. 104
Ambiguity	p. 105
Chomsky normal form	p. 106
Pushdown Automata	p. 109
Formal definition of a pushdown automaton	p. 111
Examples of pushdown automata	p. 112
Equivalence with context-free grammars	p. 115
Non-context-free Languages	p. 123
The pumping lemma for context-free languages	p. 123
Exercises, Problems, and Solutions	p. 128
Computability Theory	p. 135
The Church-Turing Thesis	p. 137
Turing Machines	p. 137
Formal definition of a Turing machine	p. 139
Examples of Turing machines	p. 142
Variants of Turing Machines	p. 148
Multitape Turing machines	p. 148
Nondeterministic Turing machines	p. 150
Enumerators	p. 152
Equivalence with other models	p. 153
The Definition of Algorithm	p. 154
Hilbert's problems	p. 154
Terminology for describing Turing machines	p. 156
Exercises, Problems, and Solutions	p. 159
Decidability	p. 165
Decidable Languages	p. 166
Decidable problems concerning regular languages	p. 166
Decidable problems concerning context-free languages	p. 170
The Halting Problem	p. 173
The diagonalization method	p. 174
The halting problem is undecidable	p. 179
A Turing-unrecognizable language	p. 181
Exercises, Problems, and Solutions	p. 182
Reducibility	p. 187
Undecidable Problems from Language Theory	p. 188
Reductions via computation histories	p. 192
A Simple Undecidable Problem	p. 199
Mapping Reducibility	p. 206
Computable functions	p. 206
Formal definition of mapping reducibility	p. 207
Exercises, Problems, and Solutions	p. 211
Advanced Topics in Computability Theory	p. 217
The Recursion Theorem	p. 217
Self-reference	p. 218
Terminology for the recursion theorem	p. 221
Applications	p. 222
Decidability of logical theories	p. 224
A decidable theory	p. 227
An undecidable theory	p. 229
Turing Reducibility	p. 232
A Definition of Information	p. 233
Minimal length descriptions	p. 234
Optimality of the definition	p. 238
Incompressible strings and randomness	p. 239
Exercises, Problems, and Solutions	p. 242
Complexity Theory	p. 245
Time Complexity	p. 247
Measuring Complexity	p. 247
Big-O and small-o notation	p. 248
Analyzing algorithms	p. 251
Complexity relationships among models	p. 254
The Class P	p. 256
Polynomial time	p. 256
Examples of problems in P	p. 258
The Class NP	p. 264
Examples of problems in NP	p. 267
The P versus NP question	p. 269
NP-completeness	p. 271
Polynomial time reducibility	p. 272
Definition of NP-completeness	p. 276
The Cook-Levin Theorem	p. 276
Additional NP-complete Problems	p. 283
The vertex cover problem	p. 284
The Hamiltonian path problem	p. 286
The subset sum problem	p. 291
Exercises, Problems, and Solutions	p. 294
Space Complexity	p. 303
Savitch's Theorem	p. 305
The Class PSPACE	p. 308
PSPACE-completeness	p. 309
The TQBF problem	p. 310
Winning strategies for games	p. 313
Generalized geography	p. 315
The Classes L and NL	p. 320
NL-completeness	p. 323
Searching in graphs	p. 325
NL equals coNL	p. 326
Exercises, Problems, and Solutions	p. 328
Intractability	p. 335
Hierarchy Theorems	p. 336
Exponential space completeness	p. 343
Relativization	p. 348
Limits of the diagonalization method	p. 349
Circuit Complexity	p. 351
Exercises, Problems, and Solutions	p. 360
Advanced topics in complexity theory	p. 365
Approximation Algorithms	p. 365
Probabilistic Algorithms	p. 368
The class BPP	p. 368
Primality	p. 371
Read-once branching programs	p. 376
Alternation	p. 380
Alternating time and space	p. 381
The Polynomial time hierarchy	p. 386
Interactive Proof Systems	p. 387
Graph nonisomorphism	p. 387
Definition of the model	p. 388
IP = PSPACE	p. 390
Parallel Computation	p. 399
Uniform Boolean circuits	p. 400
The class NC	p. 402
P-completeness	p. 404
Cryptography	p. 405
Secret keys	p. 405
Public-key cryptosystems	p. 407
One-way functions	p. 407
Trapdoor functions	p. 409
Exercises, Problems, and Solutions	p. 411
Selected Bibliography	p. 415
Table of Contents provided by Ingram. All Rights Reserved.