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.23  ·  Rating details ·  1,844 ratings  ·  78 reviews

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

Hardcover, Second Edition, 431 pages
Published February 1st 2005 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

Community Reviews

Showing 1-30
Average rating 4.23  · 
Rating details
 ·  1,844 ratings  ·  78 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
Keith Walfson
Oct 15, 2019 rated it it was amazing
This had lots of good, practical advice.
Tikhon Jelvis
Aug 01, 2015 rated it it was amazing
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 delive
Mundy Reimer
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 engi
Nick Black
Mar 23, 2008 rated it really liked it  ·  review of another edition
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. ...more
Jeremy Frens
May 25, 2014 rated it it was amazing
Shelves: computation, textbook
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 to Automata
Aug 31, 2014 rated it liked it
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. ...more
Sep 22, 2020 rated it it was amazing
I am desperate, so I review my text book.
Tianyao Chen
May 23, 2020 rated it it was amazing
Shelves: tech-books
THE best textbook regarding the theory of computation. Full of lucid explanations. Recommended for anyone studying CS theories.
Ayush Bhat
Mar 15, 2018 rated it it was amazing
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.
Brian Powell
Feb 27, 2021 rated it really liked it  ·  review of another edition
Shelves: computer-science
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 halt ...more
Jan 04, 2014 rated it really liked it
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 re
Aug 03, 2020 rated it it was amazing
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 tryi
Feb 13, 2016 rated it it was amazing  ·  review of another edition
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  ·  review of another edition
Great intro to CS Theory and is a recommended book for all my theoretical graduate classes.
Callan Delbridge
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.
Antonis Maronikolakis
May 19, 2019 rated it it was amazing
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.

Abdurrezzak Efe
Aug 26, 2018 rated it it was amazing
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
Robert L
Oct 29, 2019 rated it did not like it
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
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.
Nov 08, 2020 rated it it was amazing
The clarity of the proofs is unmatched by any other introductory book I have encountered on the subject. The definitions are also no more complicated than they need to be, and the book is wonderfully self-contained, with proofs for almost everything stated. Took me awhile to get through mainly because it covers a lot of topics to varying degrees of detail, but well worth it.
Sten Sootla
Nov 18, 2018 rated it it was amazing
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.
Scott Holstad
Oct 09, 2020 rated it it was amazing
Shelves: technology
Crucial book and outstanding at that too. Anyone wishing to delve into this field should be obligated to read this, regardless of its original publication date. If not, it'd kind of be like reading about information theory while ignoring Claude Shannon. Recommended! ...more
Adam Peterson
May 04, 2021 rated it really liked it
I really enjoyed this textbook. I found the writing very clear and informative, often entertaining. I would put it up there with SICP and AIMA in terms of utility and reward, both for the understanding the reader will gain.
Ahmed Abd El-Hamid
Nov 08, 2017 rated it it was amazing
An excellent introduction to Theoretical Computer Science and it has been a great pleasure to read it
Егор Лебедев
Nov 10, 2017 rated it really liked it
Great book for grads and theoreticians.
Jan 14, 2018 rated it it was amazing
Insightful. A must read.
Jun 29, 2018 rated it it was amazing
The most readable introductory textbook out there.
Feb 23, 2019 rated it really liked it
Shelves: science
« previous 1 3 next »
There are no discussion topics on this book yet. Be the first to start one »

Readers also enjoyed

  • Introduction to Algorithms
  • The C Programming Language
  • Artificial Intelligence: A Modern Approach
  • Discrete Mathematics and Its Applications
  • Pattern Recognition and Machine Learning
  • Computer Organization & Design: The Hardware/Software Interface
  • Compilers: Principles, Techniques, and Tools
  • Algorithm Design
  • The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine
  • The Mythical Man-Month: Essays on Software Engineering
  • Modern Operating Systems
  • Operating System Concepts
  • Code: The Hidden Language of Computer Hardware and Software
  • Computer Networking: A Top-Down Approach
  • Practical Common LISP
  • Deep Learning
  • Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)
  • The Algorithm Design Manual
See similar books…

Goodreads is hiring!

If you like books and love to build cool products, we may be looking for you.
Learn more »

News & Interviews

Believe it or not, we're halfway through 2021! As is our tradition, this is the time when the Goodreads editorial team burrows into our data to...
98 likes · 79 comments
“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.” 3 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.” 2 likes
More quotes…