Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Recorded Evaluation Preserves Complete Turing Results up to Final History

Proved
Monodromy.ReversibleTuring.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 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.

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 Turing
variable (a q : ℕ) [NeZero a] [NeZero q]

Formal statement
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
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.result_iff at L989-L1006 [UTF-8 51323:52476].
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. For every two 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 complete partial evaluation of the four-register recording table TMT_MTM​ from its encoded state for (s,h)(s,h)(s,h) returns its encoded state for (t,h′)(t,h')(t,h′) if and only if complete partial evaluation of MMM from sss returns ttt. 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 h=0h=0h=0, and it neither asserts uniqueness of h′h'h′ nor requires h′>hh'>hh′>h in this result equivalence.

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