Draft — mutable and not usable as a dependency; its citation marks the draft state.

Proof of `Every two-way transducer computes a regular function`

groundedproofs/Lax916827Proofs/Results.lean · lax-916827

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.

Read the Lean proof on GitHub

Description

Every two-way transducer computes a regular function (Theorem C.2.9, the hard implication), Transducers.twoWayisRegularTransducers.twoWay_isRegular.

Proof strategy

The source reduces to the snake lemma in its general form (Transducers.boundedWidthisRegularTransducers.boundedWidth_isRegular, PartC/SnakeReg.leanPartC/SnakeReg.lean): a halting run visits every column at most Q|Q| times, so the function is its own width-Q|Q| output function, and the width-kk output function is regular by induction on kk, cutting the run at the record-breaking columns into looping and progressing parts of smaller width (PartC/SnakeWalk.leanPartC/SnakeWalk.lean, PartC/SnakeRec.leanPartC/SnakeRec.lean, PartC/SnakeLoop.leanPartC/SnakeLoop.lean, the PartC/SnakeChk.leanPartC/SnakeChk*.lean family) and gluing them with Lemma C.2.10.

Attribution

Theorem C.2.9 of Transducers, Part C; formalised by Aristotle (Harmonic).