> Not that that would necessarily make sense in practice, but in theory Markov chains have enormous expressive power.

Right - but this feels like being half-way between transformers and lookup tables; the latter have enormous expressive power too, as long as you're willing to handle even more state. I'm curious what else could be put on that spectrum, and where. Maybe there's something weaker than transformers, but good enough for practical applications, while being more resource-efficient?

Related thought: understanding and compression seem to be fundamentally the same thing.