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,814 ratings  ·  73 reviews
Michael Sipser's philosophy in writing this book is simple: make the subject interesting and relevant, and the students will learn. His emphasis on unifying computer science theory - rather than offering a collection of low-level details - sets the book apart, as do his intuitive explanations. Throughout the book, Sipser - a noted authority on the theory of computation - b ...more
Hardcover, 396 pages
Published December 13th 1996 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

This book is not yet featured on Listopia. Add this book to your favorite list »

Community Reviews

Showing 1-30
Average rating 4.23  · 
Rating details
 ·  1,814 ratings  ·  73 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  ·  review of another edition
This had lots of good, practical advice.
Tikhon Jelvis
Aug 01, 2015 rated it it was amazing  ·  review of another edition
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
...more
Nick Black
Mar 23, 2008 rated it really liked it
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  ·  review of another edition
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
...more
Omesh
Aug 31, 2014 rated it liked it  ·  review of another edition
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
Thắng
Sep 22, 2020 rated it it was amazing  ·  review of another edition
I am desperate, so I review my text book.
Tianyao Chen
May 23, 2020 rated it it was amazing  ·  review of another edition
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  ·  review of another edition
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.
Shawn
Jan 04, 2014 rated it really liked it  ·  review of another edition
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
Adam
Aug 03, 2020 rated it it was amazing  ·  review of another edition
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
...more
Lily
Feb 13, 2016 rated it it was amazing
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
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.
...more
Antonis Maronikolakis
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.

An
...more
Abdurrezzak Efe
Aug 26, 2018 rated it it was amazing  ·  review of another edition
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
...more
Robert L
Oct 29, 2019 rated it did not like it  ·  review of another edition
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
Thor
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.
...more
Matthew
Nov 08, 2020 rated it it was amazing  ·  review of another edition
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  ·  review of another edition
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  ·  review of another edition
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
Ahmed Abd El-Hamid
An excellent introduction to Theoretical Computer Science and it has been a great pleasure to read it
Егор Лебедев
Great book for grads and theoreticians.
George
Jan 14, 2018 rated it it was amazing  ·  review of another edition
Insightful. A must read.
Touny
Jun 29, 2018 rated it it was amazing  ·  review of another edition
The most readable introductory textbook out there.
Robert
Feb 23, 2019 rated it really liked it  ·  review of another edition
Shelves: science
Classic.
Taymur Bajwa
Oct 29, 2019 is currently reading it  ·  review of another edition
Shelves: book
good book
Irvi
Dec 26, 2019 rated it it was amazing  ·  review of another edition
Recommended for those who wants to learn CFG, automata, as well as Turing machine.
Jordan Wick
Jan 12, 2020 rated it it was amazing  ·  review of another edition
Used it for a class, was very easy to understand and learn from. Almost good enough to be used as a substitute for lecture, although I wouldn’t recommend that.
« 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
  • Pattern Recognition and Machine Learning
  • Compilers: Principles, Techniques, and Tools
  • Algorithm Design
  • Discrete Mathematics and Its Applications
  • Deep Learning
  • Computer Organization & Design: The Hardware/Software Interface
  • The Mythical Man-Month: Essays on Software Engineering
  • Operating System Concepts
  • Modern Operating Systems
  • Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)
  • The Annotated Turing: A Guided Tour Through Alan Turing's Historic Paper on Computability and the Turing Machine
  • Computer Networking: A Top-Down Approach
  • Practical Common LISP
  • Designing Data-Intensive Applications
  • 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

  Die-hard mystery fans are always on the hunt for their next supremely satisfying whodunit. To help you stock that Want to Read shelf, we asked...
52 likes · 22 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…