Complete Reversible Native Turing Universality with Actual Cover Lifts
ProvedMonodromy.ReversibleNativeTuring.native_universalityFor positive naturals a,q and every Turing machine m over Fin a and Fin q, let P,R,I be its specified forward program, reverse program and complete configuration-history encoding. All eight conclusions hold: (1) I is injective on pairs (configuration,natural history); (2) P.advance and R.advance are mutual inverses on the entire coupled fiber; (3) each successful source step x→y and each h admit one h′>h giving the specified positive native first return, forward macro value some I(y,h′), and reverse macro value I(x,h); (4) each source halt gives the defined forward macro value none; (5) for every x,y,h, existence of h′ with native terminal result I(y,h′) from I(x,h) is equivalent to source terminal result y from x; (6) native and source evaluation are defined for exactly the same encoded initial configurations; (7) they are undefined for exactly the same such configurations; and (8) every finite source run, including a zero-length or nonhalting prefix, has some final history and native advance count whose generated intermediate curve and trajectory are literally the matching lower and upper covering lifts and whose endpoint is the complete restricted encoded successor. The inverse claim concerns these compiled programs, and no growth or positive-count requirement is added to clause (8).
Statement dependencies: Monodromy.CoupledContinuation.Driver, Monodromy.CoupledContinuation.Driver.restrictedPath, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program, Monodromy.CoupledContinuation.Program.advance, Monodromy.CoupledContinuation.Program.eval, Monodromy.CoupledContinuation.Program.runDriver, Monodromy.CoupledContinuation.intermediateCurve, Monodromy.CoupledContinuation.intermediatePath, Monodromy.CoupledContinuation.restrictedBase, Monodromy.CoupledContinuation.restrictedState, Monodromy.CoupledContinuation.restrictedState_over_base, Monodromy.CoupledContinuation.restrictedTrajectory, Monodromy.CoupledPullback.Base, Monodromy.CoupledPullback.Lower, Monodromy.CoupledPullback.Point, Monodromy.CoupledPullback.Punctured, Monodromy.CoupledPullback.Root, Monodromy.CoupledPullback.lowerCovering, Monodromy.CoupledPullback.lowerProjection, Monodromy.CoupledPullback.upperCovering, Monodromy.CoupledPullback.upperProjection, Monodromy.NestedRestricted.baseSet, Monodromy.ReversibleCompilation.instNeZeroNatHAdd_monodromy, Monodromy.ReversibleNativeTuring.FirstReturn, Monodromy.ReversibleNativeTuring.iota, Monodromy.ReversibleNativeTuring.macroStep, Monodromy.ReversibleNativeTuring.program, Monodromy.ReversibleNativeTuring.reverseMacro, Monodromy.ReversibleNativeTuring.reverseProgram, Monodromy.ReversibleNativeTuring.size_nonzero, Monodromy.ReversibleTuring.Compression.edges, Monodromy.ReversibleTuring.Compression.size.
Original proof dependencies: Monodromy.CoupledContinuation.Driver, Monodromy.CoupledContinuation.Driver.restrictedPath, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program, Monodromy.CoupledContinuation.Program.advance, Monodromy.CoupledContinuation.Program.eval, Monodromy.CoupledContinuation.Program.runDriver, Monodromy.CoupledContinuation.intermediateCurve, Monodromy.CoupledContinuation.intermediatePath, Monodromy.CoupledContinuation.restrictedBase, Monodromy.CoupledContinuation.restrictedState, Monodromy.CoupledContinuation.restrictedState_over_base, Monodromy.CoupledContinuation.restrictedTrajectory, Monodromy.CoupledPullback.Base, Monodromy.CoupledPullback.Lower, Monodromy.CoupledPullback.Point, Monodromy.CoupledPullback.Punctured, Monodromy.CoupledPullback.Root, Monodromy.CoupledPullback.lowerCovering, Monodromy.CoupledPullback.lowerProjection, Monodromy.CoupledPullback.upperCovering, Monodromy.CoupledPullback.upperProjection, Monodromy.NestedRestricted.baseSet, Monodromy.ReversibleCompilation.instNeZeroNatHAdd_monodromy, Monodromy.ReversibleNativeTuring.FirstReturn, Monodromy.ReversibleNativeTuring.divergence_iff, Monodromy.ReversibleNativeTuring.finite_run_actual_lifts, Monodromy.ReversibleNativeTuring.forward_after_reverse, Monodromy.ReversibleNativeTuring.halting_iff, Monodromy.ReversibleNativeTuring.iota, Monodromy.ReversibleNativeTuring.iota_injective, Monodromy.ReversibleNativeTuring.macroStep, Monodromy.ReversibleNativeTuring.macroStep_iota, Monodromy.ReversibleNativeTuring.program, Monodromy.ReversibleNativeTuring.result_iff, Monodromy.ReversibleNativeTuring.reverseMacro, Monodromy.ReversibleNativeTuring.reverseProgram, Monodromy.ReversibleNativeTuring.reverse_after_forward, Monodromy.ReversibleNativeTuring.size_nonzero, Monodromy.ReversibleNativeTuring.step_return_pair, Monodromy.ReversibleTuring.Compression.edges, Monodromy.ReversibleTuring.Compression.size.
Statement elaboration dependencies: Monodromy.CoupledContinuation.Driver, Monodromy.CoupledContinuation.Driver.restrictedPath, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program, Monodromy.CoupledContinuation.Program.advance, Monodromy.CoupledContinuation.Program.eval, Monodromy.CoupledContinuation.Program.runDriver, Monodromy.CoupledContinuation.intermediateCurve, Monodromy.CoupledContinuation.intermediatePath, Monodromy.CoupledContinuation.restrictedBase, Monodromy.CoupledContinuation.restrictedState, Monodromy.CoupledContinuation.restrictedState_over_base, Monodromy.CoupledContinuation.restrictedTrajectory, Monodromy.CoupledPullback.Base, Monodromy.CoupledPullback.Lower, Monodromy.CoupledPullback.Point, Monodromy.CoupledPullback.Punctured, Monodromy.CoupledPullback.Root, Monodromy.CoupledPullback.lowerCovering, Monodromy.CoupledPullback.lowerProjection, Monodromy.CoupledPullback.upperCovering, Monodromy.CoupledPullback.upperProjection, Monodromy.NestedRestricted.baseSet, Monodromy.ReversibleCompilation.instNeZeroNatHAdd_monodromy, Monodromy.ReversibleNativeTuring.FirstReturn, Monodromy.ReversibleNativeTuring.iota, Monodromy.ReversibleNativeTuring.macroStep, Monodromy.ReversibleNativeTuring.program, Monodromy.ReversibleNativeTuring.reverseMacro, Monodromy.ReversibleNativeTuring.reverseProgram, Monodromy.ReversibleNativeTuring.size_nonzero, Monodromy.ReversibleTuring.Compression.edges, Monodromy.ReversibleTuring.Compression.size.
Proof elaboration dependencies: Monodromy.CoupledContinuation.Driver, Monodromy.CoupledContinuation.Driver.restrictedPath, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, Monodromy.CoupledContinuation.Program, Monodromy.CoupledContinuation.Program.advance, Monodromy.CoupledContinuation.Program.eval, Monodromy.CoupledContinuation.Program.runDriver, Monodromy.CoupledContinuation.intermediateCurve, Monodromy.CoupledContinuation.intermediatePath, Monodromy.CoupledContinuation.restrictedBase, Monodromy.CoupledContinuation.restrictedState, Monodromy.CoupledContinuation.restrictedState_over_base, Monodromy.CoupledContinuation.restrictedTrajectory, Monodromy.CoupledPullback.Base, Monodromy.CoupledPullback.Lower, Monodromy.CoupledPullback.Point, Monodromy.CoupledPullback.Punctured, Monodromy.CoupledPullback.Root, Monodromy.CoupledPullback.lowerCovering, Monodromy.CoupledPullback.lowerProjection, Monodromy.CoupledPullback.upperCovering, Monodromy.CoupledPullback.upperProjection, Monodromy.NestedRestricted.baseSet, Monodromy.ReversibleCompilation.instNeZeroNatHAdd_monodromy, Monodromy.ReversibleNativeTuring.FirstReturn, Monodromy.ReversibleNativeTuring.divergence_iff, Monodromy.ReversibleNativeTuring.finite_run_actual_lifts, Monodromy.ReversibleNativeTuring.forward_after_reverse, Monodromy.ReversibleNativeTuring.halting_iff, Monodromy.ReversibleNativeTuring.iota, Monodromy.ReversibleNativeTuring.iota_injective, Monodromy.ReversibleNativeTuring.macroStep, Monodromy.ReversibleNativeTuring.macroStep_iota, Monodromy.ReversibleNativeTuring.program, Monodromy.ReversibleNativeTuring.result_iff, Monodromy.ReversibleNativeTuring.reverseMacro, Monodromy.ReversibleNativeTuring.reverseProgram, Monodromy.ReversibleNativeTuring.reverse_after_forward, Monodromy.ReversibleNativeTuring.size_nonzero, Monodromy.ReversibleNativeTuring.step_return_pair, Monodromy.ReversibleTuring.Compression.edges, Monodromy.ReversibleTuring.Compression.size.
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.native_universality (machine : TM0.Machine (Fin a) (Fin q)) :
let P := program a q machine
let R := reverseProgram a q machine
let I := iota a q machine
Function.Injective (fun pair : TM0.Cfg (Fin a) (Fin q) × ℕ => I pair.1 pair.2) ∧
(∀ state, R.advance (P.advance state) = state ∧ P.advance (R.advance state) = state) ∧
(∀ first last, TM0.step machine first = some last → ∀ history,
∃ finalHistory, history < finalHistory ∧
FirstReturn a q machine (I first history) (I last finalHistory) ∧
macroStep a q machine (I first history) = Part.some (some (I last finalHistory)) ∧
reverseMacro a q machine (I last finalHistory) = Part.some (I first history)) ∧
(∀ state history, TM0.step machine state = none →
macroStep a q machine (I state history) = Part.some none) ∧
(∀ first last history,
(∃ finalHistory, I last finalHistory ∈ P.eval (I first history)) ↔
last ∈ StateTransition.eval (TM0.step machine) first) ∧
(∀ state history, (P.eval (I state history)).Dom ↔
(StateTransition.eval (TM0.step machine) state).Dom) ∧
(∀ state history, ¬ (P.eval (I state history)).Dom ↔
¬ (StateTransition.eval (TM0.step machine) state).Dom) ∧
(∀ first last history, StateTransition.Reaches (TM0.step machine) first last →
∃ finalHistory, ∃ count : ℕ,
let initial := I first history
let driver := P.runDriver count initial
intermediateCurve driver initial =
CoupledPullback.lowerCovering.liftPath driver.restrictedPath
(CoupledPullback.upperProjection (restrictedState initial))
(driver.restrictedPath.source.trans (restrictedState_over_base initial).symm) ∧
restrictedTrajectory driver initial =
CoupledPullback.upperCovering.liftPath (intermediatePath driver initial) (restrictedState initial)
(intermediatePath driver initial).source ∧
restrictedTrajectory driver initial 1 = restrictedState (I last 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 the lift notation, put , , , and . The lower covering is and the upper covering is . Restriction of a memory simply regards its lower coordinates as elements of . A driver's restricted path is its three component base loops regarded in , based at ; its intermediate curve consists of its two lower exponential lifts and its control path, and its restricted trajectory consists of those same lower lifts and its upper exponential lift. The intermediate path is that intermediate curve with the induced endpoints. All path lifts here are the actual continuous covering lifts at the specified initial point. For each such machine , all the following assertions hold simultaneously: the map is injective on all configurations paired with natural histories; for every , and ; whenever , for every natural there is a natural such that the native first-return relation holds from to , the forward macro is and the reverse macro at is ; whenever , the forward macro at every is ; for all , there exists for which 's complete partial evaluation from returns if and only if complete partial Turing evaluation from returns ; for every , native complete evaluation is defined if and only if Turing complete evaluation is defined, and native complete evaluation is undefined if and only if Turing complete evaluation is undefined; finally, for every finite, possibly zero-step Turing run from to and every , there exist natural such that the -advance routed driver from has its intermediate curve equal to the lower-covering lift of its restricted base path from , its restricted trajectory equal to the upper-covering lift of that intermediate path from the restricted , and endpoint the restricted . Complete evaluation returns only a state with absent successor, whereas the last finite-run clause does not require to be halted; is permitted there. The inverse assertions concern advance on every memory, even where the optional step would halt.
Confirmed by the mission captain (proposal self-audit).