What do you think?
Rate this book
Introduction to the Theory of Computation
This highly anticipated revision builds upon the strengths of the previous edition. Sipser's candid, crystal-clear style allows students at every level to understand and enjoy this field. His innovative "proof idea" sections explain profound concepts in plain English. The new edition incorporates many improvements students and professors have suggested over the years, and offers updated, classroom-tested problem sets at the end of each chapter.
431 pages, Hardcover
First published January 25, 1996
260 people are currently reading
5,455 people want to read
Ratings & Reviews
Friends & Following
Create a free account to discover what your friends think of this book!
Community Reviews
Displaying 1 - 30 of 99 reviews
June 19, 2021
Motivation
If you've never heard of why someone would study the "Theory of Computation" and how this differs from something perhaps more tangible like programming or software engineering, you might come to the conclusion that this is "all just theory"...*waves around hand in the air in a useless circular manner*, but I'd beg you to not jump to this thought too soon! It's not that the latter is practical, while the former is just theory, but rather that what we call "programming" or "software engineering" is usually very specific to a certain set of technologies of a specific era or even a specific hardware implementation, whereas the former "theory" contains concepts that can be applied agnostic of the hardware you are dealing with, agnostic to the time period you are living in, agnostic of the specific programming language you are using, and even in my case, agnostic to the field at which you are even applying this knowledge to!
Computing is a very general concept that can be applied to multiple fields and domains of expertise and is much more a "way of thinking" and collection of unique logical tools and methods for solving problems in whatever domain, either software, linguistics, mathematics, electrical engineering, philosophy, botany, physics, and in my case, the foundations of biology! It is kind of unfortunate given the name, but "computing" is not about computers per se, but rather about the nature of problem solving, talking about certain limits to how efficiently a problem can be solved, and even figuring out if our problem even has a way of solving it to begin with (which you'll come to learn is very different from merely checking whether an answer is correct)! The nature of time, memory, space, efficiency, and representation are all topics that are explored in this area.
Background
Having just recently finished a Formal Grammars & Automata Theory course at the local university where we used this as our textbook, I have to say that this book was probably the main reason for why I was able to keep up and not fall behind in the course. It doesn't read like a dry definition-lemma-proof book you might have encountered in some fields of math, but rather a hybrid of that with lots of helpful injected commentary going over the thought processes of how to solve these problems and how to work your way through these proofs in plain old regular english, with lots of useful diagrams when needed. One thing I especially appreciated was the author giving a theorem or making a claim, then following that up with a helpful discussion on the "proof idea" behind that claim, and then next with the proof written in a combination of english + symbols, and finally if needed, a very formal "algorithmic" way with the steps clearly enumerated line-by-line and in concise fashion.
An example of that can be seen here:
This is a really good pedagogical technique that I wish more authors would follow, as students are given a choice as to "what level" of explanation and rigor best appeals to them. Here's another example, this time with an accompanying picture:
For the self-study people out there thinking about prerequisites, it would probably be wise to have some practice and former experience with "proofs", but regardless, the author does a great job reviewing common mathematical notation and basic proof techniques at the beginning of the book, which would usually correspond to your common undergraduate first course in discrete mathematics. Such things as relations, functions, graphs, strings, languages, boolean logic, proof by construction / contradiction / induction, etc are reviewed at the beginning and accompanied with ample practice problems (with solutions!) such that you can strengthen your foundation if needed before moving onto the meat of the book. As a disclaimer, although I'm just a data scientist with a former background in neuroscience, I have invested a non-trivial amount of both non-formal + official time in coursework such as logic, set theory, and generally "pure math" areas, and I was also concurrently going through another official and very complementary logic course in Undecidability & Incompleteness, so take my review with that in mind.
Other Helpful Material
When studying some subject I always recommend trying to learn from multiple sources because you can't always guarantee that you'll never "get stuck" on some concept or section of a book. I've found that sometimes having multiple perspectives and different people explaining things to me can help. As such, I supplemented my reading with another textbook called What Can Be Computed? (my review here) which gives a more *hands-on*, practical approach to the theory of computing with lots of exercises in Python.
Two other books I was reading in parallel that I recommend are The Annotated Turing and Gödel's Theorem: An Incomplete Guide to Its Use and Abuse, the former of which I highly recommend for its excellent historical treatment of Alan Turing's original 36-page paper establishing what is now known as the Turing Machine, and the latter book whose mathematical & philosophical topic arguably spurred the development of the former (for a short & neat explanation of this for the layman, ). I usually like accompanying my studies with historical background like this to not only help motivate me, but also to give me a bigger "forest-over-trees" picture and context as to why these ideas were even formed to begin with, how this fits into the grander historical narrative, and why I should even care. It's also somewhat fun for my socially-inclined primate brain to know the people and controversies behind such ideas, which provides a useful scaffold and cognitive framework to remember this material much better and for longer (if you especially enjoy this, see the book Exact Thinking in Demented Times: The Vienna Circle and the Epic Quest for the Foundations of Science).
In addition to the aforementioned books, I would also recommend going through which covers the Theory of Computing and solves a lot of practice problems with you (the latter of which is key to becoming fluent with this material!) Hopefully all that linked material proves helpful on your learning journey :)
Content
This book is broken up into 3 main parts: Automata & Languages, Computability Theory, and Complexity Theory. Again, each section contains lots of worked out examples with solutions, accompanied with helpful commentary.
The first part was my favorite and the main reason for why I was taking this course. In it the author covers the theory of regular languages, going over finite automata, non-determinism, regular expressions, and non-regular languages, while introducing you to a new and useful proof technique called the Pumping Lemma, which allows you to disprove the regularity of a language. For those coming from a linguistics background, you might find the intersection of this material and the incredibly fascinating. The author then follows this up with material about context-free languages, discussing context-free grammars, pushdown automata, non-context free languages, and deterministic context-free languages. This material is highly relevant to those who are interested in the more practical problems of parsing natural languages, or maybe designing your own programming language, or even how a compiler works, etc. Somewhat of an aside, but I really wished this book at least introduced or covered a little bit of context-sensitive grammars, since that was my primary interest and motivation for even taking this course to begin with (due to its relationship with cellular automata, lindenmayer systems, artificial life, and theoretical biology, all of which ).
In the second part of this book, the content shifts focus towards arguably more historical and philosophical content going under the header of 'Computability Theory'. Here we are introduced to the famous Church-Turing Thesis, Turing machines and a few of their variants (for an interesting article on "time-traveling Turing machines" and closed-timelike curves in computation, by quantum computing theorist, Scott Aaronson). This section also covers the famous Halting/Decidability problem, as well as important proof techniques like diagonalization and reducibility. Some advanced topics are also covered with a small introduction to information theory and minimal length description, the compressibility of strings, randomness, etc. Although we didn't officially cover it in my course, I found this latter section quite interesting! (and especially relevant to biology!)
This last section of the book switches gears to what arguably makes up the bulk of most theoretical computer science research today. It deals with something called 'Complexity Theory'. Whereas the former second section of the book dealt with the question of whether some problems were even possible to solve to begin with, this latter third section of the book deals with how efficient can a problem be solved given a certain amount of time, space, memory, etc, ranking problems according to certain complexity classes. In here we first are introduced to how we measure complexity using Big-O notation, the famous P vs NP problem, NP-completeness, the Cook-Levin Theorem, SAT problems, and additional NP-complete problems like independent set, vertex cover, hamiltonian path, subset-sum, etc (which are all helpful in proof techniques like reduction used to prove NP-completeness, etc). And although we never were able to cover this far in my official course, the book does continue to go over space complexity like Savitch's theorem, NL-completeness, Intractability (hierarchy problems, relativization, and circuit complexity), as well as more advanced topics like approximation algorithms, probabilistic algorithms interactive proof systems, parallel computation, and cryptography, all of which I assume the author included in case this book is used in the graduate-level Masters or PhD setting for specific topical courses and such.
Conclusion
Overall, this book introduced highly fascinating material at the intersection of multiple disciplines of computer science, logic, math, philosophy, electrical engineering, linguistics, etc. The amount of accompanying explanatory discussion along with the ample amount of worked-out examples makes this book highly recommended in my opinion (and suitable for self-study, especially if you follow along with one of the free lecture materials I linked to above).
My only comment for improvement is to include some introductory material in the first section on *context-sensitive grammars! I would've loved to have an official and well-backed source that I could reference and learn this from. And also, although it might seem a tad too advanced, I do think maybe a brief introduction to what is known as which observes the fundamental relationships between computation / programming languages, formal logic / type theory, and category theory / topology to be a highly relevant and significant perspective which would allow the student coming from another field to see all the fascinating connections linking everything together, or alternatively help a student to branch out to other fields to which the theory of computation can be applied. This "rosetta stone" is a marvelous way to bring this book and field to higher prominence and relevance today.
Thank you for reading :)
*EDIT: From the comments on another book review with Ritu, I was motivated to take a look at the textbook Automata, Computability and Complexity: Theory and Applications by Elaine Rich and just found out that by way of the Myhill–Landweber–Kuroda theorem! So technically to be fair, I guess the above textbook by Sipser indirectly covered CSGs whether the author intended to or not.
If you've never heard of why someone would study the "Theory of Computation" and how this differs from something perhaps more tangible like programming or software engineering, you might come to the conclusion that this is "all just theory"...*waves around hand in the air in a useless circular manner*, but I'd beg you to not jump to this thought too soon! It's not that the latter is practical, while the former is just theory, but rather that what we call "programming" or "software engineering" is usually very specific to a certain set of technologies of a specific era or even a specific hardware implementation, whereas the former "theory" contains concepts that can be applied agnostic of the hardware you are dealing with, agnostic to the time period you are living in, agnostic of the specific programming language you are using, and even in my case, agnostic to the field at which you are even applying this knowledge to!
Computing is a very general concept that can be applied to multiple fields and domains of expertise and is much more a "way of thinking" and collection of unique logical tools and methods for solving problems in whatever domain, either software, linguistics, mathematics, electrical engineering, philosophy, botany, physics, and in my case, the foundations of biology! It is kind of unfortunate given the name, but "computing" is not about computers per se, but rather about the nature of problem solving, talking about certain limits to how efficiently a problem can be solved, and even figuring out if our problem even has a way of solving it to begin with (which you'll come to learn is very different from merely checking whether an answer is correct)! The nature of time, memory, space, efficiency, and representation are all topics that are explored in this area.
Background
Having just recently finished a Formal Grammars & Automata Theory course at the local university where we used this as our textbook, I have to say that this book was probably the main reason for why I was able to keep up and not fall behind in the course. It doesn't read like a dry definition-lemma-proof book you might have encountered in some fields of math, but rather a hybrid of that with lots of helpful injected commentary going over the thought processes of how to solve these problems and how to work your way through these proofs in plain old regular english, with lots of useful diagrams when needed. One thing I especially appreciated was the author giving a theorem or making a claim, then following that up with a helpful discussion on the "proof idea" behind that claim, and then next with the proof written in a combination of english + symbols, and finally if needed, a very formal "algorithmic" way with the steps clearly enumerated line-by-line and in concise fashion.
An example of that can be seen here:
This is a really good pedagogical technique that I wish more authors would follow, as students are given a choice as to "what level" of explanation and rigor best appeals to them. Here's another example, this time with an accompanying picture:
For the self-study people out there thinking about prerequisites, it would probably be wise to have some practice and former experience with "proofs", but regardless, the author does a great job reviewing common mathematical notation and basic proof techniques at the beginning of the book, which would usually correspond to your common undergraduate first course in discrete mathematics. Such things as relations, functions, graphs, strings, languages, boolean logic, proof by construction / contradiction / induction, etc are reviewed at the beginning and accompanied with ample practice problems (with solutions!) such that you can strengthen your foundation if needed before moving onto the meat of the book. As a disclaimer, although I'm just a data scientist with a former background in neuroscience, I have invested a non-trivial amount of both non-formal + official time in coursework such as logic, set theory, and generally "pure math" areas, and I was also concurrently going through another official and very complementary logic course in Undecidability & Incompleteness, so take my review with that in mind.
Other Helpful Material
When studying some subject I always recommend trying to learn from multiple sources because you can't always guarantee that you'll never "get stuck" on some concept or section of a book. I've found that sometimes having multiple perspectives and different people explaining things to me can help. As such, I supplemented my reading with another textbook called What Can Be Computed? (my review here) which gives a more *hands-on*, practical approach to the theory of computing with lots of exercises in Python.
Two other books I was reading in parallel that I recommend are The Annotated Turing and Gödel's Theorem: An Incomplete Guide to Its Use and Abuse, the former of which I highly recommend for its excellent historical treatment of Alan Turing's original 36-page paper establishing what is now known as the Turing Machine, and the latter book whose mathematical & philosophical topic arguably spurred the development of the former (for a short & neat explanation of this for the layman, ). I usually like accompanying my studies with historical background like this to not only help motivate me, but also to give me a bigger "forest-over-trees" picture and context as to why these ideas were even formed to begin with, how this fits into the grander historical narrative, and why I should even care. It's also somewhat fun for my socially-inclined primate brain to know the people and controversies behind such ideas, which provides a useful scaffold and cognitive framework to remember this material much better and for longer (if you especially enjoy this, see the book Exact Thinking in Demented Times: The Vienna Circle and the Epic Quest for the Foundations of Science).
In addition to the aforementioned books, I would also recommend going through which covers the Theory of Computing and solves a lot of practice problems with you (the latter of which is key to becoming fluent with this material!) Hopefully all that linked material proves helpful on your learning journey :)
Content
This book is broken up into 3 main parts: Automata & Languages, Computability Theory, and Complexity Theory. Again, each section contains lots of worked out examples with solutions, accompanied with helpful commentary.
The first part was my favorite and the main reason for why I was taking this course. In it the author covers the theory of regular languages, going over finite automata, non-determinism, regular expressions, and non-regular languages, while introducing you to a new and useful proof technique called the Pumping Lemma, which allows you to disprove the regularity of a language. For those coming from a linguistics background, you might find the intersection of this material and the incredibly fascinating. The author then follows this up with material about context-free languages, discussing context-free grammars, pushdown automata, non-context free languages, and deterministic context-free languages. This material is highly relevant to those who are interested in the more practical problems of parsing natural languages, or maybe designing your own programming language, or even how a compiler works, etc. Somewhat of an aside, but I really wished this book at least introduced or covered a little bit of context-sensitive grammars, since that was my primary interest and motivation for even taking this course to begin with (due to its relationship with cellular automata, lindenmayer systems, artificial life, and theoretical biology, all of which ).
In the second part of this book, the content shifts focus towards arguably more historical and philosophical content going under the header of 'Computability Theory'. Here we are introduced to the famous Church-Turing Thesis, Turing machines and a few of their variants (for an interesting article on "time-traveling Turing machines" and closed-timelike curves in computation, by quantum computing theorist, Scott Aaronson). This section also covers the famous Halting/Decidability problem, as well as important proof techniques like diagonalization and reducibility. Some advanced topics are also covered with a small introduction to information theory and minimal length description, the compressibility of strings, randomness, etc. Although we didn't officially cover it in my course, I found this latter section quite interesting! (and especially relevant to biology!)
This last section of the book switches gears to what arguably makes up the bulk of most theoretical computer science research today. It deals with something called 'Complexity Theory'. Whereas the former second section of the book dealt with the question of whether some problems were even possible to solve to begin with, this latter third section of the book deals with how efficient can a problem be solved given a certain amount of time, space, memory, etc, ranking problems according to certain complexity classes. In here we first are introduced to how we measure complexity using Big-O notation, the famous P vs NP problem, NP-completeness, the Cook-Levin Theorem, SAT problems, and additional NP-complete problems like independent set, vertex cover, hamiltonian path, subset-sum, etc (which are all helpful in proof techniques like reduction used to prove NP-completeness, etc). And although we never were able to cover this far in my official course, the book does continue to go over space complexity like Savitch's theorem, NL-completeness, Intractability (hierarchy problems, relativization, and circuit complexity), as well as more advanced topics like approximation algorithms, probabilistic algorithms interactive proof systems, parallel computation, and cryptography, all of which I assume the author included in case this book is used in the graduate-level Masters or PhD setting for specific topical courses and such.
Conclusion
Overall, this book introduced highly fascinating material at the intersection of multiple disciplines of computer science, logic, math, philosophy, electrical engineering, linguistics, etc. The amount of accompanying explanatory discussion along with the ample amount of worked-out examples makes this book highly recommended in my opinion (and suitable for self-study, especially if you follow along with one of the free lecture materials I linked to above).
My only comment for improvement is to include some introductory material in the first section on *context-sensitive grammars! I would've loved to have an official and well-backed source that I could reference and learn this from. And also, although it might seem a tad too advanced, I do think maybe a brief introduction to what is known as which observes the fundamental relationships between computation / programming languages, formal logic / type theory, and category theory / topology to be a highly relevant and significant perspective which would allow the student coming from another field to see all the fascinating connections linking everything together, or alternatively help a student to branch out to other fields to which the theory of computation can be applied. This "rosetta stone" is a marvelous way to bring this book and field to higher prominence and relevance today.
Thank you for reading :)
*EDIT: From the comments on another book review with Ritu, I was motivated to take a look at the textbook Automata, Computability and Complexity: Theory and Applications by Elaine Rich and just found out that by way of the Myhill–Landweber–Kuroda theorem! So technically to be fair, I guess the above textbook by Sipser indirectly covered CSGs whether the author intended to or not.
March 21, 2024
Anyone who wishes to learn about automata, context-free languages and Turing machines needs to pick up this book. 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 happened. This hardly happens in this book.
August 2, 2015
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 deliver.
The most visible component of this is the book's structure with "proof sketches"—little proof roadmaps—laid out before diving into the fiddly details of the full proof. All too often, proofs jump around in surprising ways—sure, approach X works, but where did it come from? What insight is it based on? Proof sketches, coupled with quality prose, help you understand where proofs come from and why they make sense, not just how they work.
He also introduces some interesting context to the ideas and formalisms presented. His observation on the "robustness" of Turing-completeness—how virtually any reasonable model of computation, however weird and exotic, seems to have the same level of power—still influences my views on math and CS. Robust properties, emerging almost on their own, make mathematical ideas seem far less arbitrary than they would otherwise. Perhaps it's given me a bad case of platonism.
So: accessible, well-written, enjoyable. Rare qualities for a textbook, making it the perfect place to start with theoretical CS. One caveat comes to mind: it is not very thorough. You get a strong introduction to the field, but nothing more. This gets you going, introduces basic vocabulary and demonstrates the theoretical CS mindset but is not enough to progress further on the subject. A perfect fit if you're reading for enlightenment or curiosity, but needs supplemental resources to go beyond that.
But that's not a real shortcoming, it's just a matter of focus. So, keeping that in mind, I can recommend this book unreservedly for anyone interested in theoretical CS.
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 deliver.
The most visible component of this is the book's structure with "proof sketches"—little proof roadmaps—laid out before diving into the fiddly details of the full proof. All too often, proofs jump around in surprising ways—sure, approach X works, but where did it come from? What insight is it based on? Proof sketches, coupled with quality prose, help you understand where proofs come from and why they make sense, not just how they work.
He also introduces some interesting context to the ideas and formalisms presented. His observation on the "robustness" of Turing-completeness—how virtually any reasonable model of computation, however weird and exotic, seems to have the same level of power—still influences my views on math and CS. Robust properties, emerging almost on their own, make mathematical ideas seem far less arbitrary than they would otherwise. Perhaps it's given me a bad case of platonism.
So: accessible, well-written, enjoyable. Rare qualities for a textbook, making it the perfect place to start with theoretical CS. One caveat comes to mind: it is not very thorough. You get a strong introduction to the field, but nothing more. This gets you going, introduces basic vocabulary and demonstrates the theoretical CS mindset but is not enough to progress further on the subject. A perfect fit if you're reading for enlightenment or curiosity, but needs supplemental resources to go beyond that.
But that's not a real shortcoming, it's just a matter of focus. So, keeping that in mind, I can recommend this book unreservedly for anyone interested in theoretical CS.
October 16, 2019
This had lots of good, practical advice.
March 23, 2008
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.
September 23, 2020
I am desperate, so I review my text book.
May 25, 2014
For some reason it feels strange to me to write a review for a textbook here at Å·±¦ÓéÀÖ, 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, . Has this been unseated since I changed careers?) His selection of exercises and exercises exceeds my disgustingly high standards.
You can't do better than this book for a college course in computation. I'm not sure how well it would work to read on your own, but it'll still be better than any of the others.
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, . Has this been unseated since I changed careers?) His selection of exercises and exercises exceeds my disgustingly high standards.
You can't do better than this book for a college course in computation. I'm not sure how well it would work to read on your own, but it'll still be better than any of the others.
February 14, 2016
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, it's better to say too much about those advanced concepts than too little.
September 17, 2011
Great intro to CS Theory and is a recommended book for all my theoretical graduate classes.
March 23, 2025
Among the best-written intro level math textbooks...ever? Not a book on computability theory really (recursion gets an extremely brisk treatment, Rice's theorem is relegated to the exercises), but rather a broad overview of all the mathematical models of computation, ranging from simple automata all the way up to interactive proof systems. The running theme connecting all of them is "simulation" -- whether you are simulating a probabilistic automaton on a deterministic automaton, a multi-tape Turing machine on a single-tape, or an arbitrary computation on a vast logical circuit. Helps to have a little programming and proof experience but I don't think either is strictly necessary going in.
Sipser's innovation I guess was to include a "proof idea" segment before the majority of the proofs, and it's a good idea, although their utility varies. Sometimes the best way to understand a proof is really just to look at the pseudocode, whether you're a mathematician or a CS kid. Occasionally the "idea" section dwarfs the actual proof. I think that what really makes the book so useful is that he is not interested in overly strict mathematical rigor nor in including full implementation-level programs for the most part, so he's able to give high-level discussions of fairly big results in an approachable way.
If a non-math person wanted to learn some interesting 20th c math I would maybe recommend this book. Only nit is excluding Myhill-Nerode from the main discussion, just putting it in the exercises. He spends so much time on automata that it seems like the discussion of residue classes would be helpful.
Sipser's innovation I guess was to include a "proof idea" segment before the majority of the proofs, and it's a good idea, although their utility varies. Sometimes the best way to understand a proof is really just to look at the pseudocode, whether you're a mathematician or a CS kid. Occasionally the "idea" section dwarfs the actual proof. I think that what really makes the book so useful is that he is not interested in overly strict mathematical rigor nor in including full implementation-level programs for the most part, so he's able to give high-level discussions of fairly big results in an approachable way.
If a non-math person wanted to learn some interesting 20th c math I would maybe recommend this book. Only nit is excluding Myhill-Nerode from the main discussion, just putting it in the exercises. He spends so much time on automata that it seems like the discussion of residue classes would be helpful.
December 13, 2024
pray i pass👀
September 5, 2024
explains everything very well. this book is the only reason i passed my class
July 10, 2016
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 read as Theory of Computation is quite a dense subject. As the author mentions some of the theorems which are otherwise covered as main text in other books are covered as a part of problems, also some times the text refers to problems from the previous chapters because of which some gaps were left since I didn't plan to go through the problems on my first read.So, the best thing to do is to workout the problems after finishing each chapter.
I think this is a great text on the subject of theory of computation and one who like the subject should definitely read it twice :)
I think this is a great text on the subject of theory of computation and one who like the subject should definitely read it twice :)
March 9, 2016
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.
May 24, 2020
THE best textbook regarding the theory of computation. Full of lucid explanations. Recommended for anyone studying CS theories.
March 15, 2018
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.
August 29, 2024
Still the clearest and most well-written math/c.s. book I've ever read.
March 2, 2021
This seems to be a solid introduction to computability theory. Mind you, I am not a computer scientist, never studied computer science in school, nor do I do research in a related field. So what use are my impressions? Not much, probably. I am a physicist-turned-data scientist and am simply curious about this stuff. I didn't work through every proof, and didn't touch the end-of-section problems. If, like me, your life doesn't depend on proving that SAT3 is NP-complete, or explaining why the halting problem is undecidable while hanging upside down over an alligator tank in the cellar of some sadistic though technically-inclined serial killer, you might consider my review relevant.
Given a moderate level of effort, you will come away from this book with an essential understanding of decidability, formal models of computation, and computational complexity. The book is not the most pedagogical...it is quite formal, terse, and dry in places. The author is not in a bad mood but he is not smiling very much either. He is not excitedly welcoming you to this mysterious new land of computability theory; he's more like a jaded veteran lab technician showing you around the spectrum analyzer, gruffly telling you to clean up after yourself and to definitely *not* touch the red button. Sipser assumes you're pretty smart, and that you don't have follow-up questions. Maybe that's true of MIT students. I'm certainly not one of them.
As an example: the idea of reduction. We can 'reduce' a problem A to a problem B and use facts about the one to understand the other. If B is decidable then so is A; conversely, if A is undecidable then so is B. Now, why this asymmetric logic? Presumably it's because B is considered the harder problem (which strains the terminology 'reduce'), and if B can be decided, then the easier problem A too can be decided. But this isn't spelled out anywhere. This seems like an obvious question anyone seeing this material for the first time might ask. It could be dispelled in a line or two, but Sipser doesn't address it. There are lots of examples like this, where you're like "hey, hold on a quick second...could we just think a bit more about...no? Moving on? OK..."
In terms of structure, there are plenty of examples, but more often the structure is: introduce topic, theorem, proof of theorem, introduce topic, lemma, proof of lemma, .... lots more of this ...., then maybe an example or two. This is why I say it is not particularly pedagogical: it's not really *teaching* as much as communicating ideas. It's certainly not engaging, the way I think introductory texts should be.
Apparently Sipser is popular with people who, unlike me, take this subject seriously. For off-label use, it's pretty solid but has defects, some of which I've listed above. I suspect there might be better treatments for amateurs and idiots.
Given a moderate level of effort, you will come away from this book with an essential understanding of decidability, formal models of computation, and computational complexity. The book is not the most pedagogical...it is quite formal, terse, and dry in places. The author is not in a bad mood but he is not smiling very much either. He is not excitedly welcoming you to this mysterious new land of computability theory; he's more like a jaded veteran lab technician showing you around the spectrum analyzer, gruffly telling you to clean up after yourself and to definitely *not* touch the red button. Sipser assumes you're pretty smart, and that you don't have follow-up questions. Maybe that's true of MIT students. I'm certainly not one of them.
As an example: the idea of reduction. We can 'reduce' a problem A to a problem B and use facts about the one to understand the other. If B is decidable then so is A; conversely, if A is undecidable then so is B. Now, why this asymmetric logic? Presumably it's because B is considered the harder problem (which strains the terminology 'reduce'), and if B can be decided, then the easier problem A too can be decided. But this isn't spelled out anywhere. This seems like an obvious question anyone seeing this material for the first time might ask. It could be dispelled in a line or two, but Sipser doesn't address it. There are lots of examples like this, where you're like "hey, hold on a quick second...could we just think a bit more about...no? Moving on? OK..."
In terms of structure, there are plenty of examples, but more often the structure is: introduce topic, theorem, proof of theorem, introduce topic, lemma, proof of lemma, .... lots more of this ...., then maybe an example or two. This is why I say it is not particularly pedagogical: it's not really *teaching* as much as communicating ideas. It's certainly not engaging, the way I think introductory texts should be.
Apparently Sipser is popular with people who, unlike me, take this subject seriously. For off-label use, it's pretty solid but has defects, some of which I've listed above. I suspect there might be better treatments for amateurs and idiots.
January 4, 2014
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.
I chose to rent the book, rather than buy it, however after completing my course I chose to buy myself a copy so I can try to complete the rest of the material via self-study, which I'm still working on.
Overall, I'd definitely recommend this book to anybody interested in the Theory of Computation.
I chose to rent the book, rather than buy it, however after completing my course I chose to buy myself a copy so I can try to complete the rest of the material via self-study, which I'm still working on.
Overall, I'd definitely recommend this book to anybody interested in the Theory of Computation.
August 4, 2020
As an introduction it seems fine. Relatively clear explanations and proofs. Skips the hardest parts of every topic, so this is kind of on the extreme end of being a survey of a broad field. There are many exercises that range in type and difficulty.
I had deliberated about giving it four or five stars since it's not my favorite book on the topic. I would personally like something more comprehensive and thorough. But that's probably not a fair standard to hold this book to. It's deliberately trying to be more targeted for a wide audience that is probably less interested in being thorough and detailed.
I had deliberated about giving it four or five stars since it's not my favorite book on the topic. I would personally like something more comprehensive and thorough. But that's probably not a fair standard to hold this book to. It's deliberately trying to be more targeted for a wide audience that is probably less interested in being thorough and detailed.
December 23, 2024
Sipser is an excellent writer. Read it for my college theory of computation course, absolutely great book for anyone wanting learn about the first computers, finite automata, Turing machines, etc. I love how Sipser breaks down tough concepts, theoretical ones too, extremely difficult task but he does a great job!
December 8, 2020
Part one was a joy to read and easy to understand with just reading the book. With part 2 and part 3 book alone wasn't enough for me to understand the topics.
November 5, 2020
I surprisingly really enjoyed this - the proofs and theorems are usually explained really well, and often there are many examples given to most angles of the proof.
The section I enjoyed the most that did this was probably the proof for the Pumping Lemma for regular languages; there are a few rules to it as well as 3 conditions that must be met, but Sipser chooses a handful of different non-regular languages (for proofs by contradiction) which uniquely explain why each rule or condition is there.
I jumped around a lot and so have not read the book cover to cover, so I cannot speak for absolutely every topic (including some of the advanced ones), but some sections seem rather cryptic compared to others that seem well formulated and, at least if you have a computer science degree, quite easy to read - perhaps if there's another edition or two (it's quite old but it seems Sipser still periodically updates it!) they are smoothed over and the book is made even better.
Great book for the introduction of finite automata, pushdown automata, Turing machines, decidability proofs, time complexities (big O), languages from regular to recursively enumerable, pumping lemmas, grammars and more!
Also, there's a Leonardo da Vinci flying machine on the cover of this edition which, although I don't really see any relevance, I'm a complete sucker for!
The section I enjoyed the most that did this was probably the proof for the Pumping Lemma for regular languages; there are a few rules to it as well as 3 conditions that must be met, but Sipser chooses a handful of different non-regular languages (for proofs by contradiction) which uniquely explain why each rule or condition is there.
I jumped around a lot and so have not read the book cover to cover, so I cannot speak for absolutely every topic (including some of the advanced ones), but some sections seem rather cryptic compared to others that seem well formulated and, at least if you have a computer science degree, quite easy to read - perhaps if there's another edition or two (it's quite old but it seems Sipser still periodically updates it!) they are smoothed over and the book is made even better.
Great book for the introduction of finite automata, pushdown automata, Turing machines, decidability proofs, time complexities (big O), languages from regular to recursively enumerable, pumping lemmas, grammars and more!
Also, there's a Leonardo da Vinci flying machine on the cover of this edition which, although I don't really see any relevance, I'm a complete sucker for!
May 19, 2019
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 understand.
Another great plus is the solved exercises at the end of each chapter. The writer offers some selected solutions for some of the exercises that help the reader in dealing with the rest of the exercises.
All in all, this is a book I cannot recommend enough. Michael Sipser has done a fantastic job with this book and this is essential for any computer scientist’s library.
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 understand.
Another great plus is the solved exercises at the end of each chapter. The writer offers some selected solutions for some of the exercises that help the reader in dealing with the rest of the exercises.
All in all, this is a book I cannot recommend enough. Michael Sipser has done a fantastic job with this book and this is essential for any computer scientist’s library.
August 26, 2018
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 reader do that easily.
As the subjects in the book are interesting such as Regular Languages, Automata Theory, Turing MAchines and Decidability <3 the reader never gets bored. It is like reading a fiction book where the characters are Machines :)
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 reader do that easily.
As the subjects in the book are interesting such as Regular Languages, Automata Theory, Turing MAchines and Decidability <3 the reader never gets bored. It is like reading a fiction book where the characters are Machines :)
October 29, 2019
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 have any relation to how it could be used in the real world. You almost exclusively are asked to do either proofs or problems that could be done easier and more interestingly with circuits much less even low level programming languages.
December 15, 2024
I taught myself automata, computability, and complexity using this book early on in college. One of the pivotal decisions of mine as an undergrad as it’s what made me fall in love with the subject. Best introduction to this material there is. I’ve been a TA for an intro to TOC class for a couple years now and I take every opportunity to recommend this to my students. Sipser provides an intuitive yet fully rigorous understanding of the main topics in formal languages and computation. Shows the reader that computation is a universal phenomenon which exists independently from the digital computer; which is the central message of the theory of computation.
July 3, 2021
Most other texts make this subject painfully dry. Sipser's book makes the subject fascinating. So many "oh my god, is that really true?" moments. Everything is covered with enough detail to get the gist, and yet he somehow manages to do this with rigor too. Many concepts are broken into 3 parts: a "setting the scene" explanation, a "proof idea" and then a proof.
I'd suggest reading this book after reading something on math analysis, as this text spends a lot of its time talking about infinities.
Pretty much anything Sipser publishes next I'll read.
I'd suggest reading this book after reading something on math analysis, as this text spends a lot of its time talking about infinities.
Pretty much anything Sipser publishes next I'll read.
April 27, 2023
That's a very theoretical book.
I took my chances in reading it, and I cannot complain with its content.
As a newbie I was prepared to not understand everything, but to be honest I didn't expect this endless sequence of theorems, well explained though.
The first part on finite and nondeterminism automata is very difficult to follow, but the turning point on Turing Machine and the definition of algorithm makes it more intelligible.
At last, the chapters regarding Time and Space complexity are very interesting.
I took my chances in reading it, and I cannot complain with its content.
As a newbie I was prepared to not understand everything, but to be honest I didn't expect this endless sequence of theorems, well explained though.
The first part on finite and nondeterminism automata is very difficult to follow, but the turning point on Turing Machine and the definition of algorithm makes it more intelligible.
At last, the chapters regarding Time and Space complexity are very interesting.
October 1, 2017
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.
Clearly separate sections make for easy selection of your interest areas.
Displaying 1 - 30 of 99 reviews
Can't find what you're looking for?
Get help and learn more about the design.