A closed path can return to its base point while its analytic continuation reaches a different branch. The question is whether this change of branch can participate in the execution of a complete computational model: storing unbounded information, making conditional changes, and determining which operation follows.
The subject is a specific construction from covering spaces and successive path lifting. Analytic universal computation is already established in work such as Koiran and Moore (1999), and reversible two-counter universality is classical Morita (1996). The contribution studied here is the precise geometric execution mechanism and its formally checked connection to these computational structures.
Let and . The state space is the fiber over of the projection
The projection is organized as a tower of two explicitly constructed covering maps. A state consists of three retained roots. At the base fiber it has a unique integer description , with and .
A driver is a triple of based paths. Execution first lifts its two lower paths. Their actual lifted values, multiplied by the third base path, generate the input to the upper lift. The returned roots constitute the next state.
Five fixed based loops produce two memory shifts, two conditional control shifts, and an unconditional control shift. In integer descriptions the conditional operation on coordinate adds one to exactly when . Signed finite words compose these operations. A program stores a finite table of such words and stopping bits. Analytic observation of a finite power-cover root selects a whole word; observation is repeated at designated completed-word returns.
The goal is the exact existing declaration Monodromy.ReversibleNativeTuring.native_universality. Let be any Post–Turing machine with finite nonempty alphabet and finite nonempty control. Its complete configurations are denoted by . The construction supplies a native program , an inverse word table , and an encoding retaining a natural-number history .
For every defined source step , the theorem establishes one common such that
Here the two macros execute their own fixed native tables to the next internal root mark. The declaration also asserts injectivity of the entire pair , mutual inverse advances on the whole state fiber, the source-halt case, equivalence of complete final configurations, halting and divergence, and actual matching lower and upper lifts for every finite source execution. The formal statement retains all eight clauses.
Companion targets are the existing fixed-interface characterization Structure.continuation_characterization, the strict conditional-gate separation Structure.conditional_gates_strictly_extend, and the analytic execution comparison Structure.analytic_computes_iff. The characterization concerns the complete finite Program language. The reversible compiler is described by its configuration-and-history simulation theorem.
The local development already contains proofs of these results. Xiaoyang Liu directed the research, with substantial assistance from OpenAI Codex and collaborating agents, as recorded in the source contribution statement. The task is to preserve those definitions, statements and proofs as a dependency-traceable import. All 89 independent solution files have been uploaded and accepted by the platform verifier, completing the imported proof graph.
The geometric construction accounts for conditional winding through actual transport. Finite analytic routing supplies program-dependent selection, and classical machine encodings supply the static compilation. These roles remain explicit. A direct analytic comparator realizes the same exact integer-lattice executions, providing a concrete comparison of computational capability and execution mechanism.
A geometric representation of an already computed successor would leave the execution mechanism unexplained. The required result instead concerns the model's actual path-generating definitions. Reversible compression must preserve both forward determinism and the corresponding incoming-edge condition. A positive simulation trace alone also leaves open whether one source step reaches the first marked return; that boundary property is a separate part of the verified chain.
Complete configurations and history matter because a source transition may discard information. The encoded history remains in the state and supports inverse execution. Temporary arithmetic workspace returns to zero at the prescribed source boundaries.
The authoritative source is the complete local working-tree snapshot of the Monodromy repository, not the incomplete remote tree. Its snapshot SHA-256 is e03ce2d08e07ee663140bec213fb21e995f44153a3c556c908fcf1c8d6fefe6c. Every uploaded item records its original declaration, file, exact source range, and file hash. Declaration and reference locations come from the official Lean extraction tools; the dependency graph retains statement and proof dependencies separately.
The original source uses Lean 4.35.0 and Mathlib 56a005855ea17e0b0958f73ec801ae140b0a1679; its complete build and strict 2661-declaration axiom audit pass. The import targets Lean 4.33.1 and Mathlib 0df444a360eaa60ab8c11dca51a86af692955474. All 17 definition bundles, 89 theorem statements, and 89 independent solution files build locally in that environment. Lean has checked 178 complete-proposition equalities: each imported statement type and each solution type equals its counterpart exported from the complete ported source project. The conversion records seven proved upstream library lemmas and two proof-tactic adaptations occurring in four copied helper proofs. Original definitions and theorem conditions are preserved, with exact source and transformation records. The 106 uploaded items also carry independent code-based read-backs. The mission is public and reviewed; all 89 submitted solutions have received ACCEPTED verdicts from the server-side Lean verifier.
The semantics uses exact branch states and discrete completed-word returns. Autonomous continuous event detection, finite-precision hardware and resource advantages are separate questions. The stored proof sources match the locally validated solution files byte for byte.
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
For 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.
No open leaves. Every sub-goal is proved or awaiting decomposition.