Goodreads helps you keep track of books you want to read.
Start by marking “Introduction to the Theory of Computation” as Want to Read:
Introduction to the Theory of Computation
Enlarge cover
Rate this book
Clear rating
Open Preview

Introduction to the Theory of Computation

4.22  ·  Rating details ·  1,683 ratings  ·  59 reviews
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 - b ...more
Hardcover, 396 pages
Published December 13th 1996 by Course Technology (first published January 25th 1996)
More Details... Edit Details

Friend Reviews

To see what your friends thought of this book, please sign up.

Reader Q&A

To ask other readers questions about Introduction to the Theory of Computation, please sign up.

Be the first to ask a question about Introduction to the Theory of Computation

This book is not yet featured on Listopia. Add this book to your favorite list »

Community Reviews

Showing 1-30
Average rating 4.22  · 
Rating details
 ·  1,683 ratings  ·  59 reviews

More filters
Sort order
Start your review of Introduction to the Theory of Computation
Josh Davis
Anyone wishes to learn about automata, context-free languages, and Turing machines needs to pick up this book. I'm not even kidding. Sipser is such a clear writer and can describe concept things very lucidly. My favorite thing about this book compared to other mathematical books is that Sipser explicitly gives the "Proof Idea" before delving into a proof. Most people that use proofs are probably familiar with the sensation of finishing reading a proof only to wonder what in the world just happen ...more
Tikhon Jelvis
Aug 01, 2015 rated it it was amazing  ·  review of another edition
Shelves: favorites
The best textbook I've read on any subject—by some margin. I'd get carried away reading it, despite the fact that theoretical CS (especially complexity) has never been my thing. It's incredibly accessible, to a surprising degree for a book covering advanced abstract topics.

Sipser writes clearly and explains concepts well but, crucially, he does an incredible job building up your intuition. You don't just learn the material, you understand it. That's something few authors try and fewer yet deli
Keith Walfson
Oct 15, 2019 rated it it was amazing  ·  review of another edition
This had lots of good, practical advice.
Jeremy Frens
May 25, 2014 rated it it was amazing  ·  review of another edition
Shelves: textbook, computation
For some reason it feels strange to me to write a review for a textbook here at Goodreads, especially for a textbook I read and used years ago. But I love this book.

While I was a college professor (in Computer Science), I received a review copy of this book. I used it several times for miscellaneous reasons, and then one semester I actually got to teach from it. Sipser's writing is very clear and instructional. (It's nowhere near as dry as the once-traditional textbook, Introduction
Nick Black
Mar 23, 2008 rated it really liked it
Runs out of depth really early, but I learned my basics of automata theory from this lovely little hardback and will always love it for that. Remains the clearest exposition of the fundamental formalisms of which I'm aware. There's plenty of books with much more meat, and you'll inevitably need them -- browse my library for examples.
Aug 31, 2014 rated it liked it  ·  review of another edition
I like how the book is divided into three sections: Automata and Languages, Computability Theory and Complexity Theory. The book provides a good introduction to computability and complexity maintaining the balance between the two topics. I also like the proof idea sections, which provide valuable insights into proofs before actually proving it formally. Advanced topics in computability and complexity made an interesting read. Obviously one cannot get to the depth of all the theorems on first rea ...more
Arvydas Sidorenko
The name of the book is confusing - "Introduction to the..." is in fact written as if you already understand the material. Topics are very condensed, where rather than giving space to explain things it tends to say "it is obvious that ...", when often it isn't that obvious.
Ayush Bhat
Mar 15, 2018 rated it it was amazing  ·  review of another edition
One of the most interactive book I have ever read. This book explains concept in a very good manner. However this book lacks automata type examples , but theory is sufficient to solve any question from other book.
Jan 04, 2014 rated it really liked it  ·  review of another edition
I recently took a Finite Automata course in which we actually only covered about half of the material presented in the book. It was very well-written and for the most part pretty easy to follow. I'm not the greatest at following precise mathematical definitions, so when I had a tough time making sense of what the book was telling me I still had to go to my professor for clarification, but I think that says more about the difficult of the subject than a fault on any part of the book.

