Embed Notice

@lanodan @Moon For finite-state machines, regular languages are sufficient. And it can be argued that a memory-constrained computer is a finite-state machine (a state is the immediate contents of registers, memories, drives, &c; inputs are clocks and I/Os. The number of states is finite (though absurdly large) and the state change is well-defined for any input).

So it theoretically should be possible to create an actually-regular expression describing a “computation” of a computer (but not an unbounded Turing machine).

(TIL: there seems to be a convention that “regular expressions” are expressions describing regular languages, and “regexes” are the patterns used in programming languages, regular or not.)