The Native Macro Matches Both Halted and Live Optional Source Steps
ProvedMonodromy.ReversibleNativeTuring.macroStep_iotaFor 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.
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]
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
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. Let be natural numbers, and let be any Post-Turing machine with alphabet and control set , both with default . A configuration consists of a control, a head symbol and two half-tapes modulo trailing blank zeros; either has no next instruction or changes control and writes a symbol or moves the head one cell. The base- code of a half-tape with nearest-to-head symbols is . The specified three-counter compiler has dispatch rows indexed by (control,head), encodes the two half-tape codes as , and uses multiplication, addition and division/remainder instruction blocks. Its ordinary two-counter compression has state , where is the compressed dispatch address of that row, and simulates the three counters using primes . Denote this two-counter instruction program by , its number of addresses by , and its configuration encoding by . The recording construction is an integer four-register edge table: its encoding of an original configuration and history has control at the recording dispatch of and register tuple . Its graph is formed from a radix block in base 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 . The marked recording vertices are precisely dispatches for addresses of that themselves are compressed dispatches of original (control,head) rows. The prime compression of uses the basis : it joins radix blocks for the selected outgoing action and the restoration sites, and retains halt vertices, using the specified port wiring. If denotes the resulting wired boundary address associated to the recording dispatch of , its encoding is ; natural conversion used before prime encoding sends every negative integer register to , 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 and take the least enabled indexed edge and have no successor when no edge is enabled. Applying the eleven-stage native compiler to gives its halting program ; its embedding is . The boundary program has the same native word table and stops at phase zero at the marked compressed boundary addresses. The native first-return relation from to requires both to satisfy this boundary condition, one step from to some , and a finite, possibly empty chain of steps from to , each with nonboundary source. The native macro step is the defined partial value none if the first step is absent; otherwise it runs from that first successor and wraps the returned boundary state in some, remaining undefined if this run never stops. The reverse program is the reverse staged table: inverse memory displacement, reverse cyclic phase motion, and the corresponding involutive port swaps; the reverse macro takes one advance and then partially evaluates that reverse table with the stop flags of . For every configuration of and every , there exists such that the native macro at is the defined partial value obtained by mapping the optional Turing successor through ; explicitly it is if has no successor at , and if that successor is . In addition, if the Turing successor is present then . Thus the macro is defined on every encoded pair, including halted configurations; no history increase is demanded in the absent-successor case.
Confirmed by the mission captain (proposal self-audit).