Introduction to the Theory of Computation

One would be wrong. This book goes into rather impressive depth on some rather abstract concepts of computer science without dabbling for too long in the details. It does the best job I've ever seen of explaining the Turing machine and how it relates to computability and decidablity.

The exercises are both easy and insanely difficult - so you can basically chose your level and then go through the book, some of the problems are very hard, some are trivially easy, a great mix makes for great homework assignments.

The "Proof Idea:" sections before every proof give you the underlying concepts in plain english that are about to be stated formally so you have a clue what's happening when the formal definitions start flying. These are priceless and should be included in every other book that uses formal proof techniques.

The book reads fairly well on its own, or makes for a great class text book, which I used it for. As my professor said, "This is a good book because it doesn't have any extra words." but you don't seem to mind as you read it. Probably the best work on the science of computation in the world, certainly the best I've ever seen.


An excellent one-semester intro to theory of computation   April 18, 2005
Todd Ebert (Long Beach California)
15 out of 16 found this review helpful

The theory of computation represents a fascinating landscape that intersects computer science and mathematics and can be roughly divided into three overlapping areas: automata and formal languages, computability theory, and computational complexity. And there is enough interesting knowledge about each area to fill three books, each twice the size of this one. And because of this I find it remarkable that the author has succeeded in filling a slim volume with the essential theory and results from each area, in a style that not only seems very accessible and intuitive, but also demonstrates important relationships between the three areas. For example, most books on computability theory do not discuss automata outside of Turing machines, but in his book Sipser elegantly proves that the equivalence problem is decidable for deterministic finite automata, but undecidable for pushdown automata.

Not only does the author have very good coverage of the three areas, but he also is able to strike a nice balance between mathematical rigor and intuitive understanding. His "proof idea" proof preambles greatly helped my students better understand the main ideas behind each result. In terms of coverage I found only a handful of introductory topics that were neglected: Greibach Normal Form, Rice and Rice-Shapiro Theorems, algebraic aspects of formal languages, Turing degrees, and perhaps context sensitive languages. With that said, remember that this book is just a semester-long introduction to a vast landscape. I recommend the following books for more depth: Peter Linz, "Introduction to Formal Languages and Automata"; Nigel Cutland, "Introduction to Computability Theory"; Christos Papadimitriou, "Computational Complexity".

Another strength of the book is how the author distinguishes exercises and problems: "exercises" are similar to the worked out examples, and can be solved by following one of the presented examples, algorithms or theorems, while "problems" require significant expository writing and deeper insight. Most undergraduates should be able to handle the exercises, but will find the problems very challenging if not impossible, due to the fact that students at this level are mostly familiar with problems that can be solved in a few steps by following some algorithm. So these problems have the capability of developing student intellect, but if assigned in too large a quantity can break the spirit of the developing student. Have care!

I congratulate Dr. Sipser on this fine book. May it inspire millions of readers to question the meaning of computation and explore its possibilities and limitations.


a lifesaver for all computer science majors!   December 30, 1999
43 out of 45 found this review helpful

I bought this book in a desperate attempt to pass a Theory of Computation course in which I was enrolled. I was stuck in the sad situation of having a non-English speaking, difficult to understand professor. In addition, the required text for the course was awful. Thanks to Sipser's book, I not only avoided dropping the course, but managed to get an A. (I'm not exagerating). Sipser's book is fantastic compared to others on the subject. It is written in easy to understand, plain, no-nonsense language. (Even the section on pumping lemma is understandable) I became aware of Sipser's book as a result of reading a customer's negative review of another (more expensive) book (Intro to Languages & theory of Computation by J. Martin) on the same subject. The reviewer suggested buying this book by Sipser instead, and that advice was excellent. (Many thanks to that reader, whoever you are!) If you are considering heading for the drop course line at the registrar's office, try this book before you give up and quit!


Most appropriate for CS students   June 1, 2006
Brett Bernstein (New York, USA)
15 out of 17 found this review helpful

As a teacher of the subject, I have had the chance to evaluate numerous books on the theory of computation. Of all the available texts, I think this one is the most appropriate for CS students. In the past I taught out of Dexter Kozen's book, which is incredibly elegant, but had some resistance from the students. Thinking it over I decided that Kozen's text, although beautiful, may be better suited to students pursuing a degree in pure math. Sipser's book, on the other hand, is more gentle. I find that Sipser demands far less mathematical maturity from his readers, and thus allows the difficulty to be shifted from excessive formalism to the inherent challenges present in the material. In addition, following Sipser's treatment, I was able to cover finite state machines and pushdown automata in far less time, thus allowing me to concentrate on computability and beyond. The book really shines in its treatment of computability theory, eloquently directing attention to some of the most beautiful aspects.

Another benefit of Sipser's book is the exercises, of which there are many more in this edition. Someone studying on their own should find the initial group of exercises in each section quite approachable. Even the more challenging problems are not incredibly hard, and typically draw their difficulty from the deeper themes of the chapter instead of obscure details.

If you are looking for an enjoyable, well-paced book with an introduction to computability and complexity that is truly inspiring, this is the one for you. A mathematician looking for a bit more rigor may do better with Kozen.


Very readable, diverse, and a little sparse   November 25, 2006
Christopher D. Smith (Colorado Springs, CO)
9 out of 9 found this review helpful

This is a wonderful little gem of a book that presents the theory of computation in a fascinating way. It is targeted at advanced undergraduates in computer science, but assumes remarkably little prior knowledge, making it accessible to nearly anyone. The book covers a lot of ground, including the standard fare of automata, computability, and complexity results, plus some bonus material such as probablistic and parallel complexity, information theory, decidable logical theories, and other topics that are normally left out of introductory books. On top of this, the book is remarkably thin!

The best attribute of Sipser's book, though, is the engaging style. This is an easy book to read. You will not feel like you're running into a brick wall, as is sometimes the case with books on abstract topics. It's not so much that the book is slow or gentle (it's really not) as that it is interesting, engaging, and has a knack for stopping short of getting too caught up in details. A number of small things -- the occasional amusing exercise, the "proof idea" sections, or helpful pictures -- add up to an enjoyable reading experience.

Two cautions are appropriate to students considering this book. First, there are variations between authors in the definitions of various automata (especially PDAs). The differences are trivial, and more a matter of taste than of any real importance; but it could come up if you use Sipser as a supplement to a course that follows a different textbook. Second, the coverage of many topics in Sipser's book is brief and concise, sometimes more than you might like. Some important concepts (for example, pairwise distinguishability of strings) are only mentioned in exercises, not in the main chapter, so at least skim all the exercises even if you don't do them. The sketchy coverage is especially pronounced in advanced topics, so (as always) expect to do some filling in of concepts if you go on into further study of this area.