Customer Reviews

Introduction to the Theory of Computation

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

 

 

When I picked up this book I thought, "You have to be kidding me." This book is very thin, and then a fair chunk of it is mathematics review for some of the formal arguments the book is going to be making later on. One wouldn't think there was much in this book.

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.

Summary of this review: You'll find yourself getting interested in, and understanding, concepts, very easily, but if you're an advanced reader you'll often find (at the end of the chapters) that the more advanced topics/problems have been glossed over.

If this is your assigned course textbook, you're lucky. If this is NOT your assigned textbook, USE it as your guide. It makes topics simpler and more intuitive. The way Sipser ropes down exotic theorems into straightforward, understandable logic is almost magical. The book scores in most areas: smoothness of flow, ease of understanding, order of presentation, motivational cues, and thoroughness in the areas covered.

The problem with the book is in the number of topics covered, and in the number of examples. There are not sufficient examples in some cases, and not sufficient material in some cases. This is a small textbook. At the end of each chapter, Sipser often glosses over the more advanced issues. If doing a thorough study, one will frequently need a more complete reference.

This will, of course, not be a problem if your course does not go beyond what is covered here: Finite Automata, Turing Machines, the relationship between the classes of languages, reducibility, and complexity theory.

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!

Reading this book changed my entire set of beliefs regarding the importance and usefulness of computational theory (and math) in computer science. I have been programming since grade 7, yet only after reading this book do I feel like I really have a grasp of it on a fundamental level. Its like there was this whole other world under my nose that I caught passing glimpses of yet was never able to put together. Like in DOS: c:>dir *, why use a star character? Why is XML the way it is? The list goes on and on. This book tied *alot* of 'loose ends' for me.

I always felt that being a cs-tist was about programming, object oriented design/analysis, design patterns, UML, etc.. And there is no doubt that mastery of these technologies are required of any good cs-tist. However, if you want to understand where all these technologies you use come from, how they connect, and to get a glimpse of where its all going, you must combine your current programming and trend following expertise with knowledge of the underlying theories of computation.

This book should be required reading for all first year CS students so that they may get the 'big picture' right from the start and be able to see CS as a whole rather than a bunch of 'kinda related' courses. I see this book inspiring a whole generation of cs-tists - many of whom may have gone into other professions after reading books like 'Introduction to Automata Theory, Languages, and Computation' by Ullman, Hopcroft (a great, rigorous treatment of cs, but *not* a good book to learn from or be inspired by).

Again, great book!

Michael Sipser has an undoubted gift for writing on this subject. The book is a coincise and easy read. But be cautious, this doesn't mean superficial and poor. The book contains all the material needed for a good course on Theory of Computation and Complexity. Perhaps it has not plenty of details like other books as Hopcroft & Ullman or Kozen or Papadimitrou, but don't underestimate the vastity of the treated topics, what is important is that every time you finish a chapter, you have the sensation that you've learned what you should have to. And probably you did due to Sipser's writing style, provided that you can afford to skip "some" more detailed/advanced topics. Or you might just be looking for some further stuff like Myhill-Nerode or Rabin-Shepherdson theorems or Chomsky Hierarchy for example, and you would have to look elsewhere for them. However, I've never been told that the best book is the most complete one. As long as I've learned, the best book is the one that best fits your needs, and that fitting these needs it suceeds to transmit the knowledge you're looking for in an effective way. That's why if this stuff is not required by your course, you would be perfectly fine with this book in your hands.

Proofs on theorems are given virtually always in two steps: first you're presented with the idea that lies behind the proof, and then you get the proof itself in a more rigorous fashion. Again, Sipser strikes here because it's harder NOT to understand one of his proofs than the contrary simply because the presentation is always clear and understandable.
As a matter of fact, Sipser (as he point out in the preface) almost always avoid to overload proofs given by construction with more rigorous following proofs (e.g. induction on the constructed machine to prove its equivalence with ...). This has a strong impact on the attention you can keep when studying throghout a chapter: avoiding to dive into tedious details when the proof (by construction) has been clear enough help to keep you attention high and boredom away. This is a way of learning, an effective way.

Sipser uses sometime a notation that's different from the somewhat standard one (e.g. the description of delta or transition function on various machines), but it is coherent throughout the whole book, and that's what does count, together with the note that this notation is noway more complex or hard to understand than the "standard" one.

Should I name two books on Theory of Computation (not Complexity), one just a little less rigorous and one just a little more rigorous than this, I would suggest Coehn's "Introduction to computer Theory" and Kozen's "Automata and Computability" respectively.

My conclusion is that this is a great book, worth the price (especially if confronted with others ...) and a stable place in my bookshelf.

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.

This book is aimed as an introductory text book on computer science theory. The book is suited for both undergraduate and graduate studies. The first three chapters of the book, regular expressions, context free languages and the church-turing thesis are apt for an introductory class for the undergraduate level. The remaining 7 chapters provide more than enough content for advanced undergraduate or graduate studies.

This is the first book on computer science theory that I have seen, which is actually written in understandable English. As compared to the previous introductory texts by Hopcroft or Papadimitriou, Sipser shuns writting the entire book using just symbols of formal mathematics. This is not to say that there is no formalism in the book. There is adequate use of formal mathematics in the proofs of the book, but not so much as to scare even in most intrepid readers like in previous books on this subject.The fact I liked most about this book is that every proof in the book is accompanied by a "Proof Idea" which explains using diagrams and plain english how exactly the proof works. This followed by the formal proof. The problems at the end of each chapter are fairly interesting, and some of the * marked problems can be fairly challenging for a first time student.

Another amazing thing about this book is the amount of content it covers. I would have never expected a book of only 400 pages to cover computer science theory all the way from introductory undergraduate to advanced graduate levels. This is because, the author focusses only on core concepts and strives to make them as clear as possible. For example, this book has only one chapter on regular expressions, while every other book that I have seen has at least 3-4 chapters full of gory details. This is because Sipser does not go into the gory mechanical details of converting DFAs to NFAs, or writing Turing machines and so on, but instead explains just the important concepts and gives a few examples. Also a wealth of information is to be found in the problems at the end of the chapter. Many of these problems like the Myhill-Nerode theorem are of the kind you will find actually proved in other texts, but left as an excercise here. This is because they are relatively simple to prove once all the concepts are understood. Moreover an educator has the option of which of these problems they want to delve deeper into.

Any student who studies or wishes to study computer science theory should definately get their hands on this book, irrespective of whether they have already used a different book.

I had this book in a computer theory course and I looked up similar books in the library looking for extra help and different perspectives. They were all horrible in comparison! No book can make this topic as easy as something hands-on like programming, but this one does the best I can imagine. The proofs are preceded by a "proof idea" that outlines what's going on before you get into the rigorous details. The writing is fluid and discusses the implications of the theorems and why they're important. This gives the reader an appreciation of the topic, which is a rare thing in something this arcane. Even if your course doesn't use this book, I recommend buying it as a supplement. I expect it to become a classic in the field.

I used this book as a supplement in a college class. It was VERY helpful in understanding computability theory, Turing Machines, and finite languages. Everything is put forth in a straightforward easy to understand manner.

The main thing that made this book stand out above the rest is that it's written in language that is easily understood, while other text books burden you down with a multitude of symbols and equations. The proof ideas are very helpfull in understanding concepts

Thank you Mr. Sipser!

i haven't seen a book on computation theory as clear and easy as this one, it is full of illustrative examples, and PROOF IDEAS..The material is exposed so clearly, that you can read a great amount of material without stopping.. Thanks Michael Sipser for this great book..