The Recorded Macro Executes a Live Turing Step and Retains Its New History
ProvedMonodromy.ReversibleTuring.macroStep_liveFor positive naturals a,q, a Turing machine m over Fin a and Fin q, configurations x,y satisfying TM0.step(m,x)=some y, and every natural history h, there is a natural h′>h for which the recorded table’s causal marked-return macro at encode(x,h) is defined with optional value some encode(y,h′). The complete successor configuration and the strictly larger retained history use the same witness h′.
Statement dependencies: Monodromy.Counter.Reversible.Recording.size, Monodromy.Counter.Reversible.State, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.encode, Monodromy.ReversibleTuring.macroStep.
Original proof dependencies: Monodromy.Counter.Compression.size, Monodromy.Counter.Reversible.Recording.InternalMarkedReaches, Monodromy.Counter.Reversible.Recording.Marked, Monodromy.Counter.Reversible.Recording.MarkedFirstReturn, Monodromy.Counter.Reversible.Recording.edges, Monodromy.Counter.Reversible.Recording.size, Monodromy.Counter.Reversible.Recording.table, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.step, Monodromy.Counter.TuringCompiler.size, Monodromy.NativeTuring.counterMark, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.boundaryTransition, Monodromy.ReversibleTuring.boundaryTransition_stops, Monodromy.ReversibleTuring.encode, Monodromy.ReversibleTuring.internal_marked_reaches, Monodromy.ReversibleTuring.macroStep, Monodromy.ReversibleTuring.step_firstReturn, Monodromy.ReversibleTuring.table.
Statement elaboration dependencies: Monodromy.Counter.Reversible.Recording.size, Monodromy.Counter.Reversible.State, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.encode, Monodromy.ReversibleTuring.macroStep.
Proof elaboration dependencies: Monodromy.Counter.Compression.size, Monodromy.Counter.Reversible.Recording.InternalMarkedReaches, Monodromy.Counter.Reversible.Recording.Marked, Monodromy.Counter.Reversible.Recording.MarkedFirstReturn, Monodromy.Counter.Reversible.Recording.edges, Monodromy.Counter.Reversible.Recording.size, Monodromy.Counter.Reversible.Recording.table, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.step, Monodromy.Counter.TuringCompiler.size, Monodromy.NativeTuring.counterMark, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.boundaryTransition, Monodromy.ReversibleTuring.boundaryTransition_stops, Monodromy.ReversibleTuring.encode, Monodromy.ReversibleTuring.internal_marked_reaches, Monodromy.ReversibleTuring.macroStep, 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 Turing variable (a q : ℕ) [NeZero a] [NeZero q]
theorem Monodromy.ReversibleTuring.macroStep_live (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 ∧
macroStep a q machine (encode a q machine first history) =
Part.some (some (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. Define the four-register boundary predicate to mean a marked recording dispatch as described above, and let the boundary-stopped transition be absent at those states and otherwise equal to the ordinary least-enabled-edge step of . The recording macro first attempts one ordinary step: if none is available it returns the defined partial value none; if a successor is present it completely evaluates the boundary-stopped transition from that successor and wraps its result in some, remaining undefined if this evaluation never stops. For every with and every , there exists with such that this macro on the encoded four-register state for is exactly the defined partial value whose optional result is the encoded four-register state for . Both the outer partial value and inner optional successor are present; no reverse-macro conclusion is included.
Confirmed by the mission captain (proposal self-audit).