A question partly inspired by a recent question on the utility of FSMs: Years ago noticed the following property of FSM transducers with $\epsilon$-transitions (which allow an "empty" transition without an output symbol). Its not complicated but not trivial either; it seems to be rarely taught, and also shows a close relationship between FSMs and TMs. It also shows up as a somewhat/seemingly natural mechanism for studying the Collatz conjecture by linking to questions on automata.
Take any TM and consider the sequence of IDs, instantaneous description strings, associated with the TM tape and current state, also called a "computational tableau". (Details of the ID format/encoding are not nec so important but one simple method is to have the current TM state located embedded in the string at the current head position.) The sequential results of the TM after each TM step, $d_1, d_2, ... d_n$ can be computed by a FSM transducer with $\epsilon$-transitions, working left-to-right. am interested in answers to any of the following questions.
- What are some refs that refer to this correspondence/construction (computation of TM tableaus by FSM transducer iterations)?
- What is the earliest one to point it out?
- What are some notable results (if any) related to it?
Note, FSM transducers were also called "generalized sequential machines" in early automata theory from the 1960s.