Proof of `Every two-way transducer computes a regular function`
What this proof establishes
no assumptions
Assuming the claims on the left, the claim on the right holds — checked by the archive's pipeline. Proof code is not displayed here.
Description
Every two-way transducer computes a regular function (Theorem C.2.9, the hard implication), .
Proof strategy
The source reduces to the snake lemma in its general form (, ): a halting run visits every column at most times, so the function is its own width- output function, and the width- output function is regular by induction on , cutting the run at the record-breaking columns into looping and progressing parts of smaller width (, , , the family) and gluing them with Lemma C.2.10.
Attribution
Theorem C.2.9 of Transducers, Part C; formalised by Aristotle (Harmonic).