Yeah, but what if we didn't do that? I.e. when we are reading from memory, we treat it as part of the tokenized input stream, and whatever we are writing to memory is just the transformed output of the state machine.

This way, the contents of the memory wouldn't be state at all; they would just be, as it were, the scratchpad where sentences in the language accepted by the state machine, or output by the state machine, are found.

That's what regular expressions do for us: they are a compact way of specifying a language. Just a few characters--which is to say, just a few states--can specify a language which contains arbitrarily long strings.

But--even though the input and output streams can be very large, they no longer part of the state, and thus do not contribute to the exponential blowup of states.

Except the tape gets overwritten/looped over. What GP was referring to is event-sourcing the state in an append-only log and running finite state automata on this sequence.

Here is a java lib that apply regex to stream of Objects that could be used to achieve this purpose.

https://github.com/norswap/skelex