Customer Reviews

Introduction to the Theory of Computation

5 star:		(12)
4 star:		(4)
3 star:		(1)
2 star:		(3)
1 star:		(1)

 

 

I have a long experience with software development, but not much background in computation theory, just fascinating tidbits I have picked up here and there. So, this book for the first time deepens and organizes for me this hightly abstract and difficult topic.

Being a novice, I at first was afraid that the text of the book would be beyond my understanding. It was not. For sure, the proofs are difficult and may appeal to the person with a degree in computer science. But the copious diagrams, figures and tables are wonderful supplements to the understandable text. For the first time I really could grasp the subtleties of the finit automata, non-determinism, regular expressions, pushdown automata and other topics.

Certainly I can recommend this book to the beginner at computation theory, and even to the more advanced student who may want to review the topic.

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.

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.

As an intro to the theoretical background to computer science goes, this book is about as readable and approachable as you can get.

It gives a very thorough treatment of the whole theoretical basis, from regular languages and pumping lemmas out through Turing machines and related issues, and on to some interesting language classes (like NP and PSpace-complete).

If there's a single sticking point with the book, it's that it insists on a very strict formalism (ie: everything is proof-based) -- something necessary for the topic, but it sometimes renders the material a bit hard to digest.

If you are interested in or for other reasons must read a book on this subject, this is the book. I took a class last semester which used Hopcroft as the text and I found myself often turning to this book for better understanding. This book is more intuitive and thus a bit less formal than Hopcroft but when trying to learn, understanding is better than mathematical formalism. If you are new to the subject, Sipser is the book to begin with.

This book is a very easy read for anyone with some mathematical background. A lot of care is put into making everything as simple as possible. While this is a good thing overall, in some ways it is also a drawback. Oftentimes I felt that more detail could have been given. For example, given that encodings were used everywhere, you would think he would go over Gödel numbering. For the first two parts of the book, the simplicity really allows the book to flow very smoothly. This isn't so clear-cut for the third and final part though. I could be misguided as I've never read another text on the subject, but I feel like complexity theory really just can't be made as easy as he wants it to be. Sometimes the plain-English explanations aren't detailed enough to provide a good understanding of what's going on, and leave me confused.

What Sipser does do a good job of is explaining the genesis of his proofs. Often he will lead the reader down the wrong track just to give an example of where to look first when trying to prove something. To some this may seem like a waste of their time, but it really facilitates learning how to approach proofwriting. As a whole I would say it's a very good text.

One of the most remarkable things about this text is how well it would serve as an introduction to higher mathematics, without being written on algebra or analysis. With enough determination, one with no mathematical background could probably make it through the first nine chapters. It's that simple and self-contained. Neither calculus nor any remote knowledge of linear algebra is necessary to tackle it. This is not to say that it would be an easy task for such a person, making the transition to advanced math is going to be difficult wherever you start. The tenth chapter however breaks the self containment, assuming some very basic mathematical knowledge (finite fields, groups, matrices).

The author of this text, 2nd edition, has posted an errata list that is no less than 17 pages long! Lots of correcting to be done. Generally a well written, fairly easy to read book.

There is not too much to say about this spectacular textbook that has not been said already by many of the other reviewers. This is a wonderful presentation of key ideas in complexity, on that fulfills a big hole in the literature.

The presentation is notable for its clarity. In exposition, the author chooses one important idea and carefully but clearly develops that single idea. By contrast, certain other textbook authors (who shall remain nameless) tend to try and present so many variants of the same idea that the reader gets bogged down and loses sight of the key elements.

Michael Sipser, perhaps ironically, is known for some fiendishly complex proofs in complexity theory (e.g. Go is PSPACE hard). Despite that, the book is a model of clarity. Not surprisingly, the book really shines in its completeness presentation, where NP-completeness, PSPACE completeness, and the equivalence of IP and PSPACE are shown with great power and verve.

Perhaps my only reservation is that the book is a bit light on the recursive hierarchy, but there's enough for the curious student. Also, lets face it, nowadays the custom is probably to have more pictures and color - a teacher might want to supplement some of the proofs with demos, or the enterprising student unfamiliar with the area could do so himself.

Finally, the book has some superb special topics that make it a necessity and make most of the older theory of computation books entirely obsolete. There are great introductions to Interactive Proofs, Probabilistic Computing, Parallel Computing, and Information Theory. And nice nuances throughout, like the proof that P=NP is not relativization-independent.

All in all, this is one of those very rare books that are written by a top practitioner and theorist on the one hand, yet at the same time are clear and well-motivated for the reader.

Conclusion: presentation: terrific. Choice of topics: terrific. Writing style: terrific. Clarity: terrific. It's a great text.

Using this book for an intro to computation course. I can't stand the text. The first chapters on DFA's and NFA's through to PDA's are easy enough to understand; it's when you reach Turing machines that the book takes a dive. This text will provide "proofs" of examples. These are never strict proofs, they provide "intuition" but hardly an understanding. While this isn't an analysis text, the books proof for the uncountability of the real numbers is atrocious. The one example that is easier to prove and demonstrates diagnolization better would be proving that the set of binary numbers is uncountable. The text does this after the fact and only devotes a few sentences to it. Later it introduces the concept of reducibility, I am not familiar with how strict Turing and Church were when proving a language is decidable or not, but I am almost certain they put forward something more substantial than the "programs" that Sipser uses as proofs. If you're looking for intuition, then this book is fine. If you're looking to understand this material thoroughly I suggest something else.

This book has unbelievably clear explanations. Actually it is so good that it makes the lecturer superfluous. For years I felt I did not really understand the proof of the Cook Levin theorem. Sure, I had Garey and Johnson, and I more or less could follow the proof, but I wouldn't have been able to reproduce it on my own. With this book, it has become crystal clear, and now I would be able to explain it in front of any audience without any preparation. If you're taking a computation course and this is not your assigned textbook, go buy it now!