Introduction to the Theory of Computation

Front Cover
PWS Publishing Company, 1996 - Computational complexity - 239 pages
42 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
4 stars
3 stars
2 stars
1 star

Review: Introduction to the Theory of Computation

User Review  - Jose Vieitez - Goodreads

Really does a great job at bringing high level theories down to the basics, especially in the first half of the book. Eventually, though, the level of complication of proofs (maybe just for me) got ... Read full review

Review: Introduction to the Theory of Computation

User Review  - Umang Kumar - Goodreads

this is the best book Read full review


Automata and Languages
ContextFree Languages
Computability Theory

5 other sections not shown

Other editions - View all

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