Stack-to-Tape Translation Preserves the Entire Partial Evaluation
ProvedMonodromy.FormalCompilation.eval1For every source ToPartrec code and every finite list v of natural-number arguments, the translated TM1 machine’s partial evaluation from its initial tapeData(v) configuration equals source.eval(v) with each returned list mapped to the specified halted TM1 configuration halt1(source,·). The equality includes the undefined case and also applies to the empty argument list.
Statement dependencies: Monodromy.FormalCompilation.Alphabet, Monodromy.FormalCompilation.Control1, Monodromy.FormalCompilation.Stack, Monodromy.FormalCompilation.Store, Monodromy.FormalCompilation.Symbol, Monodromy.FormalCompilation.control1Inhabited, Monodromy.FormalCompilation.halt1, Monodromy.FormalCompilation.machine1, Monodromy.FormalCompilation.tapeData.
Original proof dependencies: Monodromy.FormalCompilation.Alphabet, Monodromy.FormalCompilation.Control1, Monodromy.FormalCompilation.Stack, Monodromy.FormalCompilation.Store, Monodromy.FormalCompilation.Symbol, Monodromy.FormalCompilation.control1Inhabited, Monodromy.FormalCompilation.halt1, Monodromy.FormalCompilation.halt_relation, Monodromy.FormalCompilation.initial_relation, Monodromy.FormalCompilation.machine1, Monodromy.FormalCompilation.relation_unique, Monodromy.FormalCompilation.tapeData.
Statement elaboration dependencies: Monodromy.FormalCompilation.Alphabet, Monodromy.FormalCompilation.Control1, Monodromy.FormalCompilation.Stack, Monodromy.FormalCompilation.Store, Monodromy.FormalCompilation.Symbol, Monodromy.FormalCompilation.control1Inhabited, Monodromy.FormalCompilation.halt1, Monodromy.FormalCompilation.machine1, Monodromy.FormalCompilation.tapeData.
Proof elaboration dependencies: Monodromy.FormalCompilation.Alphabet, Monodromy.FormalCompilation.Control1, Monodromy.FormalCompilation.Stack, Monodromy.FormalCompilation.Store, Monodromy.FormalCompilation.Symbol, Monodromy.FormalCompilation.control1Inhabited, Monodromy.FormalCompilation.halt1, Monodromy.FormalCompilation.halt_relation, Monodromy.FormalCompilation.initial_relation, Monodromy.FormalCompilation.machine1, Monodromy.FormalCompilation.relation_unique, Monodromy.FormalCompilation.tapeData.
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.FormalCompilation open Turing variable (source : ToPartrec.Code)
theorem Monodromy.FormalCompilation.eval1 (values : List ℕ) :
StateTransition.eval (TM1.step (machine1 source))
(TM1.init (tapeData values) : TM1.Cfg Alphabet (Control1 source) Store) =
halt1 source <$> source.eval values := by sorry
Read-back
What the Lean code literally says, in plain math · OpenAI Codex (independent agent)
For every partial-recursive list-program code in the specified code language and every finite input list of natural numbers, the complete partial evaluation of the associated tape machine from its initial configuration equals the partial value mapped to a particular halted configuration. The associated TM1 table is Mathlib's stack-to-tape translation of its stack-machine interpreter for these codes; its four stack names are main, reverse, auxiliary and stack, its stack-symbol set is the four constructors list-separator, number-separator, bit-zero and bit-one, its variable store is an optional stack symbol, its tape alphabet is a Boolean bottom marker together with one optional symbol for each of the four stacks, and its control type is the translator's normal/go/return control type, with distinguished initial normal label corresponding to running and then halting. The input word is formed by writing each natural number in least-significant-bit-first binary, with zero represented by no bits, adjoining a number separator after each number, reversing this symbol list onto the main-stack track of a tape word, leaving other tracks empty, and marking the first cell as bottom; even the empty list gives the bottom-marked cell. The initial tape lies at that word's beginning with blank left half and store none. For any output list , the named halted configuration is the same initialization constructed from with its control field replaced by none. Thus, if is defined, tape evaluation is defined with exactly that entire halted configuration, including tape, control and store; if is undefined, tape evaluation is undefined. The equality includes empty lists, zero arguments and immediate or infinite executions and asserts no running-time bound.
Confirmed by the mission captain (proposal self-audit).