Introduction to the theory of computation
by Michael Sipser · first published 2013
74% recommend26% neutral
Why HN recommends it
Readable, coherent introduction to automata, pushdown automata, Turing machines and decidability; friendly yet precise, with partial answers to exercises. Suits CS-minded readers without heavy math.
Summarised by Claude from recommending comments
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
Mentions per year
What Hacker News says
Related books
2008–2025Introduction to automata theory, languages, and computation
John E. Hopcroft, Jeffrey D. Ullman, Rajeev Motwani
Recommended by 24 · mentioned by 3324 recommend · 33 mention24 recommend · 3324 recommend
2008–2024Computational complexity
Christos H. Papadimitriou
Recommended by 7 · mentioned by 97 recommend · 9 mention7 recommend · 97 recommend
2012–2026Computer science
J. Glenn Brookshear, Brookshear
Recommended by 8 · mentioned by 118 recommend · 11 mention8 recommend · 118 recommend
2007–2026Artificial Intelligence
Stuart J. Russell, Peter Norvig
Recommended by 60 · mentioned by 13660 recommend · 136 mention60 recommend · 13660 recommend
2009–2026Computer systems
Randal Bryant, Randal E. Bryant, David R. O'Hallaron
Recommended by 67 · mentioned by 8367 recommend · 83 mention67 recommend · 8367 recommend
2007–2026Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Recommended by 274 · mentioned by 712274 recommend · 712 mention274 recommend · 712274 recommend
…Rivest, and Stein The Art of Assembly Language - Hyde a digital logic book (not sure which is most recommended), and an architecture book (see reply by tftfmacedo) Modern Operating Systems - Tanenbaum Introduction to the Theory of Computation - Sipser Compilers: Principles, Techniques, and Tools - Aho, Lam, Sethi, and Ullman (a.k.a. "Dragon Book") Programming Language Pragmatics - Scott A database design book (one that covers Relational…
on “Must Read CS Books For Self Self-Taught Programmers” ↗Two and a half years into my bachelor's, Sipser's Introduction to the Theory of Computation is the only computer science textbook I've had so far that I'd say I really found useful for anything beyond the homework problems, besides K.N. King's C Programming: A Modern Approach. (To keep this…
on “A list of free programming books” ↗…Edit: and the type state pattern http://cliffle.com/blog/rust-typestate/ As an aside, if you want to dive in with FSMs and automata theory (as well as some basic language topics) go read Sipser's book, "Introduction to the Theory of Computation." You'll go from logic to state machines to understanding why Turing Machines are so dope in a few dozen pages. The math isn't bad.
on “State Machines in Rust” ↗…Probably why I didn't like the course much. It feels like a bunch of disjoint topics held together very loosely by some techniques that get repeated a bit. I compare it very unfavorably to Sispser's Introduction to the Theory of Computation which, I felt, was much more coherent as a book. It's not a fair comparison at all because they're about different (although related) subjects, but I think it neatly illustrates my point. Also, I don't…
on “A list of free programming books” ↗The best introduction I’ve ever read is Michael Sipser’s Introduction to the Theory of Computation. It is eminently readable. It somehow manages to be logically rigorous while remaining approachable. I couldn’t recommend a book more strongly for someone such as yourself. As a bonus it’s not even particularly…
on “Computer science as a lost art (2015)” ↗…Turing's and Shannon's; but you're probably better off reading more recent textbooks. That said, to balance out the heavy emphasis on programming and engineering books here, some recommendations: - Sipser. Introduction to the Theory of Computation. - Russell, Norvig. AI: A Modern Approach. - For algorithms I don't have a preference. There is Dasgupta-Papadimitriou-Vazirani; Cormen-Leisersen-Rivest-Stein; Kleinberg-Tardos; and more. A bit farther…
on “Ask HN: What are the most fundamental books on computer science?” ↗I'll second the Algorithm Design book recommendation. An even better theory book is Introduction to the Theory of Computation by Sipser, however it covers slightly different topics. It is one of the most readable theory books I've seen, highly recommended, and a great resource for information on regular languages, context-free…
on “How to Pass a Silicon Valley Software Engineering Interview [PDF slides]” ↗…Algorithms, Purdom & Brown The Elements of Statistical Learning, Hastie, Tibshirani, Friedman Biological Sequence Analysis, Durbin et al. Artificial Intelligence: A Modern Approach, Russell & Norvig Introduction to the Theory of Computation, Sipser Introduction to Linear Algebra, Strang GEB is my 1/2
on “The Top 9½ Books In a Hacker's Bookshelf” ↗The best book on the subject I know of is Introduction to the Theory of Computation, by Michael Sipser. Very readable and lucid. Great exercises.
on “Ask HN: Good books on computational complexity?” ↗…paper that does not include some description of the blind alleys. In mathematics, being suspicious might be a bit much, but it's a very valuable (for your audience) habit to have. For example, the book Introduction to the Theory of Computation by Michael Sipser does this a lot: it often explores avenues that lead to dead ends before arriving at the correct proof. This is the way mathematicians work, and it's usually hidden from papers or other…
on “To Get More Out of Science, Show the Rejected Research” ↗Kozen's book that has been mentioned is very good. I also recommend Sipser's "Introduction to the Theory of Computation". It goes from Deterministic Finite Automata (equivalent in power to regular expressions in their purest sense, as opposed to POSIX regexps) to Context-Free Grammars and then finally Turing Machines.…
on “Show HN: Turing machine simulator in C” ↗I highly recommend Sipser's "Introduction to the Theory of Computation" if you want to learn more. Here's a link to the edition I had in college (around 2002): http://www.amazon.com/Introduction-Theory-Computation-Michae... It's used at MIT (http://math.mit.edu/~sipser/18404/),…
on “Implementing Regular Expressions (2007)” ↗@galeaspablo, sorry I should have been more clear. What I meant is basically the comment above. I highly recommend "Introduction to the Theory of Computation" by Sipser. As I mentioned in my original comment, I barley passed Calculus. CS Theory is still math, but just... without numbers. The class felt more like solving puzzles, if anything. Writing proofs…
on “Lambda School Announces $14M Series A Led by GV” ↗…recommend you, and most of them I was able to read cover-to-cover during the university years. And they are also in my bookshelf for reference. The book order does not represent rank of importance. * “Introduction to the Theory of Computation”, by Michael Sipser. * I also recommend the “Elements of the Theory of Computation”, by Christos Papadimitriou. * Another good complement is “Introduction to Automata Theory, Languages and Computation”,…
on “Ask HN: What are the most fundamental books on computer science?” ↗I TAed the class for a while in undergrad and it was one of the few CS classes with a textbook that really actually helped and augmented the lectures/homework. The one we used was Introduction to the Theory of Computation by Michael Sipser (not hard to find a pdf online).
on “The Elements of Computing Systems, Second Edition” ↗