## Key is that one time step and the next are related by a “regular relation”: can be expressed by a finite-state transducer

- $:$ (0:0|1:1)* (L1:A1 Q1:B1 R1:C1|L2:A2 Q2:B2 R2:C2|...) (0:0|1:1)* $:$
- Writing, moving and state transitions expressed by small table of triples

## If we collapse into one sequence of alternating symbols, can be expressed using FSM

- $$ (00|11)* (L1A1 Q1B1 R1C1|L2A2 Q2B2 R2C2|...) (00|11)* $$

Start by considering a single TM transition. The tape away from the head does not change. The cell the head is over may change contents, the state may change, and the head may move left or right one cell. Thus, all change takes place in a window of 3 cells centered on the head, and within these cells only a small finite number of before and after configurations are possible. Therefore the set of permitted transitions can be encoded using a

We can change the representation so that the before-and-after contents of each cell are interleaved, as in the lower diagram. There the gray cells represent the tape at the current time step, and the white cells the tape at the next time step. Then a single row reflects one transition, and the consistency of that transition can be enforced by a