Recorded Evaluation Preserves Complete Turing Results up to Final History
ProvedMonodromy.ReversibleTuring.result_iffFor positive naturals a,q, every Turing machine m over Fin a and Fin q, configurations x,y and natural history h, the following are equivalent: there exists a natural final history h′ such that the reversible recording table’s partial evaluation from encode(x,h) returns encode(y,h′); and the source Turing evaluation from x returns the complete halted configuration y. The existential history lies inside the recorded-result side of the equivalence; no final-history inequality is asserted.
Statement dependencies: Monodromy.Counter.Compression.size, Monodromy.Counter.Reversible.Recording.edges, Monodromy.Counter.Reversible.Recording.size, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.eval, Monodromy.Counter.TuringCompiler.size, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.encode, Monodromy.ReversibleTuring.table.
Original proof dependencies: Monodromy.Counter.Compression.size, Monodromy.Counter.Reversible.Recording.edges, Monodromy.Counter.Reversible.Recording.size, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.eval, Monodromy.Counter.Reversible.step, Monodromy.Counter.TuringCompiler.size, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.Related, Monodromy.ReversibleTuring.encode, Monodromy.ReversibleTuring.encode_injective, Monodromy.ReversibleTuring.respects, Monodromy.ReversibleTuring.table.
Statement elaboration dependencies: Monodromy.Counter.Compression.size, Monodromy.Counter.Reversible.Recording.edges, Monodromy.Counter.Reversible.Recording.size, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.eval, Monodromy.Counter.TuringCompiler.size, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.encode, Monodromy.ReversibleTuring.table.
Proof elaboration dependencies: Monodromy.Counter.Compression.size, Monodromy.Counter.Reversible.Recording.edges, Monodromy.Counter.Reversible.Recording.size, Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.eval, Monodromy.Counter.Reversible.step, Monodromy.Counter.TuringCompiler.size, Monodromy.NativeTuring.source2, Monodromy.NativeTuring.source3, Monodromy.RecordedTuring.size, Monodromy.ReversibleTuring.Related, Monodromy.ReversibleTuring.encode, Monodromy.ReversibleTuring.encode_injective, Monodromy.ReversibleTuring.respects, 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.result_iff (machine : TM0.Machine (Fin a) (Fin q))
(first last : TM0.Cfg (Fin a) (Fin q)) (history : ℕ) :
(∃ finalHistory, encode a q machine last finalHistory ∈
Counter.Reversible.eval (table a q machine) (encode a q machine first history)) ↔
last ∈ StateTransition.eval (TM0.step machine) first := 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 two configurations of and every , there exists such that complete partial evaluation of the four-register recording table from its encoded state for returns its encoded state for if and only if complete partial evaluation of from returns . Evaluation takes least-enabled-edge steps until the table has no enabled edge and returns that terminal state, and is undefined if no such finite stopping time exists; the right-hand Turing evaluation has the same final-state interpretation. The claim includes an already halted source configuration and , and it neither asserts uniqueness of nor requires in this result equivalence.
Confirmed by the mission captain (proposal self-audit).