Introduction to the Theory of Computation

Front Cover
PWS Publishing Company, 1996 - Computational complexity - 239 pages
21 Reviews
Discusses such topics as: regular languages; context-free languages; Church-Turing thesis; decidability; reducibility; the recursion theorem; time complexity; space complexity; and provable intractability.

From inside the book

What people are saying - Write a review

User ratings

5 stars
14
4 stars
7
3 stars
0
2 stars
0
1 star
0

Review: Introduction to the Theory of Computation

User Review  - Nirbhai Singh - Goodreads

One of the best writings on computability and complexity theory. And authors chaste way of putting things upfront, just adds to the already whooping brilliance of this text. Read full review

Review: Introduction to the Theory of Computation

User Review  - Lewis Cawthorne - Goodreads

Had to shelve this about a third in to focus on classes, but looking forward to finishing it. Read full review

Contents

Automata and Languages
29
ContextFree Languages
81
Computability Theory
111
Copyright

5 other sections not shown

Common terms and phrases

About the author (1996)

Michael Sipser has taught theoretical computer science and other mathematical subjects at the Massachusetts Institute of Technology for the past 25 years, where he is a professor of Applied Mathematics and a member of the Computer Science and Artificial Intelligence Laboratory (CSAIL). Currently, he is the head of the mathematics department. He enjoys teaching and pondering the many mysteries of complexity theory.

Bibliographic information