Surprisingly Turing-Complete (2021)
Not quite Turing-complete, but any Turing machine <i>that halts on a given input</i> can be simulated by a sufficiently large finite state machine. At each step, a complete TM state can be represented by a tuple of &lt;TM state #, cell position, tape state&gt;. If the TM halts, then it can only have visited a finite number (K) of cells on its tape, plus every possible TM state (N), plus every possible cell position (K), plus every possible state of the tape (2^K). Therefore, we can number each possible state from 1 to N * K * (2^K). Those are the states of our FSM. The FSM transitions are wired up to match the TM transitions to the corresponding TM destination state.<p>Similarly, any actual computer with finite memory can be modeled as a finite state machine with 2^(# bits of all memory, registers, storage) states.<p>Edit: Changed &quot;<i>that halts</i>&quot; to &quot;<i>that halts on a given input</i>&quot;.