A Recorded Turing Step Is a Marked First Return with Larger History
ProvedMonodromy.ReversibleTuring.step_firstReturnFor positive naturals a,q, a Turing machine m over Fin a and Fin q, complete configurations x,y with TM0.step(m,x)=some y, and any natural history h, there exists a natural h′>h such that the reversible recording table has a positive first return from its encoding of (x,h) to its encoding of (y,h′) at the finite Turing-dispatch marks, with no marked intermediate return.
Statement dependencies: Monodromy.Counter.Compression.size, Monodromy.Counter.Reversible.Recording.MarkedFirstReturn, Monodromy.Counter.TuringCompiler.size, Monodromy.NativeTuring.counterMark, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.ReversibleTuring.encode.
Original proof dependencies: Monodromy.Counter.Compression.dispatch, Monodromy.Counter.Compression.encode, Monodromy.Counter.Compression.size, Monodromy.Counter.Configuration, Monodromy.Counter.Reversible.Recording.MarkedFirstReturn, Monodromy.Counter.Reversible.Recording.marked_firstReturn, Monodromy.Counter.TuringCompiler.Row, Monodromy.Counter.TuringCompiler.dispatch, Monodromy.Counter.TuringCompiler.encode, Monodromy.Counter.TuringCompiler.size, Monodromy.Counter.step, Monodromy.NativeTuring.CounterInternalReaches, Monodromy.NativeTuring.CounterInternalStep, Monodromy.NativeTuring.CounterMarked, Monodromy.NativeTuring.counterMark, Monodromy.NativeTuring.counter_firstReturn, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.RecordedTuring.counterEncode, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.encode, Monodromy.ReversibleTuring.source_marked.
Statement elaboration dependencies: Monodromy.Counter.Compression.size, Monodromy.Counter.Reversible.Recording.MarkedFirstReturn, Monodromy.Counter.TuringCompiler.size, Monodromy.NativeTuring.counterMark, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.ReversibleTuring.encode.
Proof elaboration dependencies: Monodromy.Counter.Compression.dispatch, Monodromy.Counter.Compression.encode, Monodromy.Counter.Compression.size, Monodromy.Counter.Configuration, Monodromy.Counter.Reversible.Recording.MarkedFirstReturn, Monodromy.Counter.Reversible.Recording.marked_firstReturn, Monodromy.Counter.TuringCompiler.Row, Monodromy.Counter.TuringCompiler.dispatch, Monodromy.Counter.TuringCompiler.encode, Monodromy.Counter.TuringCompiler.size, Monodromy.Counter.step, Monodromy.NativeTuring.CounterInternalReaches, Monodromy.NativeTuring.CounterInternalStep, Monodromy.NativeTuring.CounterMarked, Monodromy.NativeTuring.counterMark, Monodromy.NativeTuring.counter_firstReturn, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.RecordedTuring.counterEncode, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.encode, Monodromy.ReversibleTuring.source_marked.
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 Turing variable (a q : ℕ) [NeZero a] [NeZero q]
theorem Monodromy.ReversibleTuring.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 ∧
Counter.Reversible.Recording.MarkedFirstReturn (NativeTuring.source2 a q machine)
(NativeTuring.counterMark a q machine)
(encode a q machine first history) (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. For every with and every , there exists with such that the recorded four-register encodings of and both have marked controls, one step takes the first to some state , and a finite, possibly empty chain of further steps reaches the second from , each source in this latter chain having unmarked control. Explicitly a control is marked exactly when it is the recording dispatch of a address that is itself the ordinary counter compression's dispatch for a three-counter Turing (control,head) row. This expands the recording marked first-return relation; it requires a positive total number of steps but does not specify that number.
Confirmed by the mission captain (proposal self-audit).