[bogomipz]

>"The only thing that rivaled that lightbulb was aspects of Theory of Computation with undecidability, turing machine vs stack machine vs state machine powers that theoretically limit Von Neumann architecture."

Might you or someone else have a title that you would recommend for this that is the equivalent of a "Elements of Computing Systems" style book?

[qwertygnu]

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).

[gengear]

can borrow one at open library https://openlibrary.org/works/OL18180546W/Theory_of_computat...

[AtlasBarfed]

It was 1995... so the Comp Org was Tanenbaum's Structured Computer Organization. I also used his Operating Systems book in the OS class. I thought they were excellent but I also had great profs.

I'll try to find my theory of computation text so I can see who wrote that, but again that was a great prof that walked through it really well.

Alas my bias against lisp may solely be traced to the Programming Languages prof that loved Scheme but couldn't actually communicate with humans. He could recite pi to 100 decimal places and was esteemed as brilliant but literally couldn't form sentences when talking to students. I suspect the lambda calculus would have been a good insight as well, but oh well.

[bear8642]

Sounds like you had an excellent romp = was scheme taught with SICP?

Lambda calculus' anonymous functions are fairly simple but massively powerful - try this page? <https://www.inf.fu-berlin.de/lehre/WS03/alpi/lambda.pdf>

[Banana699]

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 with the rough outlines of the theory of computation and its main lore and results. The author uses Ruby as an interactive "Illustration language", a notation to describe concepts that happens to be executable. It's the same way I noticed the authors of "Structure and Ineterpetation of Computer Programs" use scheme or the way Niklaus Wirth sometimes uses Pascal in his educational writings. There is a small tutorial chapter in the beginning that crash-courses you through all what you need to understand in Ruby to read the book.

The structure is a bit different, the book isn't project-based like ECS, and there is no natural hierarchy to the theory of computation (except maybe the famous state_machines ==( push_down_automatons ==( turing_machines, and the book does introduce those topics in the natural order) that would make the book feel more bottom up. There is no exercises or nudges towards exploration and tinkering so you need to come equipped with your own. I stopped trying to digest it in one reading and designated it as one of those books you come back over and over again to fully absorb its nourishment.

But the main motivation of the book is strikingly similar to that of ECS: to take a complex and jargon-heavy several-years study topic and distill the most essential lines and edges so that a minimally-educated person motivated enough to understand could mostly understand. Some parts felt rushed and weren't meant to be digested in full details (when he was e.g. discussing a "zoo" of other computational systems that feels superficially different or less powerful than turing machines but are equivalent nonetheless, he was fairly hand-waivy), but the book is so great you will feel guilt dwelling on its shortcomings.

[tomstuart]

That’s a very generous comparison, thank you!

[bogomipz]

This is fantastic. I will definitely search this title out. Thanks for the wonderfully detailed response. This sounds exactly what I was looking for. Cheers.

[jgwil2]

I would add that I like Michael Sipser's Introduction to the Theory of Computation. It provides an introduction that explains a lot of the mathematical concepts and notation, which is helpful for self-study. Covers all the material mentioned, as well as time- and space-complexity and some other topics. However, it is basically a math textbook, so it doesn't have any actual code that you can run (you might code up the theoretical machines as an exercise). Rather, it mainly consists of theorems and their proofs.