Prime-Compressed Evaluation Preserves Complete Turing Results
ProvedMonodromy.ReversibleTuring.Compression.result_iffFor positive naturals a,q, every Turing machine m over Fin a and Fin q, configurations x,y and natural initial history h, the following are equivalent: there exists a natural h′ for which the prime-compressed reversible 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 final history is inside the compressed-result side of the equivalence; no final-history inequality is asserted.
Statement dependencies: Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.eval, Monodromy.ReversibleTuring.Compression.edges, Monodromy.ReversibleTuring.Compression.encode, Monodromy.ReversibleTuring.Compression.size, Monodromy.ReversibleTuring.Compression.table.
Original proof dependencies: Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.eval, Monodromy.Counter.Reversible.step, Monodromy.ReversibleTuring.Compression.Related, Monodromy.ReversibleTuring.Compression.edges, Monodromy.ReversibleTuring.Compression.encode, Monodromy.ReversibleTuring.Compression.encode_injective, Monodromy.ReversibleTuring.Compression.respects, Monodromy.ReversibleTuring.Compression.size, Monodromy.ReversibleTuring.Compression.table.
Statement elaboration dependencies: Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.eval, Monodromy.ReversibleTuring.Compression.edges, Monodromy.ReversibleTuring.Compression.encode, Monodromy.ReversibleTuring.Compression.size, Monodromy.ReversibleTuring.Compression.table.
Proof elaboration dependencies: Monodromy.Counter.Reversible.State, Monodromy.Counter.Reversible.eval, Monodromy.Counter.Reversible.step, Monodromy.ReversibleTuring.Compression.Related, Monodromy.ReversibleTuring.Compression.edges, Monodromy.ReversibleTuring.Compression.encode, Monodromy.ReversibleTuring.Compression.encode_injective, Monodromy.ReversibleTuring.Compression.respects, Monodromy.ReversibleTuring.Compression.size, Monodromy.ReversibleTuring.Compression.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.result_iff (machine : TM0.Machine (Fin a) (Fin q))
(first last : TM0.Cfg (Fin a) (Fin q)) (history : ℕ) :
(∃ finalHistory, Monodromy.ReversibleTuring.Compression.encode a q machine last finalHistory ∈
Monodromy.Counter.Reversible.eval (Monodromy.ReversibleTuring.Compression.table a q machine) (Monodromy.ReversibleTuring.Compression.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. 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 all configurations of and every , there exists such that the complete partial evaluation of the two-register integer table starting at returns if and only if complete partial evaluation of from returns . Complete table evaluation repeatedly executes the least enabled edge until there is no enabled edge, and is undefined for an infinite run; the same terminating-state semantics is used for Turing evaluation. Thus on the right must be a terminal configuration, while the existential final history is not asserted unique or greater than here; histories and immediate termination are included.
Confirmed by the mission captain (proposal self-audit).