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.19  ·  Rating Details ·  1,268 Ratings  ·  41 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

...more
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)
filter  |  sort: default (?)  |  Rating Details
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
Tikhon Jelvis
Aug 01, 2015 Tikhon Jelvis rated it it was amazing
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
...more
Jeremy Frens
May 25, 2014 Jeremy Frens rated it it was amazing
Shelves: textbook, computation
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
...more
Omesh
Aug 31, 2014 Omesh 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
Lily
Feb 13, 2016 Lily 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
Nick Black
Mar 23, 2008 Nick Black 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.
Ro Givens
Aug 26, 2010 Ro Givens 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.
Joe Cole
Mar 06, 2017 Joe Cole rated it it was amazing
I bought this for class and it is important to understand that this text is meant to supplement lectures on the theory of computation.
an excellent introduction for someone new to the field and subject!
Jamie
Jan 29, 2011 Jamie rated it really liked it
I've read Introduction to Automata Theory by Hopcroft, et al, and parts of Elements of the Theory of Computation, and Sipser's book is definitely the most clear. I have no doubt that it is one of the clearer books on the subject in general, but its difficult to follow the more advanced proofs and some of the chapter problems without a very solid foundation in mathematics. I find it difficult to follow mathematical symbology, and hence some of the proofs are beyond me. I think its a matter of pra ...more
Shawn
Jan 04, 2014 Shawn 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
...more
Matthew
Dec 10, 2012 Matthew rated it it was amazing
Shelves: cs
A fantastic introduction into the theory of computation. With no perquisite knowledge apart from mathematical maturity the book starts by exploring simple finite state automaton and ends with the discussion of the complex proof that IP = PSPACE. The presentation is very clear and the ideas are broken down succinctly but with very clear proofs with accompanying diagrams Often people complain about a book being too brief ("This proof is left to the reader...") or being too detailed without explana ...more
Kai
Aug 09, 2014 Kai rated it really liked it
Shelves: mathematics, it
This is the best prose that I have read so far about the topic of Computation and Automata theory. Purists might see it as a disadvantage that must concepts are explicitly put down in plain words and might miss the one or other formula. But for the reader who has no university degree in mathematics, the prose descriptions must be very welcome. Furthermore, the topic is elaborated in a didactically useful sequence and the relations of automata, formal grammars, decidability and complexity become ...more
Jose Vieitez
Dec 25, 2015 Jose Vieitez rated it really liked it
Really does a great job at bringing high level theories down to the basics, especially in the first half of the book. Eventually, though, the level of complication of proofs (maybe just for me) got higher and the level of apparent relevance/ feeling of being worthwhile of theories went down, so it started becoming a bit of a drag. It wasn't the author's fault though, I just don't care much for how to prove something and care more for why it works, and it was pretty much all proofs toward the end ...more
Tolga
May 22, 2012 Tolga rated it it was amazing
I am reading this book for my curiosity. Author style is chaste. Therefore If you decide to read this book, you will encounter an understandable world of computation. Book consists of three parts. It explains complexity, computability and automata theory. If you do a computer program, you encounter regular expression concept. Book points out theory behind regular expression. Thus, You have a widespread view of programming language, regular languages and compiler etc. To sum up, I offer this book ...more
Chris Herdt
Jan 09, 2012 Chris Herdt rated it really liked it
This was a surprisingly well-organized and well-written textbook. I consulted some additional texts on the subject during the course I was taking, but this book was superior to any of them.

I would have preferred some additional basic, or possibly intermediate, exercises. The problem sets offered at the end of each chapter got very complex very quickly.
javier
Mar 25, 2007 javier rated it it was amazing
Shelves: math-books
what i learned from this book: everything about the theory of computation. this book is crystal clear. mike sipser is a master of making the most complex ideas lucid to all. some very cool ideas are covered too.
Emily
Jun 21, 2008 Emily rated it really liked it
I had an incomprehensible professor, and this great little book got me through the class with flying colors. Clear, and a great resource. How often do you find yourself keeping a computer science textbook because you liked it?
Vincent Russo
Apr 01, 2012 Vincent Russo rated it it was amazing
One of the texts used for a computational complexity class I had quite a while ago. It's a bit less dense than some other texts on the subject, but still manages to get into many of the core bits of computational complexity theory. Ideal text for an undergraduate course on the subject.
Rich
Mar 20, 2012 Rich rated it it was amazing
Easy to read introduction to Theoretical Computer Science. Perfect.
Tony Poerio
Jul 01, 2016 Tony Poerio rated it liked it
A difficult subject, lucidly explained. Exercises are essential for understanding, and this book has lots. More answers and walk throughs would be appreciated though.
Zach
Jun 26, 2014 Zach rated it did not like it
Alphabet soup.
Jagdeep Pani
Sep 21, 2013 Jagdeep Pani rated it it was amazing
The best book I have ever read..
Very good for beginners..
The more you read this book.. the more will be your thirstiness towards theory of computation..
Yunjiang Jiang
Dec 21, 2014 Yunjiang Jiang rated it it was amazing
The best math book I have ever read.
Chris
Nov 24, 2008 Chris marked it as to-read  ·  review of another edition
Never actually took a computational theory course in college - guess it's time to read now.
Marcus Reilly
Sep 11, 2014 Marcus Reilly rated it really liked it
Good book, even goes into detail on underlying math
Lewis Cawthorne
Oct 19, 2011 Lewis Cawthorne rated it it was amazing
Had to shelve this about a third in to focus on classes, but looking forward to finishing it.
Ahmed Afifi
Jun 19, 2012 Ahmed Afifi rated it it was amazing
Shelves: favorites
Would absolutely recommend this book to anyone who wants to learn computation theory
Umang Kumar
Aug 03, 2015 Umang Kumar rated it it was amazing
This review has been hidden because it contains spoilers. To view it, click here.
Steven Tomcavage
Jan 14, 2011 Steven Tomcavage rated it really liked it
I read this for a class in the Theory of Computation. The book was very clear and as easy to read as any other theoretical math textbook.
Juliusz Gonera
Jun 23, 2013 Juliusz Gonera rated it it was amazing
Very accessible intro to the theory of computation.
« previous 1 3 4 5 6 7 8 9 next »
There are no discussion topics on this book yet. Be the first to start one »
  • Introduction to Automata Theory, Languages, and Computation
  • Artificial Intelligence: A Modern Approach
  • Computers and Intractability: A Guide to the Theory of NP-Completeness
  • Computational Complexity
  • Types and Programming Languages
  • The Art of Computer Programming, Volumes 1-3 Boxed Set
  • Introduction to Algorithms
  • Modern Operating Systems
  • Concrete Mathematics: A Foundation for Computer Science
  • Computer Systems: A Programmer's Perspective
  • Concepts, Techniques, and Models of Computer Programming
  • Compilers: Principles, Techniques, and Tools
  • Algorithm Design
  • The UNIX Programming Environment
  • Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)
  • Advanced Programming in the UNIX Environment
  • Computational Complexity: A Modern Approach
  • Applied Cryptography: Protocols, Algorithms, and Source Code in C

Goodreads is hiring!

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

Share This Book