Feb 13, 2016 rated it it was amazing
I wish I could go back in time and give my past self this book, I encourage anyone interested in pursuing a degree in Computer Science to read chapter 0, it will show you the kinds of things that will be expected of you and prepare you for the math you'll need to learn. The later chapters are excellent for Automata Theory for those interested, and earlier editions like this are fairly cheap. The language makes the concepts easy to understand, and although the later chapters get a little wordy, i ...more
Ro Givens
Aug 26, 2010 rated it it was amazing
Great intro to CS Theory and is a recommended book for all my theoretical graduate classes.
Antonis Maronikolakis
What really stands out for the book is that it is very well written. Great wording and language from Sipser make for a very easy read. All the concepts are put forth in as a friendly manner as possible, allowing one to focus on the concepts themselves and not get tripped over big words and cumbersome notation a lot of writers go for.

Most proofs are preceded by a section walking the reader through the idea behind the proof in an intuitive way. That makes the proofs so much easier to under
Robert L
Oct 29, 2019 rated it did not like it  ·  review of another edition
While I can't say that I have read another book on the same subject and thus can't rate the book comparatively, I can say beware to anyone picking up this book that likes to see practicality and don't have a big interest in this form of mathematical theory. For those in Computer Science, the only explanation about why you should be concerned is a one page of the preface at the beginning. And at least for the first two parts of the book, it includes very few examples and questions that seem to ha ...more
Abdurrezzak Efe
Aug 26, 2018 rated it it was amazing  ·  review of another edition
There is a common belief that textbooks cannot be read for fun because they just "tell you" things. "No storyline is followed in them."
This book beats that belief to death :) Dr. Sipser first gives us a list of approaches that will be used to prove things. It is particularly important because Theory of Computation is a very central, fundamental and sometimes non-intuitive subject. One should be able to internalize the things she learns before getting into the next subject. The book helps the re
Oct 01, 2017 rated it really liked it  ·  review of another edition
Detailed, yet very concise in some sections. A well-written (course) book that delivers valuable examples and clear introductions. Peculiar cases can be hard to work out, and it's particularly challenging in sections where this book is the de facto book on the subject matter, where extra resources are not available.

