Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Prime-Compressed Evaluation Preserves Complete Turing Results

Proved
Monodromy.ReversibleTuring.Compression.result_iff

by Xiaoyang Liu · Nov 5, 2026 · Mathlib 0df444a (Lean v4.33.1)

computabilitycovering-spacesmonodromy-computation

For 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.

Preamble
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]

Formal statement
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
Source
Authoritative local working-tree snapshot SHA-256 e03ce2d08e07ee663140bec213fb21e995f44153a3c556c908fcf1c8d6fefe6c; repository https://github.com/ERHUTUZI123/monodromy. The remote Git base is incomplete and is not asserted to contain these declarations. src/Monodromy/FormalCompilation.lean (file SHA-256 c07335814044367fc4605d1e494fe82a30c684f754d58d55aaa7514b94c37122): Monodromy.ReversibleTuring.Compression.result_iff at L1280-L1297 [UTF-8 67555:68690].
Read-back

What the Lean code literally says, in plain math · OpenAI Codex (independent agent)

Let a,q>0a,q>0a,q>0 be natural numbers, and let MMM be any Post-Turing machine with alphabet {0,…,a−1}\{0,\ldots,a-1\}{0,…,a−1} and control set {0,…,q−1}\{0,\ldots,q-1\}{0,…,q−1}, both with default 000. A configuration consists of a control, a head symbol and two half-tapes modulo trailing blank zeros; MMM either has no next instruction or changes control and writes a symbol or moves the head one cell. The base-(a+1)(a+1)(a+1) code of a half-tape with nearest-to-head symbols b0,b1,…b_0,b_1,\ldotsb0​,b1​,… is ∑ibi(a+1)i\sum_i b_i(a+1)^i∑i​bi​(a+1)i. The specified three-counter compiler has dispatch rows indexed by (control,head), encodes the two half-tape codes as (L,R,0)(L,R,0)(L,R,0), and uses multiplication, addition and division/remainder instruction blocks. Its ordinary two-counter compression has state (p,(2L3R,0))(p,(2^L3^R,0))(p,(2L3R,0)), where ppp is the compressed dispatch address of that row, and simulates the three counters using primes 2,3,52,3,52,3,5. Denote this two-counter instruction program by CMC_MCM​, its number of addresses by mmm, and its configuration encoding by EME_MEM​. The recording construction TMT_MTM​ is an integer four-register edge table: its encoding of an original configuration sss and history h∈Nh\in\mathbb Nh∈N has control at the recording dispatch of EM(s)E_M(s)EM​(s) and register tuple (EM(s)0,EM(s)1,h,0)(E_M(s)_0,E_M(s)_1,h,0)(EM​(s)0​,EM​(s)1​,h,0). Its graph is formed from a radix block in base 2m+12m+12m+1 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 2p+b+12p+b+12p+b+1. The marked recording vertices are precisely dispatches for addresses of CMC_MCM​ that themselves are compressed dispatches of original (control,head) rows. The prime compression UMU_MUM​ of TMT_MTM​ uses the basis (2,3,5,7)(2,3,5,7)(2,3,5,7): it joins radix blocks for the selected outgoing action and the restoration sites, and retains halt vertices, using the specified port wiring. If bM(s)b_M(s)bM​(s) denotes the resulting wired boundary address associated to the recording dispatch of EM(s)E_M(s)EM​(s), its encoding is FM(s,h)=(bM(s),(2EM(s)03EM(s)15h,0))F_M(s,h)=(b_M(s),(2^{E_M(s)_0}3^{E_M(s)_1}5^h,0))FM​(s,h)=(bM​(s),(2EM​(s)0​3EM​(s)1​5h,0)); natural conversion used before prime encoding sends every negative integer register to 000, 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 TMT_MTM​ and UMU_MUM​ take the least enabled indexed edge and have no successor when no edge is enabled. For all configurations s,ts,ts,t of MMM and every h∈Nh\in\mathbb Nh∈N, there exists h′∈Nh'\in\mathbb Nh′∈N such that the complete partial evaluation of the two-register integer table UMU_MUM​ starting at FM(s,h)F_M(s,h)FM​(s,h) returns FM(t,h′)F_M(t,h')FM​(t,h′) if and only if complete partial evaluation of MMM from sss returns ttt. 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 ttt on the right must be a terminal configuration, while the existential final history is not asserted unique or greater than hhh here; histories 000 and immediate termination are included.

Human review
  • Endorsed by marwahaha · Nov 6, 2026

  • Endorsed by Xiaoyang Liu · Nov 6, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me