Cover image for Introduction to the theory of computation
Title:
Introduction to the theory of computation
Author:
Sipser, Michael.
Personal Author:
Publication Information:
Boston : PWS Pub. Co., [1997]

©1997
Physical Description:
xv, 396 pages : illustrations ; 25 cm
Language:
English
ISBN:
9780534947286
Format :
Book

Available:*

Library
Call Number
Material Type
Home Location
Status
Item Holds
Searching...
QA267 .S56 1997 Adult Non-Fiction Non-Fiction Area
Searching...

On Order

Summary

Summary

Michael Sipser's philosophy in writing this book is simple: make the subject interesting and relevant, and the students will learn. His emphasis on unifying computer science theory - rather than offering a collection of low-level details - sets the book apart, as do his intuitive explanations. Throughout the book, Sipser - a noted authority on the theory of computation - builds students' knowledge of conceptual tools used in computer science, the aesthetic sense they need to create elegant systems, and the ability to think through problems on their own. INTRODUCTION TO THE THEORY OF COMPUTATION provides a mathematical treatment of computation theory grounded in theorems and proofs. Proofs are presented with a "proof idea" component to reveal the concepts underpinning the formalism. Algorithms are presented using prose instead of pseudocode to focus attention on the algorithms themselves, rather than on specific computational models. Topic coverage, terminology, and order of presentation are traditional for an upper-level course in computer science theory. Users of the Preliminary Edition (now out of print) will be interested to note several new chapters on complexity theory: Chapter 8 on space complexity; Chapter 9 on provable intractability, and Chapter 10 on advanced topics, including approximation algorithms, alternation, interactive proof systems, cryptography, and parallel computing.


