A Turing move division macro returns the new head
ProvedMonodromy.Counter.TuringCompiler.divide_reachesLet a,q be positive and suppose a TM0 machine selects a move in direction d from row=(σ,h) to target state t. For any natural pop-register value v and spectator w, the compiled three-counter table has an internal run from the division consume-zero entry for that move to the dispatch for t and the decoded remainder of v modulo a+1, with pop register ⌊v/(a+1)⌋, spectator w and scratch 0. The unused remainder a is decoded as blank 0, and every departure state of the run is outside the dispatch set.
Statement dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.DivMod.consume, Monodromy.Counter.DivMod.residue, Monodromy.Counter.TuringCompiler.InternalReaches, Monodromy.Counter.TuringCompiler.Row, Monodromy.Counter.TuringCompiler.base, Monodromy.Counter.TuringCompiler.base_neZero, Monodromy.Counter.TuringCompiler.dispatch, Monodromy.Counter.TuringCompiler.divTarget, Monodromy.Counter.TuringCompiler.frame, Monodromy.Counter.TuringCompiler.popRegister, Monodromy.Counter.TuringCompiler.size, Monodromy.Counter.TuringCompiler.symbol.
Original proof dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.DivMod.configuration, Monodromy.Counter.DivMod.consume, Monodromy.Counter.DivMod.finish, Monodromy.Counter.DivMod.program, Monodromy.Counter.DivMod.reaches_divmod, Monodromy.Counter.DivMod.residue, Monodromy.Counter.DivMod.size, Monodromy.Counter.Instruction, Monodromy.Counter.RegisterRelocation.embed, Monodromy.Counter.RegisterRelocation.pairIntoThree, Monodromy.Counter.RegisterRelocation.pairIntoThree_injective, Monodromy.Counter.RegisterRelocation.program, Monodromy.Counter.RegisterRelocation.reaches_embed, Monodromy.Counter.TuringCompiler.Boundary, Monodromy.Counter.TuringCompiler.InternalReaches, Monodromy.Counter.TuringCompiler.Row, Monodromy.Counter.TuringCompiler.base, Monodromy.Counter.TuringCompiler.base_neZero, Monodromy.Counter.TuringCompiler.dispatch, Monodromy.Counter.TuringCompiler.divTarget, Monodromy.Counter.TuringCompiler.divTarget_finish, Monodromy.Counter.TuringCompiler.div_live, Monodromy.Counter.TuringCompiler.extend_frame, Monodromy.Counter.TuringCompiler.frame, Monodromy.Counter.TuringCompiler.map_internal, Monodromy.Counter.TuringCompiler.popRegister, Monodromy.Counter.TuringCompiler.program, Monodromy.Counter.TuringCompiler.size, Monodromy.Counter.TuringCompiler.symbol, Monodromy.Counter.mapConfiguration, Monodromy.Counter.mapInstruction, Monodromy.Counter.step.
Statement elaboration dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.DivMod.consume, Monodromy.Counter.DivMod.residue, Monodromy.Counter.TuringCompiler.InternalReaches, Monodromy.Counter.TuringCompiler.Row, Monodromy.Counter.TuringCompiler.base, Monodromy.Counter.TuringCompiler.base_neZero, Monodromy.Counter.TuringCompiler.dispatch, Monodromy.Counter.TuringCompiler.divTarget, Monodromy.Counter.TuringCompiler.frame, Monodromy.Counter.TuringCompiler.popRegister, Monodromy.Counter.TuringCompiler.size, Monodromy.Counter.TuringCompiler.symbol.
Proof elaboration dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.DivMod.configuration, Monodromy.Counter.DivMod.consume, Monodromy.Counter.DivMod.finish, Monodromy.Counter.DivMod.program, Monodromy.Counter.DivMod.reaches_divmod, Monodromy.Counter.DivMod.residue, Monodromy.Counter.DivMod.size, Monodromy.Counter.Instruction, Monodromy.Counter.RegisterRelocation.embed, Monodromy.Counter.RegisterRelocation.pairIntoThree, Monodromy.Counter.RegisterRelocation.pairIntoThree_injective, Monodromy.Counter.RegisterRelocation.program, Monodromy.Counter.RegisterRelocation.reaches_embed, Monodromy.Counter.TuringCompiler.Boundary, Monodromy.Counter.TuringCompiler.InternalReaches, Monodromy.Counter.TuringCompiler.Row, Monodromy.Counter.TuringCompiler.base, Monodromy.Counter.TuringCompiler.base_neZero, Monodromy.Counter.TuringCompiler.dispatch, Monodromy.Counter.TuringCompiler.divTarget, Monodromy.Counter.TuringCompiler.divTarget_finish, Monodromy.Counter.TuringCompiler.div_live, Monodromy.Counter.TuringCompiler.extend_frame, Monodromy.Counter.TuringCompiler.frame, Monodromy.Counter.TuringCompiler.map_internal, Monodromy.Counter.TuringCompiler.popRegister, Monodromy.Counter.TuringCompiler.program, Monodromy.Counter.TuringCompiler.size, Monodromy.Counter.TuringCompiler.symbol, Monodromy.Counter.mapConfiguration, Monodromy.Counter.mapInstruction, Monodromy.Counter.step.
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.divide_reaches (machine : TM0.Machine (Fin a) (Fin q))
(row : Row a q) (target : Fin q) (direction : Dir)
(selected : machine row.1 row.2 = some (target, .move direction))
(value spectator : ℕ) :
InternalReaches a q machine
⟨divTarget a q row target (DivMod.consume (base a) 0),
frame (popRegister direction) value spectator⟩
⟨dispatch a q (target, symbol a (DivMod.residue (base a) value)),
frame (popRegister direction) (value / base a) spectator⟩ := by sorry
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
For positive , write and let be a partial Turing table on controls and symbols. Fix a row , a target , and a direction with , and set for a left move and for a right move. For every , the compiled three-counter table has a finite run from its division entry for row with registers to its dispatch cell for with registers ; here puts in register , in the other main register, and in scratch register , and when but . Control cells are distinct tags enumerated by the fixed equivalence with a finite ordinal. The division subtable has for and a bump cell: decrements register , going to if zero and otherwise to when or to bump; bump increments scratch and goes to ; decrements scratch, going at zero to and otherwise to ; increments register and returns to ; and is identified with dispatch . Every actual step counted in the asserted reflexive transitive closure starts outside all dispatch cells, though the final state may be a dispatch. There is no bound on the finite number of steps, and no assumption that is a valid tape code: , , and the otherwise unused residue are included.
Confirmed by the mission captain (proposal self-audit).