Every Finite Turing Prefix Has the Two Actual Matching Cover Lifts
ProvedMonodromy.ReversibleNativeTuring.finite_run_actual_liftsFor positive naturals a,q, a Turing machine m over Fin a and Fin q, configurations x,y, natural history h and a finite possibly zero-length successful source run from x to y, there exist natural h′ and n such that the driver P.runDriver(n,I(x,h)) has its entire intermediate curve equal to the lower-covering lift from the upper projection of the restricted initial state, its entire restricted trajectory equal to the upper-covering lift of that intermediate path from the restricted initial state, and its endpoint equal to the restricted state I(y,h′). A halt, n>0, and h′>h are not required.
Statement dependencies: Monodromy.CoupledContinuation.Driver, Monodromy.CoupledContinuation.Driver.restrictedPath, Monodromy.CoupledContinuation.Memory, Monodromy.CoupledContinuation.Point, 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.iota, Monodromy.ReversibleNativeTuring.program, 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.runDriver, Monodromy.CoupledContinuation.Program.runDriver_of_reaches, Monodromy.CoupledContinuation.Program.step, Monodromy.CoupledContinuation.execute, Monodromy.CoupledContinuation.intermediateCurve, Monodromy.CoupledContinuation.intermediateCurve_actual_lift, Monodromy.CoupledContinuation.intermediatePath, Monodromy.CoupledContinuation.restrictedBase, Monodromy.CoupledContinuation.restrictedState, Monodromy.CoupledContinuation.restrictedState_over_base, Monodromy.CoupledContinuation.restrictedTrajectory, Monodromy.CoupledContinuation.restrictedTrajectory_actual_lift, Monodromy.CoupledContinuation.restrictedTrajectory_end, 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.Related, Monodromy.ReversibleNativeTuring.iota, Monodromy.ReversibleNativeTuring.program, Monodromy.ReversibleNativeTuring.respects, Monodromy.ReversibleNativeTuring.size_nonzero, 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.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.iota, Monodromy.ReversibleNativeTuring.program, 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.runDriver, Monodromy.CoupledContinuation.Program.runDriver_of_reaches, Monodromy.CoupledContinuation.Program.step, Monodromy.CoupledContinuation.execute, Monodromy.CoupledContinuation.intermediateCurve, Monodromy.CoupledContinuation.intermediateCurve_actual_lift, Monodromy.CoupledContinuation.intermediatePath, Monodromy.CoupledContinuation.restrictedBase, Monodromy.CoupledContinuation.restrictedState, Monodromy.CoupledContinuation.restrictedState_over_base, Monodromy.CoupledContinuation.restrictedTrajectory, Monodromy.CoupledContinuation.restrictedTrajectory_actual_lift, Monodromy.CoupledContinuation.restrictedTrajectory_end, 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.Related, Monodromy.ReversibleNativeTuring.iota, Monodromy.ReversibleNativeTuring.program, Monodromy.ReversibleNativeTuring.respects, Monodromy.ReversibleNativeTuring.size_nonzero, 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.finite_run_actual_lifts (machine : TM0.Machine (Fin a) (Fin q))
{first last : TM0.Cfg (Fin a) (Fin q)} (history : ℕ)
(run : StateTransition.Reaches (TM0.step machine) first last) :
∃ finalHistory, ∃ count : ℕ,
let initial := iota a q machine first history
let driver := (program a q machine).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 (iota a q machine 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 every pair of -configurations , every initial natural history (including ), and every finite, possibly zero-step run from to , there exist a natural final history and such that, writing and for the driver obtained by concatenating successive routed advance drivers of starting at , the intermediate curve of at equals the lower-covering lift of 's restricted path starting at , the restricted trajectory equals the upper-covering lift of the intermediate path starting at the restricted , and its time- value is the restriction of . The driver of length is idle; driver construction iterates advance without checking stop flags. No strict increase of and no positive lower bound on is asserted here.
Confirmed by the mission captain (proposal self-audit).