Author Notes

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 Editionp. xi
To the studentp. xi
To the educatorp. xii
The first editionp. xiii
Feedback to the authorp. xiii
Acknowledgmentsp. xiv
Preface to the Second Editionp. xvii
0 Introductionp. 1
0.1 Automata, Computability, and Complexityp. 1
Complexity theoryp. 2
Computability theoryp. 2
Automata theoryp. 3
0.2 Mathematical Notions and Terminologyp. 3
Setsp. 3
Sequences and tuplesp. 6
Functions and relationsp. 7
Graphsp. 10
Strings and languagesp. 13
Boolean logicp. 14
Summary of mathematical termsp. 16
0.3 Definitions, Theorems, and Proofsp. 17
Finding proofsp. 17
0.4 Types of Proofp. 21
Proof by constructionp. 21
Proof by contradictionp. 21
Proof by inductionp. 22
Exercises, Problems, and Solutionsp. 25
Part 1 Automata and Languagesp. 29
1 Regular Languagesp. 31
1.1 Finite Automatap. 31
Formal definition of a finite automatonp. 35
Examples of finite automatap. 37
Formal definition of computationp. 40
Designing finite automatap. 41
The regular operationsp. 44
1.2 Nondeterminismp. 47
Formal definition of a nondeterministic finite automatonp. 53
Equivalence of NFAs and DFAsp. 54
Closure under the regular operationsp. 58
1.3 Regular Expressionsp. 63
Formal definition of a regular expressionp. 64
Equivalence with finite automatap. 66
1.4 Nonregular Languagesp. 77
The pumping lemma for regular languagesp. 77
Exercises, Problems, and Solutionsp. 82
2 Context-Free Languagesp. 99
2.1 Context-free Grammarsp. 100
Formal definition of a context-free grammarp. 102
Examples of context-free grammarsp. 103
Designing context-free grammarsp. 104
Ambiguityp. 105
Chomsky normal formp. 106
2.2 Pushdown Automatap. 109
Formal definition of a pushdown automatonp. 111
Examples of pushdown automatap. 112
Equivalence with context-free grammarsp. 115
2.3 Non-context-free Languagesp. 123
The pumping lemma for context-free languagesp. 123
Exercises, Problems, and Solutionsp. 128
Part 2 Computability Theoryp. 135
3 The Church-Turing Thesisp. 137
3.1 Turing Machinesp. 137
Formal definition of a Turing machinep. 139
Examples of Turing machinesp. 142
3.2 Variants of Turing Machinesp. 148
Multitape Turing machinesp. 148
Nondeterministic Turing machinesp. 150
Enumeratorsp. 152
Equivalence with other modelsp. 153
3.3 The Definition of Algorithmp. 154
Hilbert's problemsp. 154
Terminology for describing Turing machinesp. 156
Exercises, Problems, and Solutionsp. 159
4 Decidabilityp. 165
4.1 Decidable Languagesp. 166
Decidable problems concerning regular languagesp. 166
Decidable problems concerning context-free languagesp. 170
4.2 The Halting Problemp. 173
The diagonalization methodp. 174
The halting problem is undecidablep. 179
A Turing-unrecognizable languagep. 181
Exercises, Problems, and Solutionsp. 182
5 Reducibilityp. 187
5.1 Undecidable Problems from Language Theoryp. 188
Reductions via computation historiesp. 192
5.2 A Simple Undecidable Problemp. 199
5.3 Mapping Reducibilityp. 206
Computable functionsp. 206
Formal definition of mapping reducibilityp. 207
Exercises, Problems, and Solutionsp. 211
6 Advanced Topics in Computability Theoryp. 217
6.1 The Recursion Theoremp. 217
Self-referencep. 218
Terminology for the recursion theoremp. 221
Applicationsp. 222
6.2 Decidability of logical theoriesp. 224
A decidable theoryp. 227
An undecidable theoryp. 229
6.3 Turing Reducibilityp. 232
6.4 A Definition of Informationp. 233
Minimal length descriptionsp. 234
Optimality of the definitionp. 238
Incompressible strings and randomnessp. 239
Exercises, Problems, and Solutionsp. 242
Part 3 Complexity Theoryp. 245
7 Time Complexityp. 247
7.1 Measuring Complexityp. 247
Big-O and small-o notationp. 248
Analyzing algorithmsp. 251
Complexity relationships among modelsp. 254
7.2 The Class Pp. 256
Polynomial timep. 256
Examples of problems in Pp. 258
7.3 The Class NPp. 264
Examples of problems in NPp. 267
The P versus NP questionp. 269
7.4 NP-completenessp. 271
Polynomial time reducibilityp. 272
Definition of NP-completenessp. 276
The Cook-Levin Theoremp. 276
7.5 Additional NP-complete Problemsp. 283
The vertex cover problemp. 284
The Hamiltonian path problemp. 286
The subset sum problemp. 291
Exercises, Problems, and Solutionsp. 294
8 Space Complexityp. 303
8.1 Savitch's Theoremp. 305
8.2 The Class PSPACEp. 308
8.3 PSPACE-completenessp. 309
The TQBF problemp. 310
Winning strategies for gamesp. 313
Generalized geographyp. 315
8.4 The Classes L and NLp. 320
8.5 NL-completenessp. 323
Searching in graphsp. 325
8.6 NL equals coNLp. 326
Exercises, Problems, and Solutionsp. 328
9 Intractabilityp. 335
9.1 Hierarchy Theoremsp. 336
Exponential space completenessp. 343
9.2 Relativizationp. 348
Limits of the diagonalization methodp. 349
9.3 Circuit Complexityp. 351
Exercises, Problems, and Solutionsp. 360
10 Advanced topics in complexity theoryp. 365
10.1 Approximation Algorithmsp. 365
10.2 Probabilistic Algorithmsp. 368
The class BPPp. 368
Primalityp. 371
Read-once branching programsp. 376
10.3 Alternationp. 380
Alternating time and spacep. 381
The Polynomial time hierarchyp. 386
10.4 Interactive Proof Systemsp. 387
Graph nonisomorphismp. 387
Definition of the modelp. 388
IP = PSPACEp. 390
10.5 Parallel Computationp. 399
Uniform Boolean circuitsp. 400
The class NCp. 402
P-completenessp. 404
10.6 Cryptographyp. 405
Secret keysp. 405
Public-key cryptosystemsp. 407
One-way functionsp. 407
Trapdoor functionsp. 409
Exercises, Problems, and Solutionsp. 411
Selected Bibliographyp. 415