Clearly separate sections make for easy selection of your interest areas.
Sten Sootla
Nov 18, 2018 rated it it was amazing  ·  review of another edition
I found it so engrossing that I read the book as if it were science fiction. A fascinating look into how one can develop theoretical models of computation, and prove interesting properties of these models. A must-read for every computer scientist/engineer who aspires to be a cultural professional.
Jun 29, 2018 rated it it was amazing  ·  review of another edition
The most readable introductory textbook out there.
Jan 14, 2018 rated it it was amazing  ·  review of another edition
Insightful. A must read.
Taymur Bajwa
Oct 29, 2019 is currently reading it  ·  review of another edition
Shelves: book
good book
Feb 23, 2019 rated it really liked it  ·  review of another edition
Егор Лебедев
Great book for grads and theoreticians.
Ahmed Abd El-Hamid
An excellent introduction to Theoretical Computer Science and it has been a great pleasure to read it
Joe Cole
Mar 06, 2017 rated it it was amazing  ·  review of another edition
I bought this for class and it is important to understand that this text is meant to supplement lectures on the theory of computation.
an excellent introduction for someone new to the field and subject!
Jan 29, 2011 rated it really liked it  ·  review of another edition
Shelves: technical
I've read Introduction to Automata Theory by Hopcroft, et al, and parts of Elements of the Theory of Computation, and Sipser's book is definitely the most clear. I have no doubt that it is one of the clearer books on the subject in general, but its difficult to follow the more advanced proofs and some of the chapter problems without a very solid foundation in mathematics. I find it difficult to follow mathematical symbology, and hence some of the proofs are beyond me. I think its a matter of pra ...more
Dec 10, 2012 rated it it was amazing  ·  review of another edition
Shelves: cs
A fantastic introduction into the theory of computation. With no perquisite knowledge apart from mathematical maturity the book starts by exploring simple finite state automaton and ends with the discussion of the complex proof that IP = PSPACE. The presentation is very clear and the ideas are broken down succinctly but with very clear proofs with accompanying diagrams Often people complain about a book being too brief ("This proof is left to the reader...") or being too detailed without explana ...more
Jose Vieitez
Dec 25, 2015 rated it really liked it  ·  review of another edition
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 higher and the level of apparent relevance/ feeling of being worthwhile of theories went down, so it started becoming a bit of a drag. It wasn't the author's fault though, I just don't care much for how to prove something and care more for why it works, and it was pretty much all proofs toward the end ...more
May 22, 2012 rated it it was amazing  ·  review of another edition
I am reading this book for my curiosity. Author style is chaste. Therefore If you decide to read this book, you will encounter an understandable world of computation. Book consists of three parts. It explains complexity, computability and automata theory. If you do a computer program, you encounter regular expression concept. Book points out theory behind regular expression. Thus, You have a widespread view of programming language, regular languages and compiler etc. To sum up, I offer this book ...more
Kai Weber
Aug 09, 2014 rated it really liked it  ·  review of another edition
Shelves: it, mathematics
This is the best prose that I have read so far about the topic of Computation and Automata theory. Purists might see it as a disadvantage that must concepts are explicitly put down in plain words and might miss the one or other formula. But for the reader who has no university degree in mathematics, the prose descriptions must be very welcome. Furthermore, the topic is elaborated in a didactically useful sequence and the relations of automata, formal grammars, decidability and complexity become ...more
Chris Herdt
Jan 09, 2012 rated it really liked it  ·  review of another edition
This was a surprisingly well-organized and well-written textbook. I consulted some additional texts on the subject during the course I was taking, but this book was superior to any of them.

I would have preferred some additional basic, or possibly intermediate, exercises. The problem sets offered at the end of each chapter got very complex very quickly.
Vincent Russo
Apr 01, 2012 rated it it was amazing  ·  review of another edition
One of the texts used for a computational complexity class I had quite a while ago. It's a bit less dense than some other texts on the subject, but still manages to get into many of the core bits of computational complexity theory. Ideal text for an undergraduate course on the subject.
« previous 1 next »
There are no discussion topics on this book yet. Be the first to start one »

Readers also enjoyed

  • Introduction to Automata Theory, Languages, and Computation
  • Computers and Intractability: A Guide to the Theory of NP-Completeness
  • Computational Complexity
  • Elements of the Theory of Computation
  • The Art of Computer Programming, Volumes 1-3 Boxed Set
  • Artificial Intelligence: A Modern Approach
  • Computer Systems: A Programmer's Perspective
  • The UNIX Programming Environment
  • Types and Programming Languages
  • Computational Complexity
  • Concrete Mathematics: A Foundation for Computer Science
  • Modern Operating Systems
  • Programming Language Pragmatics
  • Compilers: Principles, Techniques, and Tools
  • Advanced Programming in the UNIX Environment
  • Concepts, Techniques, and Models of Computer Programming
  • Introduction to Algorithms
  • Algorithm Design
See similar books…

Goodreads is hiring!

If you like books and love to build cool products, we may be looking for you.
Learn more »
“Theory is relevant to you because it shows you a new, simpler, and more elegant side of computers, which we normally consider to be complicated machines. The best computer designs and applications are conceived with elegance in mind. A theoretical course can heighten your aesthetic sense and help you build more beautiful systems.” 2 likes
“... theory is good for you because studying it expands your mind... 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.” 1 likes
More quotes…