Understanding Computation
From Simple Machines to Impossible Programs
by Tom Stuart · first published 2013
76% recommend24% neutral
Why HN recommends it
Introduction to computation theory for working programmers, using Ruby to build toy interpreters, Turing machines and lambda calculus from examples and exercises. Suits those without a CS theory background.
Summarised by Claude from recommending comments
Finally, you can learn computation theory and programming language design in an engaging, practical way. Understanding Computation explains theoretical computer science in a context you’ll recognize, helping you appreciate why these ideas matter and how they can inform your day-to-day programming. Rather than use mathematical notation or an unfamiliar academic programming language like Haskell or Lisp, this book uses Ruby in a reductionist manner to present formal semantics, automata theory, and functional programming with the lambda calculus. It’s ideal for programmers versed in modern lan
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
Mentions per year
What Hacker News says
Related books
2013–2025Good Math
Mark C. Chu-Carroll
Recommended by 3 · mentioned by 63 recommend · 6 mention3 recommend · 63 recommend
2008–2024Algorithmics
David Harel
Recommended by 11 · mentioned by 1211 recommend · 12 mention11 recommend · 1211 recommend
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
2009–2026The Annotated Turing
Charles Petzold
Recommended by 56 · mentioned by 7056 recommend · 70 mention56 recommend · 7056 recommend
2008–2026Introduction to the theory of computation
Michael Sipser
Recommended by 66 · mentioned by 8966 recommend · 89 mention66 recommend · 8966 recommend
2008–2026Code
Charles Petzold
Recommended by 243 · mentioned by 287243 recommend · 287 mention243 recommend · 287243 recommend
2012–2025Practical Object Oriented Design In Ruby
Sandi Metz
Recommended by 46 · mentioned by 6246 recommend · 62 mention46 recommend · 6246 recommend
2007–2026The algorithm design manual
Steven S. Skiena
Recommended by 195 · mentioned by 265195 recommend · 265 mention195 recommend · 265195 recommend
…enjoyable nonetheless so I would recommend that book to anyone, even to people like me who don’t really like Ruby in general and don’t really want to read or write Ruby in general. Stuart, T., 2013. Understanding Computation: From Simple Machines To Impossible Programs. O’Reilly. Book website: https://computationbook.com/
on “Design Principles Behind Smalltalk (1981)” ↗The book "Understanding Computation: From Simple Machines to Impossible Programs" by Tom Stuart was/is my Theory Of Computation Nirvana experience. Its motives is the same as NandToTetris: to make any programming-literate person comfortable…
on “The Elements of Computing Systems, Second Edition” ↗Understanding Computation by Tom Stuart [0]. While not soley dedicated to creating a language, the first couple of chapters deal with building semantics of a simple language using Ruby as the implementation language (but easily…
on “Ask HN: Resources for building a programming language?” ↗Take a look at: Understanding Computation: From Simple Machines to Impossible Programs by Tom Stuart. It's pretty much "computation theory for the everyday programmer". It uses Ruby to implement things like Turing Machines and the lambda calculus.…
on “Computer Science from the Bottom Up” ↗…about it already have a look at what people are saying; https://hn.algolia.com/?query=sicp&sort=byPopularity&prefix&.... Great book, and one that I will definitely be reading again in the future. 4. Understanding Computation: From Simple Machines to Impossible Programs. Tom Stuart. 2013. O'Reilly. http://computationbook.com/. A fun and gentle book covering a range of computer science topics. He's using Ruby which personally…
on “MIT lecturer Ana Bell discusses books to learn CS and programming” ↗Understanding Computation: From Simple Machines to Impossible Programs by Tom Stuart https://www.amazon.co.uk/Understanding-Computation-Machines-... Not finished it yet, but it's a joy to read and explains fundamental concepts…
on “Ask HN: What's the best computer science book you've read recently?” ↗The description immediately reminded me of a book called "Understanding Computation." Scrolling down I see the video is by Tom Stuart, the author of that book. I'd really recommend it (the book) for anyone interested in learning about "big step" (operational) and "small step" (structural)…
on “Compilers for Free” ↗My recommendations are not exactly what you ask but what I suspect you'll enjoy if you're asking this. (1) "Understanding Computation" by Tom Stuart. Not "fundamental" as a deep textbook, but very approachable for programmers intro into a big chunk of CS, explaining deep ideas about languages using rigorous working clean code (in Ruby,…
on “Ask HN: What are the most fundamental books on computer science?” ↗* Understanding Computation: From Simple Machines to Impossible Programs by Tom Stuart. * Out of their Minds: The Lives and Discoveries of 15 Great Computer Scientists by Dennis Shasha et al. * Ideas That Created the Future: Classic…
on “Ask HN: Top inspiring books on crucial CS ideas?” ↗Understanding Computation by Tom Stuart is very good. [https://computationbook.com]
on “Ask HN: Recommendations for books and tutorials on Theory of Computation” ↗Nice! If folks would like to learn these ideas by hand via programming, i highly recommend Tom Stuart's Understanding Computation From Simple Machines to Impossible Programs - https://computationbook.com/
on “Great ideas in theoretical computer science” ↗Another excellent book is Tom Stuart's Understanding Computation : From Simple Machines to Impossible Programs - https://computationbook.com/
on “What can be computed? A practical guide to the theory of computation (2018) [pdf]” ↗This is quite unique and interesting; thanks for posting. Seems like there might be some overlap with Tom Stuart's excellent Understanding Computation book - https://computationbook.com/
on “Making your own programming language is easier than you think (but also harder)” ↗I just picked up Understanding Computation and, having made it through the first two chapters at this point, heartily recommend it. If anyone wants to have a little reading group, I'd be interested. http://shop.oreilly.com/product/0636920025481.do
on “Save 50% on All O'Reilly Ebooks and Videos” ↗I recommend "Understanding Computation" from O'Reilly - it's pretty straightforward, teaches through examples and exercises, and uses Ruby, to build toy compilers from first principles. It's not going to give you the mathematical basis that…
on “Rich Programmer Food (2007)” ↗