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

by

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

...moreHardcover, Second Edition, 431 pages

Published
February 1st 2005
by Course Technology
(first published January 25th 1996)

## 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

Start your review of Introduction to the Theory of Computation

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

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

I chose to re ...more

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

Feb 27, 2021
Brian Powell
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

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

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

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

Clearly separate sections make for easy selection of your interest areas. ...more

There are no discussion topics on this book yet.
Be the first to start one »

## Goodreads is hiring!

236 users

70 users

44 users

43 users

42 users

33 users

31 users

28 users

21 users

20 users

## News & Interviews

If you've got an overflowing Want to Read shelf of books that you keep meaning to get to (one day!), you're in good company. Our company, that...

126 likes · 46 comments

No trivia or quizzes yet. Add some now »

“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…