Agreement on live instructions preserves a renamed step
ProvedMonodromy.Counter.step_map_liveFor arbitrary natural register and control counts n,m,k, let a map the m old control addresses into k new addresses; a need not be injective. Suppose two n-counter programs agree, after renaming every destination by a, on each old instruction that is not halt. Every successful old step s→t then becomes a successful new step from the configuration with control a(s.pc) and unchanged counters to the similarly renamed t. No agreement is required at old halt addresses.
Statement dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.Instruction, Monodromy.Counter.Program, Monodromy.Counter.mapConfiguration, Monodromy.Counter.mapInstruction, Monodromy.Counter.step.
Original proof dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.Instruction, Monodromy.Counter.Program, Monodromy.Counter.mapConfiguration, Monodromy.Counter.mapInstruction, Monodromy.Counter.step.
Statement elaboration dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.Instruction, Monodromy.Counter.Program, Monodromy.Counter.mapConfiguration, Monodromy.Counter.mapInstruction, Monodromy.Counter.step.
Proof elaboration dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.Instruction, Monodromy.Counter.Program, 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
variable {n m k : ℕ}
theorem Monodromy.Counter.step_map_live (address : Fin m → Fin k)
(oldProgram : Program n m) (newProgram : Program n k)
(agrees : ∀ label, oldProgram label ≠ .halt →
newProgram (address label) = mapInstruction address (oldProgram label))
{state result : Configuration n m} (running : step oldProgram state = some result) :
step newProgram (mapConfiguration address state) = some (mapConfiguration address result) := by sorry
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
For all natural numbers , let be an -label program on natural-number counters, let be a -label program on the same counters, and let be any function, with no injectivity assumption. An instruction either increments a specified register and jumps, branches on a specified register being zero and otherwise decrements it before jumping, or halts; an increment always has a successor, a zero decrement leaves all counters unchanged, a positive decrement reduces that counter by one, and halt has no successor. Suppose that for every label at which is not halt, is the instruction obtained from by applying to each target label and retaining the register and instruction kind. For arbitrary source configurations , if one -step returns from , then one -step from returns . No condition is imposed on at images of halting labels beyond any constraints inherited from other live preimages. Zero sizes are allowed; leaves no source configurations, and a successful transition cannot exist for a zero-register program, whose only available instruction is halt.
Confirmed by the mission captain (proposal self-audit).