Theory of computation
by Michael Sipser · first published 2007
74% recommend26% neutral
Why HN recommends it
Clearly written intro to automata and languages, computability, and complexity, with proofs that give a short proof idea first and then the details. Suits self-learners and course readers wanting a solid base.
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
2018–2022How Computers Work
Roger Young
Recommended by 2 · mentioned by 22 recommend · 2 mention2 recommend · 22 recommend
2019–2022Introduction to Topological Manifolds
John M. Lee
Recommended by 2 · mentioned by 22 recommend · 2 mention2 recommend · 22 recommend
2018–2020An introduction to formal languages and automata
Peter Linz
Recommended by 4 · mentioned by 54 recommend · 5 mention4 recommend · 54 recommend
2008–2024Algorithmics
David Harel
Recommended by 11 · mentioned by 1211 recommend · 12 mention11 recommend · 1211 recommend
2008–2026Computers and intractability
Michael R. Garey, David S. Johnson
Recommended by 5 · mentioned by 115 recommend · 11 mention5 recommend · 115 recommend
2018–2026Algorithms Illuminated
Tim Roughgarden
Recommended by 9 · mentioned by 109 recommend · 10 mention9 recommend · 109 recommend
2008–2024Computational complexity
Christos H. Papadimitriou
Recommended by 7 · mentioned by 97 recommend · 9 mention7 recommend · 97 recommend
2016–2026Programming in the 1990s
Edward Cohen
Recommended by 1 · mentioned by 31 recommend · 3 mention1 recommend · 31 recommend
…with reason and right judgement in order to get there. Also, happiness is not a state but rather the result of our active will and right ordering of desire. Required reading for any political leader. - Theory of Computation by Michael Sipser: Javascript frameworks come and go, language standards change, Computer platforms rise and fall, but math and the underling concepts of computation stay the same. Knowing what computation…
on “Ask HN: What are some of the best books you have read in 2022?” ↗…to it 5) Optimization by Boyd and Vanderberghe 7) There's no single topic called "Computer Science", but going with the theme of the topics you are looking at, Algorithms by Cormen, Leiserson et. al, Theory of Computation by Michael Sipser should be good starting points. Note that for a lot of these, you can find high quality material online (Both videos as well as course material). Just do a search for "Topic MIT OCW",…
on “Ask HN: Mathematicians, what textbooks are best for learning these math topics?” ↗…studied it. I read it in sixth form, and it probably swung me more towards CS from my since-childhood intention of studying electronics. (Ended up doing a mix, but applied to some straight CS too.)) Theory of Computation by Sipser. (More subject specific and just a textbook really, I just thought it was a really great one and was able to read it ahead of my most relevant course.)
on “Ask HN: The book that did it for you in math and/or CS?” ↗…best book in each subject and read that instead. Most of them were fairly old. Some examples that I remember off the top of my head: Intro to CS: SICP (1979) Algorithms/data structures: CLRS (1989) Theory of computation: Sipser (1996) Compilers: Dragon book (1986) Calculus: Spivak (1967) Linear Algebra: Dover's by Shilov (1971) The given year is for the first publication, some of them are still being updated and…
on “Ask HN: Older textbooks/papers you consider classics still worth studying today?” ↗…work you want? If not, you probably don't need to learn it. That being said, if you want to get into CS, I recommend getting a textbook or two about computational complexity (big-O notation) and the theory of computation (nondeterministic finite automata and regular expressions, stack machines, and Turing machines). I liked "Theory of Computation" by Michael Sipser for the second topic (didn't like my textbook for the…
on “Ask HN: Why do many software engineers not know data structures and algorithms?” ↗…for peer review. That could take well over a year. Well, in the meanwhile, I have a question: what's a good intro resource to quantum computing? For general complexity intro, I like Michael Sipser's Theory Of Computation
on “A Polynomial Time Bounded-Error Quantum Algorithm for Boolean Satisfiability” ↗…https://courses.csail.mit.edu/6.042/spring18/mcs.pdf This is distinctive for its intuitive explanations with essential, approachable formalism. The exercises are fine too, if you are really mean it. Sipser's book on the Theory of Computation is great and the one by Hopcroft et al is also very good (as suggested by others). But the most beginner-friendly (or, light on math) coverage of this area is apparently in Peter Linz's book "Introduction…
on “Ask HN: What book to read to get a footing in CS theory?” ↗…Principles of Effortless Power by Peter Ralston (martial artist) A lot of stuff by John-Roger (spiritual author) - helped me decide that I'm here to serve the people around me, as best I can Intro to the Theory of Computation, by Mike Sipser Many of the physics books I've read over the years (though now a hacker I be, I started as a scientist... still am at heart). Not one in particular, except maybe Modern Quantum Mechanics…
on “Books That Changed My Life” ↗…by actually working through a system and its rules. It's hard to actually trace reasoning down the entire "stack" like you would when working in code. The only GOOD math-y books I've read are Sipser's Theory of Computation and GEB. The tone of these is "Here's how shit is, and here's why Y makes sense if you accept X", not "Here's the problems you'll be doing on the test, and you have to practice them so you can solve them…
on “Notation And Thinking” ↗…seminars than larger introductory courses, where recent papers are most relevant. For intro courses, coming up with good intro materials is a fairly hard problem. If I were teaching an intro course on theory of computation, for example, I would probably still use Michael Sipser's Theory of Computation, because it's good, and I don't think I would be likely able to put together an equally good replacement out of freely available…
on “The Textbook Industry & Greed: My Story” ↗If someone asked for my recommendations for reading on state machines I would point them to Michael Sipser's Introduction to Theory of Computation. http://www.amazon.com/Introduction-Theory-Computation-Michae... Though I get the impression you're looking for something a bit more like an oreilly cookbook or nutshell book.
on “What is the enlightenment I'm supposed to attain after studying finite automata?” ↗Sipser's Theory of Computation is the closest thing I could think of to an all-round essential.
on “Ask HN: what are some essential theoretical computer science books?” ↗Sipser's Theory of Computation. It covers automata and languages, computability, and complexity - and is brilliantly written, the proof style in particular: clear 'proof idea's followed by the details that can be easily skipped if…
on “Ask HN: What language-agnostic programming books should I read?” ↗Lots of favorite math books! Not as many programming. Maybe I'd recommend Sipser's Intro to the Theory of Computation?
on “A Programmer's Introduction to Mathematics” ↗As someone else said already: Theory of Computation by Sipser is the go to intro book for this. I'd recommend really reading the book front to back honestly. It helps to have a complete picture of everything that leads up to getting into complexity theory.…
on “Recommended Books on Computational Complexity Theory” ↗