One counter transition becomes two native steps
ProvedMonodromy.CounterContinuation.two_returnsFor every positive m and every two-counter program with m addresses, a successful source step from configuration s to t has a native intermediate state u such that the compiled program takes one successful optional step from encode(s) to u and one from u to encode(t). The same u witnesses both step equalities.
Statement dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.Program, Monodromy.Counter.step, Monodromy.CounterContinuation.compile, Monodromy.CounterContinuation.encode, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program.step.
Original proof dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.Instruction, Monodromy.Counter.Program, Monodromy.Counter.step, Monodromy.CounterContinuation.advance_dec_first, Monodromy.CounterContinuation.advance_dec_positive, Monodromy.CounterContinuation.advance_dec_zero, Monodromy.CounterContinuation.advance_inc_first, Monodromy.CounterContinuation.advance_inc_second, Monodromy.CounterContinuation.compile, Monodromy.CounterContinuation.encode, Monodromy.CounterContinuation.instructionStop, Monodromy.CounterContinuation.label, Monodromy.CounterContinuation.label_eq, Monodromy.CounterContinuation.step_phase_one, Monodromy.CounterContinuation.step_phase_two, Monodromy.CounterContinuation.step_running_at, Monodromy.CounterContinuation.stopping, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program.advance, Monodromy.CoupledContinuation.Program.step, Monodromy.CoupledContinuation.prepare.
Statement elaboration dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.Program, Monodromy.Counter.step, Monodromy.CounterContinuation.compile, Monodromy.CounterContinuation.encode, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program.step.
Proof elaboration dependencies: Monodromy.Counter.Configuration, Monodromy.Counter.Instruction, Monodromy.Counter.Program, Monodromy.Counter.step, Monodromy.CounterContinuation.advance_dec_first, Monodromy.CounterContinuation.advance_dec_positive, Monodromy.CounterContinuation.advance_dec_zero, Monodromy.CounterContinuation.advance_inc_first, Monodromy.CounterContinuation.advance_inc_second, Monodromy.CounterContinuation.compile, Monodromy.CounterContinuation.encode, Monodromy.CounterContinuation.instructionStop, Monodromy.CounterContinuation.label, Monodromy.CounterContinuation.label_eq, Monodromy.CounterContinuation.step_phase_one, Monodromy.CounterContinuation.step_phase_two, Monodromy.CounterContinuation.step_running_at, Monodromy.CounterContinuation.stopping, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program.advance, Monodromy.CoupledContinuation.Program.step, Monodromy.CoupledContinuation.prepare.
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.CounterContinuation
open CoupledContinuation
variable {m : ℕ}
variable [NeZero m]
theorem Monodromy.CounterContinuation.two_returns (program : Counter.Program 2 m)
(state result : Counter.Configuration 2 m) (source_step : Counter.step program state = some result) :
∃ middle : Memory,
(compile program).step (encode state) = some middle ∧
(compile program).step middle = some (encode result) := by sorry
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
For every positive natural number , any -label natural two-counter program , and configurations for which one counter step of from returns , there exists a geometric memory point such that one step of the compiled -entry geometric program sends to and one further step sends to . For , is in the fiber over of the coupled exponential projection . The compiler uses control phases : its first word advances control, using the appropriate zero-conditional loop for a decrement, and its next selected word updates the register and/or jumps to the appropriate target phase zero; stopping is marked at halting source labels in phase zero. A compiled step performs the word selected by the finite control-root kernels unless its stopping signal is , when it has no successor. The witness is required to make both successors exist, with no distinctness conditions on the three states, no uniqueness claim for the witness, no explicit boundary predicate in the conclusion, and no later termination assumption.
Confirmed by the mission captain (proposal self-audit).