A native counter simulation departs before its next marked return
ProvedMonodromy.ReversibleCompilation.counter_departureFor positive q and arbitrary e, let T be a two-integer-counter table with complementary same-register tests at shared sources and targets, and choose any Boolean marking of its source vertices. For every successful T step s→t, there is a native state u reached by one successful step of the compiled halting program from the eleven-phase encoding of s, followed by a finite possibly empty chain of that same program’s successful steps to the encoding of t whose departure states are unmarked by the native finite-root observation. There is no hypothesis that either endpoint is marked, and the source registers may be arbitrary integers.
Statement dependencies: Monodromy.Counter.Reversible.Deterministic, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.Table, Monodromy.Counter.Reversible.TargetCompatible, Monodromy.Counter.Reversible.step, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program.step, Monodromy.ReversibleCompilation.NativeInternalReaches, Monodromy.ReversibleCompilation.haltingProgram, Monodromy.ReversibleCompilation.instNeZeroNatHAdd_monodromy, Monodromy.ReversibleCompilation.iota.
Original proof dependencies: Monodromy.Counter.Reversible.Action.enabled, Monodromy.Counter.Reversible.Deterministic, Monodromy.Counter.Reversible.Edge, Monodromy.Counter.Reversible.Edge.enabled, Monodromy.Counter.Reversible.Edge.execute, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.StepRel, Monodromy.Counter.Reversible.Table, Monodromy.Counter.Reversible.TargetCompatible, Monodromy.Counter.Reversible.step, Monodromy.Counter.Reversible.step_iff, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program, Monodromy.CoupledContinuation.Program.advance, Monodromy.CoupledContinuation.Program.haltSignal, Monodromy.CoupledContinuation.Program.step, Monodromy.ReversibleCompilation.MarkedBoundary, Monodromy.ReversibleCompilation.NativeInternalReaches, Monodromy.ReversibleCompilation.NativeInternalStep, Monodromy.ReversibleCompilation.haltMark, Monodromy.ReversibleCompilation.haltSignal_iota_iff, Monodromy.ReversibleCompilation.haltingProgram, Monodromy.ReversibleCompilation.instNeZeroNatHAdd_monodromy, Monodromy.ReversibleCompilation.iota, Monodromy.ReversibleCompilation.markedBoundary_phase, Monodromy.ReversibleCompilation.stages, Monodromy.ReversibleCompilation.step_firstReturn, Monodromy.ReversibleCompilation.stopped_phase, Monodromy.StagedProgram.PhaseBoundary.
Statement elaboration dependencies: Monodromy.Counter.Reversible.Deterministic, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.Table, Monodromy.Counter.Reversible.TargetCompatible, Monodromy.Counter.Reversible.step, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program.step, Monodromy.ReversibleCompilation.NativeInternalReaches, Monodromy.ReversibleCompilation.haltingProgram, Monodromy.ReversibleCompilation.instNeZeroNatHAdd_monodromy, Monodromy.ReversibleCompilation.iota.
Proof elaboration dependencies: Monodromy.Counter.Reversible.Action.enabled, Monodromy.Counter.Reversible.Deterministic, Monodromy.Counter.Reversible.Edge, Monodromy.Counter.Reversible.Edge.enabled, Monodromy.Counter.Reversible.Edge.execute, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.StepRel, Monodromy.Counter.Reversible.Table, Monodromy.Counter.Reversible.TargetCompatible, Monodromy.Counter.Reversible.step, Monodromy.Counter.Reversible.step_iff, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program, Monodromy.CoupledContinuation.Program.advance, Monodromy.CoupledContinuation.Program.haltSignal, Monodromy.CoupledContinuation.Program.step, Monodromy.ReversibleCompilation.MarkedBoundary, Monodromy.ReversibleCompilation.NativeInternalReaches, Monodromy.ReversibleCompilation.NativeInternalStep, Monodromy.ReversibleCompilation.haltMark, Monodromy.ReversibleCompilation.haltSignal_iota_iff, Monodromy.ReversibleCompilation.haltingProgram, Monodromy.ReversibleCompilation.instNeZeroNatHAdd_monodromy, Monodromy.ReversibleCompilation.iota, Monodromy.ReversibleCompilation.markedBoundary_phase, Monodromy.ReversibleCompilation.stages, Monodromy.ReversibleCompilation.step_firstReturn, Monodromy.ReversibleCompilation.stopped_phase, Monodromy.StagedProgram.PhaseBoundary.
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.ReversibleCompilation
open Counter.Reversible CoupledContinuation
variable {q e : ℕ} [NeZero q]
theorem Monodromy.ReversibleCompilation.counter_departure (table : Table 2 q e) (deterministic : Deterministic table)
(compatible : TargetCompatible table) (mark : Fin q → Bool) {first last : State 2 q}
(transition : Counter.Reversible.step table first = some last) :
∃ next, (haltingProgram table deterministic compatible).step (iota (e := e) first) = some next ∧
NativeInternalReaches table deterministic compatible mark next (iota (e := e) last) := by sorry
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
Write . The memory space consists of triples of complex numbers with , , and ; its integer-labelled point is , using the principal complex logarithm. A degree- native program, for , assigns a finite word and a Boolean stop flag to each . Its letters are left shift, right shift, left zero probe, right zero probe, and control shift, each with a reversal flag. Their geometric drivers respectively use the left or right base loop or , or the control loop , leaving other components constant; a reversal reverses these paths. From a memory, lower exponential path lifts start at , and an upper exponential lift starts at over the product of those lower lifts and the control path; the endpoint is the new memory. A word concatenates these drivers in list order, with the empty word idle. Selection uses : the values at roots are selected by , where is the divided slope of at , divided by its derivative at , with the divided slope equal to the derivative when . The same selector applied to the stop flags is the halt signal; a program step is absent exactly when that signal equals , and otherwise is its routed advance. Its partial evaluation returns the final state whose step is absent, and is undefined if no such state is reached. For natural numbers and , a reversible two-register table has control vertices, indexed edges, integer registers, and edge actions either adding any integer to one register or testing that a register is zero or nonzero without changing it. A test is enabled exactly according to its Boolean zero flag; a shift is always enabled. An edge is enabled when its source is the current vertex and its action is enabled; the counter step executes the least indexed enabled edge, returning no successor if there is none. Determinism means that distinct edges sharing a source have test actions on the same register with opposite flags; target compatibility imposes the same condition on distinct edges sharing a target. The native compiler has degree and eleven stages: five guarded source-to-edge-port swaps in the order unconditional, left-zero, left-nonzero, right-zero, right-nonzero; the edge's register displacement at its port; and the five guarded target-to-port swaps in reverse order. These swaps use finite control-root routing and the zero/control words of the native language. Staging multiplies an integer control label by and adds its phase, advances phases cyclically, and scales every control/probe letter elevenfold while leaving memory-shift letters unchanged. Its halting version stops only at phase zero at a source vertex with no outgoing edge; its state embedding is . A separate marking program has the same stages and stops only at phase zero at source vertices marked true by a supplied Boolean map; call this condition . For every table with the stated determinism and target compatibility, every Boolean mark on its vertices, and any first and last counter states such that the optional counter step at equals , there exists a native memory such that and there is a finite, possibly empty chain from to of steps, with every source in this latter chain failing . There is no requirement that or themselves satisfy , and the chain after the initial departure may have length zero. The number is allowed to be zero, in which case the successful-counter-step premise has no instances.
Confirmed by the mission captain (proposal self-audit).