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.16 of 5 stars 4.16  ·  rating details  ·  831 ratings  ·  34 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

Structure and Interpretation of Computer Programs by Harold AbelsonIntroduction to Algorithms by Thomas H. CormenThe C Programming Language by Brian W. KernighanThe Pragmatic Programmer by Andrew HuntArt of Computer Programming, The, Volumes 1-3 Boxed Set by Donald Ervin Knuth
Essential Books of Computer Science
8th out of 143 books — 101 voters
The Pragmatic Programmer by Andrew HuntThe C Programming Language by Brian W. KernighanDesign Patterns by Erich GammaStructure and Interpretation of Computer Programs by Harold AbelsonCode Complete by Steve McConnell
Essential Programming Books
60th out of 112 books — 270 voters

More lists with this book...

Community Reviews

(showing 1-30 of 2,175)
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
Jeremy Frens
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
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
Ro Givens
Great intro to CS Theory and is a recommended book for all my theoretical graduate classes.
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
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
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
Dec 17, 2012 Matthew rated it 5 of 5 stars
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
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
Yunjiang Jiang
The best math book I have ever read.
Mar 27, 2011 Joecolelife rated it 5 of 5 stars
Recommended to Joecolelife by: Online Bookstore
I think that this book is by far the best introductory text on theory of computation and complexity that I have read so far. I would recommend the aho ulmann book as a companion after having gone through this book to strengthen your knowledge. But, this book introduces stuff like never before. Simply amazing.. buy it even if you are planning to take a course and the instructor is using some other textbook, its that good!!
Chris Herdt
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.
Nick Black
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.
Vincent Russo
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.
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?
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.
Marcus Reilly
Good book, even goes into detail on underlying math
Nirbhai Singh
One of the best writings on computability and complexity theory.
And authors chaste way of putting things upfront, just adds to the already whooping brilliance of this text.
Jagdeep Pani
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..
Steven Tomcavage
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.
dead letter office
if you must learn computational complexity, this is the easiest way to do it. introductory undergraduate text.
its very easy to understand..................
the book is very helpful for me..............
Jan 25, 2009 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.
Lewis Cawthorne
Had to shelve this about a third in to focus on classes, but looking forward to finishing it.
Sep 11, 2007 Shani rated it 5 of 5 stars
Recommends it for: computer scientists
Shelves: popular-science
This is the textbook that makes you love what you are studying. Beautifully and simply explained.
Ahmed Afifi
Would absolutely recommend this book to anyone who wants to learn computation theory
Alftheo Potgieter
Math alert! Although it seems like the computer science math notation needs a bit of work
Philip Shing
Favorite textbook.
Genuinely enjoyed reading this more than most puzzle books.
Easy to read introduction to Theoretical Computer Science. Perfect.
Juliusz Gonera
Very accessible intro to the theory of computation.
« previous 1 3 4 5 6 7 8 9 72 73 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
  • Types and Programming Languages
  • Introduction to Algorithms
  • Computers and Intractability: A Guide to the Theory of NP-Completeness
  • Art of Computer Programming, The, Volumes 1-3 Boxed Set
  • Modern Operating Systems
  • Concrete Mathematics: A Foundation for Computer Science
  • Compilers: Principles, Techniques, and Tools
  • Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)
  • The UNIX Programming Environment
  • Programming Language Pragmatics
  • Algorithm Design
  • Concepts, Techniques, and Models of Computer Programming
  • Programming Pearls
  • Computer Systems: A Programmer's Perspective
  • Applied Cryptography: Protocols, Algorithms, and Source Code in C
  • The Algorithm Design Manual

Goodreads is hiring!

If you like books and love to build cool products, we may be looking for you.
Learn more »
Introduction to the Theory of Computation. Michael Sipser Introduction to the Theory of Computation By Sipser (1st, First Edition) Introduction to the Theory of Computation, Instructor's Manual Εισαγωγή στη Θεωρία Υπολογισμού

Share This Book