Prime Compression Preserves the Marked Turing Step and Its Growing History
ProvedMonodromy.ReversibleTuring.Compression.step_firstReturnFor positive naturals a,q, a Turing machine m over Fin a and Fin q, configurations x,y with TM0.step(m,x)=some y, and any natural history h, there exists h′>h such that the fixed prime compression of the four-register recording table has a marked positive first return from encode(x,h) to encode(y,h′). The marks are the specified source Turing-dispatch boundaries, and no intermediate compressed return is marked.
Statement dependencies: Monodromy.Counter.Compression.size, Monodromy.Counter.Reversible.PrimeCompression.MarkedFirstReturn, Monodromy.Counter.Reversible.Recording.edges, Monodromy.Counter.Reversible.Recording.size, Monodromy.Counter.TuringCompiler.size, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.Compression.basis, Monodromy.ReversibleTuring.Compression.encode, Monodromy.ReversibleTuring.Compression.sourceMark, Monodromy.ReversibleTuring.Compression.source_deterministic, Monodromy.ReversibleTuring.Compression.source_targetCompatible, Monodromy.ReversibleTuring.table.
Original proof dependencies: Monodromy.Counter.Compression.size, Monodromy.Counter.Reversible.PrimeCompression.MarkedFirstReturn, Monodromy.Counter.Reversible.PrimeCompression.encode, Monodromy.Counter.Reversible.PrimeCompression.marked_firstReturn, Monodromy.Counter.Reversible.PrimeCompression.toNatural, Monodromy.Counter.Reversible.Recording.InternalMarkedReaches, Monodromy.Counter.Reversible.Recording.InternalMarkedStep, Monodromy.Counter.Reversible.Recording.Marked, Monodromy.Counter.Reversible.Recording.MarkedFirstReturn, Monodromy.Counter.Reversible.Recording.Valid, Monodromy.Counter.Reversible.Recording.edges, Monodromy.Counter.Reversible.Recording.size, Monodromy.Counter.Reversible.Recording.stable, Monodromy.Counter.Reversible.Recording.table, Monodromy.Counter.Reversible.Recording.unitShift, Monodromy.Counter.Reversible.Recording.valid_encode, Monodromy.Counter.Reversible.Recording.valid_nonnegative, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.step, Monodromy.Counter.TuringCompiler.size, Monodromy.NativeTuring.counterMark, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.RecordedTuring.counterEncode, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.Boundary, Monodromy.ReversibleTuring.Compression.basis, Monodromy.ReversibleTuring.Compression.encode, Monodromy.ReversibleTuring.Compression.sourceMark, Monodromy.ReversibleTuring.Compression.sourceMark_false_iff, Monodromy.ReversibleTuring.Compression.sourceMark_true_iff, Monodromy.ReversibleTuring.Compression.source_deterministic, Monodromy.ReversibleTuring.Compression.source_targetCompatible, Monodromy.ReversibleTuring.encode, Monodromy.ReversibleTuring.step_firstReturn, Monodromy.ReversibleTuring.table.
Statement elaboration dependencies: Monodromy.Counter.Compression.size, Monodromy.Counter.Reversible.PrimeCompression.MarkedFirstReturn, Monodromy.Counter.Reversible.Recording.edges, Monodromy.Counter.Reversible.Recording.size, Monodromy.Counter.TuringCompiler.size, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.Compression.basis, Monodromy.ReversibleTuring.Compression.encode, Monodromy.ReversibleTuring.Compression.sourceMark, Monodromy.ReversibleTuring.Compression.source_deterministic, Monodromy.ReversibleTuring.Compression.source_targetCompatible, Monodromy.ReversibleTuring.table.
Proof elaboration dependencies: Monodromy.Counter.Compression.size, Monodromy.Counter.Reversible.PrimeCompression.MarkedFirstReturn, Monodromy.Counter.Reversible.PrimeCompression.encode, Monodromy.Counter.Reversible.PrimeCompression.marked_firstReturn, Monodromy.Counter.Reversible.PrimeCompression.toNatural, Monodromy.Counter.Reversible.Recording.InternalMarkedReaches, Monodromy.Counter.Reversible.Recording.InternalMarkedStep, Monodromy.Counter.Reversible.Recording.Marked, Monodromy.Counter.Reversible.Recording.MarkedFirstReturn, Monodromy.Counter.Reversible.Recording.Valid, Monodromy.Counter.Reversible.Recording.edges, Monodromy.Counter.Reversible.Recording.size, Monodromy.Counter.Reversible.Recording.stable, Monodromy.Counter.Reversible.Recording.table, Monodromy.Counter.Reversible.Recording.unitShift, Monodromy.Counter.Reversible.Recording.valid_encode, Monodromy.Counter.Reversible.Recording.valid_nonnegative, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.step, Monodromy.Counter.TuringCompiler.size, Monodromy.NativeTuring.counterMark, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.RecordedTuring.counterEncode, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.Boundary, Monodromy.ReversibleTuring.Compression.basis, Monodromy.ReversibleTuring.Compression.encode, Monodromy.ReversibleTuring.Compression.sourceMark, Monodromy.ReversibleTuring.Compression.sourceMark_false_iff, Monodromy.ReversibleTuring.Compression.sourceMark_true_iff, Monodromy.ReversibleTuring.Compression.source_deterministic, Monodromy.ReversibleTuring.Compression.source_targetCompatible, Monodromy.ReversibleTuring.encode, Monodromy.ReversibleTuring.step_firstReturn, Monodromy.ReversibleTuring.table.
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.ReversibleTuring open Monodromy.ReversibleTuring.Compression open Turing Counter.Reversible variable (a q : ℕ) [NeZero a] [NeZero q]
theorem Monodromy.ReversibleTuring.Compression.step_firstReturn (machine : TM0.Machine (Fin a) (Fin q))
{first last : TM0.Cfg (Fin a) (Fin q)} (transition : TM0.step machine first = some last)
(history : ℕ) :
∃ finalHistory, history < finalHistory ∧
PrimeCompression.MarkedFirstReturn basis (ReversibleTuring.table a q machine)
(source_deterministic a q machine) (source_targetCompatible a q machine)
(sourceMark a q machine)
(Monodromy.ReversibleTuring.Compression.encode a q machine first history) (Monodromy.ReversibleTuring.Compression.encode a q machine last finalHistory) := by sorry
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
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. For any configurations satisfying and any , there exists with such that and are both marked compressed states, there is one step from to a state , and a finite, possibly empty chain of further steps from to has every source unmarked. Here marked means that the control is the port-wiring image of a recording dispatch associated with an original Turing (control,head) row; the Boolean source marking tests this property at all-zero registers and therefore marks controls independently of data. This is precisely the prime-compression marked first-return predicate; at least one step overall is required, but no bound or exact number is asserted.
Confirmed by the mission captain (proposal self-audit).