iterations of a $\epsilon$-FSM transducer on a tape as equivalent to a TM computation

Question

A question partly inspired by a recent question[1] 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.[2]

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.

[1] What is the enlightenment I'm supposed to attain after studying finite automata?

[2] Collatz Conjecture & Grammars / Automata

Answer 1

We used this idea in our paper [J. Shallit and D. Swart, An Efficient Algorithm for Computing the ith Letter of phi^n (a), SODA 1990, 768-777] to show that a problem about iterated finite-state transducers is EXPTIME-hard.

Answer 2

Yes, it is a lovely observation. At first it might be a little surprising, but it is widely known, in disguise.

If we write the instantaneous description of a Turing machine as $vqw$, where $q$ is the state, $v,w$ are the segments left and right of the head, then the next ID of the TM is obtained by just a local transformation of the string $vqw$ (namely $q$, the letter next to $q$ that the TM is reading, and one or two neighbouring letters). This observation is used when showing that every TM accepted language can be generated by a type-0 grammar. Such a grammar can only transform a local part of the string (and thus this can be simulated by a FST/GSM). Applying consecutive derivation steps then is iterating the transducer.