Also, https://matklad.github.io/2018/06/06/modern-parser-generator.html is worth a read even if you're only kind of interested in parsers. There's epiphanies in it. Like:
Regular languages (regex's) are state machines with a fixed memory space.
Full Turing machine languages are state machines with two stacks of memory space (moving the Tape is popping an item from one stack and pushing it to the other).
Context-free languages are exactly in the middle: they're state machines with one stack.
I don't know what it means but it's deep.
I don't know if it's a coincidence that the math behind models of computation and the programs we create to parse human (and machine) languages are so closely related, but it's a compelling coincidence even so.
@Azure I knew that there was a hierarchy of expressiveness but didn't know it could be summed up so simply.
What does one get when one gives a state machine *three* stacks? (No increase in expressiveness, I'm sure, given that a Turing machien can represent any number of stacks you want it to... but *why*?)
@icefox I think the insight to be had from this is that in a sense it's hard NOT being Turing complete.
The simplest universal Turing machine is pretty simple. There are surprisingly simple universal cellular automata. There are the infamous One Instruction Set Computers like Subtract and Branch if Negative. And as the Langsec people have pointed out people are constantly creating Turing complete formalisms without meaning to or noticing that they have.
This probably makes extropians happy.
@Azure That is probably a very good way to view it!
Though I suspect that if it makes extropians happy they are extropians who have no conception of how difficult it is to do anything terribly complicated with a Turing-equivalent machine...
@icefox Would you prefer to have Computation as an eldritch abomination?
Dripping into our world wherever complexity leaves a gaping crack in reality.
It is omnipotent: All things that can be done it can do.
It is unstoppable, or at least you will never know if it can be stopped.
Unless you ward against it strictly and set your mind to keeping it out, you'll invite it in to your reality........
@Azure That sounds like a pretty good description of computation as it currently is...
@icefox This is the Chomsky Hierarchy. Linear Bounded Automata can parse context sensitive languages, too. Chomsky's work on formal languages is why some linguists have an Erdos number.