A Turing move multiplication macro preserves the spectator
ProvedMonodromy.Counter.TuringCompiler.multiply_reachesLet a,q be positive, M a TM0 machine over Fin a and Fin q, and row=(σ,h) a source state/head pair for which M selects a move in direction d to state t. For all natural values v,w, its three-counter table has an internal run from the multiplication entry for row, with push register v, other tape register w and scratch 0, to the addition entry for the old head h with push register (a+1)v, spectator w and scratch 0. Every departure state in this internal run is outside the source dispatch set.
Statement dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.TuringCompiler.InternalReaches, Monodromy.Counter.TuringCompiler.Row, Monodromy.Counter.TuringCompiler.add, Monodromy.Counter.TuringCompiler.base, Monodromy.Counter.TuringCompiler.frame, Monodromy.Counter.TuringCompiler.mulTarget, Monodromy.Counter.TuringCompiler.pushRegister, Monodromy.Counter.TuringCompiler.size.
Original proof dependencies: Monodromy.Counter.Configuration, 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.add, Monodromy.Counter.TuringCompiler.base, Monodromy.Counter.TuringCompiler.extend_frame, Monodromy.Counter.TuringCompiler.frame, Monodromy.Counter.TuringCompiler.map_internal, Monodromy.Counter.TuringCompiler.mulTarget, Monodromy.Counter.TuringCompiler.mulTarget_finish, Monodromy.Counter.TuringCompiler.mul_live, Monodromy.Counter.TuringCompiler.program, Monodromy.Counter.TuringCompiler.pushRegister, Monodromy.Counter.TuringCompiler.size, Monodromy.Counter.mapConfiguration, Monodromy.Counter.mapInstruction, Monodromy.Counter.step, Monodromy.CounterMultiplication.configuration, Monodromy.CounterMultiplication.finish, Monodromy.CounterMultiplication.program, Monodromy.CounterMultiplication.reaches_result.
Statement elaboration dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.TuringCompiler.InternalReaches, Monodromy.Counter.TuringCompiler.Row, Monodromy.Counter.TuringCompiler.add, Monodromy.Counter.TuringCompiler.base, Monodromy.Counter.TuringCompiler.frame, Monodromy.Counter.TuringCompiler.mulTarget, Monodromy.Counter.TuringCompiler.pushRegister, Monodromy.Counter.TuringCompiler.size.
Proof elaboration dependencies: Monodromy.Counter.Configuration, 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.add, Monodromy.Counter.TuringCompiler.base, Monodromy.Counter.TuringCompiler.extend_frame, Monodromy.Counter.TuringCompiler.frame, Monodromy.Counter.TuringCompiler.map_internal, Monodromy.Counter.TuringCompiler.mulTarget, Monodromy.Counter.TuringCompiler.mulTarget_finish, Monodromy.Counter.TuringCompiler.mul_live, Monodromy.Counter.TuringCompiler.program, Monodromy.Counter.TuringCompiler.pushRegister, Monodromy.Counter.TuringCompiler.size, Monodromy.Counter.mapConfiguration, Monodromy.Counter.mapInstruction, Monodromy.Counter.step, Monodromy.CounterMultiplication.configuration, Monodromy.CounterMultiplication.finish, Monodromy.CounterMultiplication.program, Monodromy.CounterMultiplication.reaches_result.
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.multiply_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
⟨mulTarget a q row 0, frame (pushRegister direction) value spectator⟩
⟨add a q row row.2, frame (pushRegister direction) (base a * value) spectator⟩ := by sorry
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
For positive , put , let be a partial Turing table on controls and symbols, and fix a row , a target , and a direction such that . Let for a left move and for a right move, and write for the three registers with value at , spectator value at the other main register, and scratch value at register . For all natural numbers , the actual compiled counter table has a finite run from the multiplication cell tagged by and registers to the addition cell tagged by and registers . All transitions in the asserted reflexive transitive closure have nondispatch source controls; zero transitions are allowed by the relation itself and no uniform bound is asserted. In this multiplication region, cell decrements register , branching at zero to cell and otherwise to cell ; a cell increments scratch and goes to ; cell decrements scratch, branching at zero to the addition cell and otherwise to cell ; and cell increments register and returns to . The tags are carried into a finite ordinal by the fixed finite enumeration of rows and phases. This includes , , and arbitrary spectator or active values that are not tape encodings.
Confirmed by the mission captain (proposal self-audit).