Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A native counter simulation departs before its next marked return

Proved
Monodromy.ReversibleCompilation.counter_departure

by Xiaoyang Liu · Nov 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

computabilitycovering-spacesmonodromy-computation

For 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.

Preamble
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]

Formal statement
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
Source
Authoritative local working-tree snapshot SHA-256 e03ce2d08e07ee663140bec213fb21e995f44153a3c556c908fcf1c8d6fefe6c; repository https://github.com/ERHUTUZI123/monodromy. The remote Git base is incomplete and is not asserted to contain these declarations. src/Monodromy/Counter.lean (file SHA-256 40536289575067aae1ed4154805e219805a1c786ccfdfcbe632ea7478a40636a): Monodromy.ReversibleCompilation.counter_departure at L8517-L8557 [UTF-8 445957:448375].
Read-back

What the Lean code literally says, in plain math · OpenAI Codex (independent agent)

Write τ=2πi\tau=2\pi iτ=2πi. The memory space M\mathcal MM consists of triples (zL,zR,w)(z_L,z_R,w)(zL​,zR​,w) of complex numbers with zL,zR≠0z_L,z_R\ne0zL​,zR​=0, ezL=ezR=ee^{z_L}=e^{z_R}=eezL​=ezR​=e, and ew=zLzRe^w=z_Lz_Rew=zL​zR​; its integer-labelled point Φ(l,r,c)\Phi(l,r,c)Φ(l,r,c) is (1+τl,1+τr,log⁡(1+τl)+log⁡(1+τr)+τc)(1+\tau l,1+\tau r,\log(1+\tau l)+\log(1+\tau r)+\tau c)(1+τl,1+τr,log(1+τl)+log(1+τr)+τc), using the principal complex logarithm. A degree-ddd native program, for d>0d>0d>0, assigns a finite word and a Boolean stop flag to each j∈{0,…,d−1}j\in\{0,\ldots,d-1\}j∈{0,…,d−1}. 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 t↦e1+2πitt\mapsto e^{1+2\pi it}t↦e1+2πit or t↦exp⁡(e2πit)t\mapsto\exp(e^{2\pi it})t↦exp(e2πit), or the control loop t↦e2πitt\mapsto e^{2\pi it}t↦e2πit, leaving other components constant; a reversal reverses these paths. From a memory, lower exponential path lifts start at zL,zRz_L,z_RzL​,zR​, and an upper exponential lift starts at www 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 rd=exp⁡((w−log⁡zL−log⁡zR)/d)r_d=\exp((w-\log z_L-\log z_R)/d)rd​=exp((w−logzL​−logzR​)/d): the values at roots ωj=e2πij/d\omega_j=e^{2\pi ij/d}ωj​=e2πij/d are selected by ∑jKd(ωj,rd)vj\sum_j K_d(\omega_j,r_d)v_j∑j​Kd​(ωj​,rd​)vj​, where Kd(r,z)K_d(r,z)Kd​(r,z) is the divided slope of z↦zdz\mapsto z^dz↦zd at (r,z)(r,z)(r,z), divided by its derivative at rrr, with the divided slope equal to the derivative when z=rz=rz=r. The same selector applied to the 0/10/10/1 stop flags is the halt signal; a program step is absent exactly when that signal equals 111, 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 q>0q>0q>0 and e≥0e\ge0e≥0, a reversible two-register table has qqq control vertices, eee 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 D=11(q+e)D=11(q+e)D=11(q+e) 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 111111 and adds its phase, advances phases cyclically, and scales every control/probe letter elevenfold while leaving memory-shift letters unchanged. Its halting version PPP stops only at phase zero at a source vertex with no outgoing edge; its state embedding is J(p,v)=Φ(v0,v1,11p)J(p,v)=\Phi(v_0,v_1,11p)J(p,v)=Φ(v0​,v1​,11p). 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 BBB. For every table with the stated determinism and target compatibility, every Boolean mark on its qqq vertices, and any first and last counter states s,t∈{0,…,q−1}×Z2s,t\in\{0,\ldots,q-1\}\times\mathbb Z^2s,t∈{0,…,q−1}×Z2 such that the optional counter step at sss equals some(t)\mathrm{some}(t)some(t), there exists a native memory uuu such that P.step(J(s))=some(u)P.\mathrm{step}(J(s))=\mathrm{some}(u)P.step(J(s))=some(u) and there is a finite, possibly empty chain from uuu to J(t)J(t)J(t) of PPP steps, with every source in this latter chain failing BBB. There is no requirement that J(s)J(s)J(s) or J(t)J(t)J(t) themselves satisfy BBB, and the chain after the initial departure may have length zero. The number eee is allowed to be zero, in which case the successful-counter-step premise has no instances.

Human review
  • Endorsed by marwahaha · Nov 6, 2026

  • Endorsed by Xiaoyang Liu · Nov 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me