Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

The Native Macro Matches Both Halted and Live Optional Source Steps

Proved
Monodromy.ReversibleNativeTuring.macroStep_iota

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

computabilitycovering-spacesmonodromy-computation

For positive naturals a,q, every Turing machine m over Fin a and Fin q, complete configuration x and natural history h, there exists a natural h′ such that the native macro at I(x,h) equals the defined partial optional source step with each successful successor y replaced by I(y,h′). If the source step is present then h<h′. In the halted case the value is defined none, and the statement imposes no condition on h′, including no equality h′=h.

Statement dependencies: Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.ReversibleNativeTuring.iota, Monodromy.ReversibleNativeTuring.macroStep.

Original proof dependencies: Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.ReversibleCompilation.nativeMacro_of_halt, Monodromy.ReversibleNativeTuring.FirstReturn, Monodromy.ReversibleNativeTuring.iota, Monodromy.ReversibleNativeTuring.macroStep, Monodromy.ReversibleNativeTuring.reverseMacro, Monodromy.ReversibleNativeTuring.size_nonzero, Monodromy.ReversibleNativeTuring.step_halt, Monodromy.ReversibleNativeTuring.step_return_pair, Monodromy.ReversibleTuring.Compression.deterministic, Monodromy.ReversibleTuring.Compression.edges, Monodromy.ReversibleTuring.Compression.mark, Monodromy.ReversibleTuring.Compression.size, Monodromy.ReversibleTuring.Compression.table, Monodromy.ReversibleTuring.Compression.targetCompatible.

Statement elaboration dependencies: Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.ReversibleNativeTuring.iota, Monodromy.ReversibleNativeTuring.macroStep.

Proof elaboration dependencies: Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.ReversibleCompilation.nativeMacro_of_halt, Monodromy.ReversibleNativeTuring.FirstReturn, Monodromy.ReversibleNativeTuring.iota, Monodromy.ReversibleNativeTuring.macroStep, Monodromy.ReversibleNativeTuring.reverseMacro, Monodromy.ReversibleNativeTuring.size_nonzero, Monodromy.ReversibleNativeTuring.step_halt, Monodromy.ReversibleNativeTuring.step_return_pair, Monodromy.ReversibleTuring.Compression.deterministic, Monodromy.ReversibleTuring.Compression.edges, Monodromy.ReversibleTuring.Compression.mark, Monodromy.ReversibleTuring.Compression.size, Monodromy.ReversibleTuring.Compression.table, Monodromy.ReversibleTuring.Compression.targetCompatible.

Preamble
module
public import Definitions.Def_Monodromy_FormalCompilation
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.Computability.TuringMachine.ToPartrec
public import Mathlib.Data.Fin.Basic
public import Mathlib.Data.Fintype.Card
public import Mathlib.Data.Fintype.EquivFin
public import Mathlib.Data.Fintype.Sets
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.ReversibleNativeTuring
open Turing CoupledContinuation ReversibleTuring
variable (a q : ℕ) [NeZero a] [NeZero q]

