LEdoian@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.)
All GNU social JP content and data are available under the