A Turing transition is a compiled first return
ProvedMonodromy.Counter.TuringCompiler.step_firstReturnFor positive a,q, every TM0 machine over Fin a and Fin q and every successful source transition s→t, the three-counter encodings satisfy the compiler’s FirstReturn relation: there is one successful compiled step from encode(s), followed by a finite possibly empty chain of compiled steps whose departure addresses are not source dispatches, ending at encode(t).
Statement dependencies: Monodromy.Counter.TuringCompiler.FirstReturn, Monodromy.Counter.TuringCompiler.encode.
Original proof dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.Instruction, Monodromy.Counter.TuringCompiler.FirstReturn, Monodromy.Counter.TuringCompiler.InternalReaches, Monodromy.Counter.TuringCompiler.InternalStep, Monodromy.Counter.TuringCompiler.base, Monodromy.Counter.TuringCompiler.dispatch, Monodromy.Counter.TuringCompiler.encode, Monodromy.Counter.TuringCompiler.move_reaches, Monodromy.Counter.TuringCompiler.mulTarget, Monodromy.Counter.TuringCompiler.program, Monodromy.Counter.TuringCompiler.program_dispatch, Monodromy.Counter.TuringCompiler.size, Monodromy.Counter.TuringCompiler.write_step, Monodromy.Counter.step, Monodromy.TapeCode.encode.
Statement elaboration dependencies: Monodromy.Counter.TuringCompiler.FirstReturn, Monodromy.Counter.TuringCompiler.encode.
Proof elaboration dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.Instruction, Monodromy.Counter.TuringCompiler.FirstReturn, Monodromy.Counter.TuringCompiler.InternalReaches, Monodromy.Counter.TuringCompiler.InternalStep, Monodromy.Counter.TuringCompiler.base, Monodromy.Counter.TuringCompiler.counters, Monodromy.Counter.TuringCompiler.dispatch, Monodromy.Counter.TuringCompiler.encode, Monodromy.Counter.TuringCompiler.move_reaches, Monodromy.Counter.TuringCompiler.mulTarget, Monodromy.Counter.TuringCompiler.program, Monodromy.Counter.TuringCompiler.program_dispatch, Monodromy.Counter.TuringCompiler.size, Monodromy.Counter.TuringCompiler.write_step, Monodromy.Counter.step, Monodromy.TapeCode.encode.
module public import Definitions.Def_Monodromy_Counter public import Lean.Elab.Tactic.Omega public import Mathlib.Analysis.Analytic.Constructions public import Mathlib.Analysis.Analytic.IsolatedZeros public import Mathlib.Analysis.Analytic.Linear public import Mathlib.Analysis.Calculus.DSlope public import Mathlib.Analysis.Calculus.Deriv.Add public import Mathlib.Analysis.Calculus.Deriv.Comp public import Mathlib.Analysis.Calculus.Deriv.Mul public import Mathlib.Analysis.Calculus.Deriv.Pow public import Mathlib.Analysis.Complex.Basic public import Mathlib.Analysis.Complex.CoveringMap public import Mathlib.Analysis.Real.Pi.Bounds public import Mathlib.Analysis.SpecialFunctions.Complex.Analytic public import Mathlib.Analysis.SpecialFunctions.Complex.Circle public import Mathlib.Computability.StateTransition public import Mathlib.Computability.TuringMachine.PostTuringMachine public import Mathlib.Data.Fin.Basic public import Mathlib.Data.Fintype.Card public import Mathlib.Data.Fintype.EquivFin public import Mathlib.Data.Nat.Digits.Lemmas public import Mathlib.Data.Nat.Factorization.Basic public import Mathlib.Logic.Equiv.Fin.Basic public import Mathlib.Logic.Equiv.Fin.Rotate public import Mathlib.Logic.Function.Basic public import Mathlib.Logic.Function.Conjugate public import Mathlib.RingTheory.RootsOfUnity.Complex public import Mathlib.Tactic.FieldSimp public import Mathlib.Tactic.FinCases public import Mathlib.Tactic.FunProp public import Mathlib.Tactic.Linarith public import Mathlib.Tactic.Ring public import Mathlib.Topology.Homotopy.Lifting @[expose] public section open Monodromy open Monodromy.Counter open Monodromy.Counter.TuringCompiler open Turing variable (a q : ℕ) [NeZero a] [NeZero q]
theorem Monodromy.Counter.TuringCompiler.step_firstReturn (machine : TM0.Machine (Fin a) (Fin q))
{first last : TM0.Cfg (Fin a) (Fin q)} (source : TM0.step machine first = some last) :
FirstReturn a q machine (encode a q first) (encode a q last) := by sorry
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
For all positive natural numbers , every partial Turing table on controls and symbols, and any two complete configurations such that one ordinary Turing transition returns from , there exists a compiled three-counter configuration such that one actual step of the compiled table sends to and a finite sequence of actual steps from reaches with every source in that latter sequence outside the dispatch controls. The encoding puts the source control and scanned symbol into a dispatch tag, encodes the left and right blank-padded half-tapes with least-significant-first digits in base , and adds a third scratch counter initialized to . The compiler has separate row-tagged multiplication, addition and division cells for move instructions; it multiplies the half-tape being left by , adds the old scanned symbol, divides the half-tape being entered, and dispatches to the target control and remainder symbol, mapping the extra residue to blank . A write instruction uses a decrement of scratch with the same target on its zero and nonzero branches to dispatch to the new control and written symbol, and an absent Turing instruction gives halt. The relation named first return is defined only by the one initial step followed by the stated reflexive transitive interior closure; it has no separate endpoint-boundary clauses, although these particular endpoints are dispatch encodings. The interior part may have zero steps, but the whole witnessed run has at least one; the theorem covers writes, both move directions, blank tapes and , and assumes no later termination.
Confirmed by the mission captain (proposal self-audit).