Formal statement
theorem Monodromy.ReversibleNativeTuring.macroStep_iota (machine : TM0.Machine (Fin a) (Fin q))
    (state : TM0.Cfg (Fin a) (Fin q)) (history : ℕ) :
    ∃ finalHistory,
      Monodromy.ReversibleNativeTuring.macroStep a q machine (iota a q machine state history) =
        Part.some ((TM0.step machine state).map (fun next => iota a q machine next finalHistory)) ∧
      (TM0.step machine state ≠ none → history < finalHistory) := 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/FormalCompilation.lean (file SHA-256 c07335814044367fc4605d1e494fe82a30c684f754d58d55aaa7514b94c37122): Monodromy.ReversibleNativeTuring.macroStep_iota at L1557-L1574 [UTF-8 83810:84915].
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. Let a,q>0a,q>0a,q>0 be natural numbers, and let MMM be any Post-Turing machine with alphabet {0,…,a−1}\{0,\ldots,a-1\}{0,…,a−1} and control set {0,…,q−1}\{0,\ldots,q-1\}{0,…,q−1}, both with default 000. A configuration consists of a control, a head symbol and two half-tapes modulo trailing blank zeros; MMM either has no next instruction or changes control and writes a symbol or moves the head one cell. The base-(a+1)(a+1)(a+1) code of a half-tape with nearest-to-head symbols b0,b1,…b_0,b_1,\ldotsb0​,b1​,… is ∑ibi(a+1)i\sum_i b_i(a+1)^i∑i​bi​(a+1)i. The specified three-counter compiler has dispatch rows indexed by (control,head), encodes the two half-tape codes as (L,R,0)(L,R,0)(L,R,0), and uses multiplication, addition and division/remainder instruction blocks. Its ordinary two-counter compression has state (p,(2L3R,0))(p,(2^L3^R,0))(p,(2L3R,0)), where ppp is the compressed dispatch address of that row, and simulates the three counters using primes 2,3,52,3,52,3,5. Denote this two-counter instruction program by CMC_MCM​, its number of addresses by mmm, and its configuration encoding by EME_MEM​. The recording construction TMT_MTM​ is an integer four-register edge table: its encoding of an original configuration sss and history h∈Nh\in\mathbb Nh∈N has control at the recording dispatch of EM(s)E_M(s)EM​(s) and register tuple (EM(s)0,EM(s)1,h,0)(E_M(s)_0,E_M(s)_1,h,0)(EM​(s)0​,EM​(s)1​,h,0). Its graph is formed from a radix block in base 2m+12m+12m+1 at every source address plus the edges for that address's increment or zero/decrement branches; the old address and branch are represented by the nonzero digit 2p+b+12p+b+12p+b+1. The marked recording vertices are precisely dispatches for addresses of CMC_MCM​ that themselves are compressed dispatches of original (control,head) rows. The prime compression UMU_MUM​ of TMT_MTM​ uses the basis (2,3,5,7)(2,3,5,7)(2,3,5,7): it joins radix blocks for the selected outgoing action and the restoration sites, and retains halt vertices, using the specified port wiring. If bM(s)b_M(s)bM​(s) denotes the resulting wired boundary address associated to the recording dispatch of EM(s)E_M(s)EM​(s), its encoding is FM(s,h)=(bM(s),(2EM(s)03EM(s)15h,0))F_M(s,h)=(b_M(s),(2^{E_M(s)_0}3^{E_M(s)_1}5^h,0))FM​(s,h)=(bM​(s),(2EM​(s)0​3EM​(s)1​5h,0)); natural conversion used before prime encoding sends every negative integer register to 000, although the displayed encoded registers are nonnegative. A compressed state is marked when its control is a wired boundary address of a marked recording dispatch, independently of its integer registers. Both TMT_MTM​ and UMU_MUM​ take the least enabled indexed edge and have no successor when no edge is enabled. Applying the eleven-stage native compiler to UMU_MUM​ gives its halting program PMP_MPM​; its embedding is IM(s,h)=Φ(2EM(s)03EM(s)15h,0,11bM(s))I_M(s,h)=\Phi(2^{E_M(s)_0}3^{E_M(s)_1}5^h,0,11b_M(s))IM​(s,h)=Φ(2EM​(s)0​3EM​(s)1​5h,0,11bM​(s)). The boundary program QMQ_MQM​ has the same native word table and stops at phase zero at the marked compressed boundary addresses. The native first-return relation from xxx to yyy requires both x,yx,yx,y to satisfy this boundary condition, one PMP_MPM​ step from xxx to some uuu, and a finite, possibly empty chain of PMP_MPM​ steps from uuu to yyy, each with nonboundary source. The native macro step is the defined partial value none if the first PMP_MPM​ step is absent; otherwise it runs QMQ_MQM​ from that first successor and wraps the returned boundary state in some, remaining undefined if this run never stops. The reverse program RMR_MRM​ is the reverse staged table: inverse memory displacement, reverse cyclic phase motion, and the corresponding involutive port swaps; the reverse macro takes one RMR_MRM​ advance and then partially evaluates that reverse table with the stop flags of QMQ_MQM​. For every configuration sss of MMM and every h∈Nh\in\mathbb Nh∈N, there exists h′∈Nh'\in\mathbb Nh′∈N such that the native macro at IM(s,h)I_M(s,h)IM​(s,h) is the defined partial value obtained by mapping the optional Turing successor through t↦IM(t,h′)t\mapsto I_M(t,h')t↦IM​(t,h′); explicitly it is Part.some(none)\mathrm{Part.some}(\mathrm{none})Part.some(none) if MMM has no successor at sss, and Part.some(some(IM(t,h′)))\mathrm{Part.some}(\mathrm{some}(I_M(t,h')))Part.some(some(IM​(t,h′))) if that successor is ttt. In addition, if the Turing successor is present then h<h′h<h'h<h′. Thus the macro is defined on every encoded pair, including halted configurations; no history increase is demanded in the absent-successor case.

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