Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Structured finite stack-machine programs

Definition
QMAPerfectCompleteness_Proof_StructuredStackCode

by Dorian Rudolph · Nov 14, 2026 · Mathlib 0df444a (Lean v4.33.1)

qma-perfect-completeness-bbe19ef

Defines finite program codes for atomic statements, sequencing, stack-guarded loops and conditional branches. A bounded execution relation and its composition lemmas connect these structured programs to concrete TM2 output computations.

Definition code
/- Generated from Solutions.StructuredStackCode by authoritative Stage-2 skeleton subtraction.
Original explanatory text, declaration names and scoped commands are retained.
Only selected proof cuts, import rewrites and fact-indexed platform edits are applied. -/
import Definitions.Def_QMAPerfectCompleteness_Main_Cyclic
import Definitions.Def_QMAPerfectCompleteness_Main_Compiler
import Definitions.Def_QMAPerfectCompleteness_Main_Classes
import Definitions.Def_QAlgorithms_ClassicalStringComputability
import Definitions.Def_QMAPerfectCompleteness_Proof_BinaryComposition
import Definitions.Def_QMAPerfectCompleteness_Proof_BlockEncoding
import Definitions.Def_QMAPerfectCompleteness_Proof_CircuitUnitary
import Definitions.Def_QMAPerfectCompleteness_Proof_ConcreteUniformity
import Definitions.Def_QMAPerfectCompleteness_Proof_ControlCircuits
import Definitions.Def_QMAPerfectCompleteness_Proof_Cyclic
import Definitions.Def_QMAPerfectCompleteness_Proof_EuclideanStates
import Definitions.Def_QMAPerfectCompleteness_Proof_PolyTimeComposition
import Definitions.Def_QMAPerfectCompleteness_Proof_RawCircuitEncoding
import Definitions.Def_QMAPerfectCompleteness_Proof_Repetition
import Definitions.Def_QMAPerfectCompleteness_Proof_RepetitionCircuit
import Definitions.Def_QMAPerfectCompleteness_Proof_RepetitionEncoding
import Definitions.Def_QMAPerfectCompleteness_Proof_ReversibleGadgets
import Definitions.Def_QMAPerfectCompleteness_Proof_VerifierEncoding

/- Namespace registrations retained from original proof-only imports. -/
namespace QMAPerfectCompleteness.Main.DiagonalProof
end QMAPerfectCompleteness.Main.DiagonalProof
namespace QMAPerfectCompleteness.Uniformity.Expansion
end QMAPerfectCompleteness.Uniformity.Expansion



/-! Structured finite TM2 programs. Sequencing and stack-guarded loops preserve arbitrary
shared stack data; their execution proofs compose without repeated low-level label bookkeeping. -/
open Turing StateTransition
set_option backward.isDefEq.respectTransparency false
namespace QMAPerfectCompleteness.Uniformity.StructuredStack

abbrev Data (K : Type) := Option Bool × (K → List Bool)

structure Code (K : Type) where
  Label : Type
  [labelFinite : Fintype Label]
  main : Label
  program : Label → TM2.Stmt (fun _ : K => Bool) Label (Option Bool)
attribute [instance] Code.labelFinite

namespace Code
variable {K : Type} [DecidableEq K]
abbrev Cfg (P : Code K) := TM2.Cfg (fun _ : K => Bool) P.Label (Option Bool)
def step (P : Code K) : P.Cfg → Option P.Cfg := TM2.step P.program

def start (P : Code K) (d : Data K) : P.Cfg := ⟨some P.main,d.1,d.2⟩
def halt (P : Code K) (d : Data K) : P.Cfg := ⟨none,d.1,d.2⟩
def Exec (P : Code K) (d e : Data K) (t : ℕ) : Prop :=
  Nonempty (EvalsToInTime P.step (P.start d) (some (P.halt e)) t)

def atomic (q : TM2.Stmt (fun _ : K => Bool) Unit (Option Bool)) : Code K where
  Label := Unit
  main := ()
  program _ := q

def effect (q : TM2.Stmt (fun _ : K => Bool) Unit (Option Bool)) (d : Data K) : Data K :=
  let c := TM2.stepAux q d.1 d.2
  (c.var,c.stk)

/-- An inline statement ending in halt executes in exactly one global TM2 step. -/
theorem atomic_exec (q : TM2.Stmt (fun _ : K => Bool) Unit (Option Bool)) (d : Data K)
    (hq : (TM2.stepAux q d.1 d.2).l=none) : (atomic q).Exec d (effect q d) 1 := by
  refine ⟨{steps := 1,steps_le_m := le_rfl,evals_in_steps := ?_}⟩
  change some (TM2.stepAux q d.1 d.2) = some ⟨none,(TM2.stepAux q d.1 d.2).var,(TM2.stepAux q d.1 d.2).stk⟩
  congr 1
  generalize hd : TM2.stepAux q d.1 d.2 = c at *
  rcases c with ⟨l,v,S⟩
  simp only at hq
  subst l
  rfl

def push (k : K) (b : Bool) : Code K := atomic (.push k (fun _=>b) .halt)
def pop (k : K) : Code K := atomic (.pop k (fun _ b=>b) .halt)
def load (v : Option Bool) : Code K := atomic (.load (fun _=>v) .halt)

theorem push_exec (k : K) (b : Bool) (d : Data K) :
    (push k b).Exec d (d.1,Function.update d.2 k (b::d.2 k)) 1 := atomic_exec _ _ rfl
theorem pop_exec (k : K) (d : Data K) :
    (pop k).Exec d ((d.2 k).head?,Function.update d.2 k (d.2 k).tail) 1 := atomic_exec _ _ rfl
theorem load_exec (v : Option Bool) (d : Data K) : (load v).Exec d (v,d.2) 1 := atomic_exec _ _ rfl

/-- Relabel a subroutine and redirect each return to a caller's continuation label. -/
def linkStmt {A B : Type} (f : A → B) (finish : B)
    (q : TM2.Stmt (fun _ : K => Bool) A (Option Bool)) :
    TM2.Stmt (fun _ : K => Bool) B (Option Bool) :=
  Statement.continueWith (.goto (fun _=>finish)) (Statement.mapLabels f q)

def linkCfg {A B : Type} (f : A → B) (finish : B)
    (c : TM2.Cfg (fun _ : K => Bool) A (Option Bool)) :
    TM2.Cfg (fun _ : K => Bool) B (Option Bool) :=
  ⟨some (c.l.elim finish f),c.var,c.stk⟩

lemma linkStmt_stepAux {A B : Type} (f : A → B) (finish : B)
    (q : TM2.Stmt (fun _ : K => Bool) A (Option Bool)) (d : Data K) :
    TM2.stepAux (linkStmt f finish q) d.1 d.2 = linkCfg f finish (TM2.stepAux q d.1 d.2) := by
  rw [linkStmt,Statement.stepAux_continueWith,Statement.stepAux_mapLabels]
  generalize hd : TM2.stepAux q d.1 d.2 = c
  rcases c with ⟨l,v,S⟩
  cases l <;> rfl

lemma link_step (P Q : Code K) (f : P.Label → Q.Label) (finish : Q.Label)
    (hm : ∀ l, Q.program (f l)=linkStmt f finish (P.program l))
    (c c' : P.Cfg) (h : P.step c=some c') :
    Q.step (linkCfg f finish c)=some (linkCfg f finish c') := by
  rcases c with ⟨l,v,S⟩
  cases l with
  | none => simp [step,TM2.step] at h
  | some l =>
    change some (TM2.stepAux (P.program l) v S)=some c' at h
    have hh := Option.some.inj h
    subst c'
    change some (TM2.stepAux (Q.program (f l)) v S)=_
    rw [hm]
    exact congrArg some (linkStmt_stepAux f finish (P.program l) (v,S))

lemma mapped_step (P Q : Code K) (f : P.Label → Q.Label)
    (hm : ∀ l, Q.program (f l)=Statement.mapLabels f (P.program l))
    (c c' : P.Cfg) (h : P.step c=some c') :
    Q.step (Statement.mapCfgLabels f c)=some (Statement.mapCfgLabels f c') := by
  rcases c with ⟨l,v,S⟩
  cases l with
  | none => simp [step,TM2.step] at h
  | some l =>
    change some (TM2.stepAux (P.program l) v S)=some c' at h
    have hh := Option.some.inj h
    subst c'
    change some (TM2.stepAux (Q.program (f l)) v S)=_
    rw [hm,Statement.stepAux_mapLabels]

abbrev seq (P Q : Code K) : Code K where
  Label := P.Label ⊕ Q.Label
  main := Sum.inl P.main
  program
    | .inl l => linkStmt Sum.inl (.inr Q.main) (P.program l)
    | .inr l => Statement.mapLabels Sum.inr (Q.program l)

/-- Sequential programs share their stacks; no intermediate encoding or copying is needed. -/
theorem seq_exec (P Q : Code K) {d e f : Data K} {m n : ℕ}
    (hp : P.Exec d e m) (hq : Q.Exec e f n) : (seq P Q).Exec d f (m+n) := by
  obtain ⟨hp⟩ := hp
  obtain ⟨hq⟩ := hq
  have hs := successful_iterate_simulation P.step (seq P Q).step
    (linkCfg Sum.inl (.inr Q.main)) (link_step P (seq P Q) Sum.inl (.inr Q.main) (fun _=>rfl))
    hp.steps (P.start d) (P.halt e) hp.evals_in_steps
  have ht := successful_iterate_simulation Q.step (seq P Q).step
    (Statement.mapCfgLabels Sum.inr) (mapped_step Q (seq P Q) Sum.inr (fun _=>rfl))
    hq.steps (Q.start e) (Q.halt f) hq.evals_in_steps
  refine ⟨{ steps := hp.steps+hq.steps, steps_le_m := ?_, evals_in_steps := ?_ }⟩
  · rw [show hp.steps+hq.steps=hq.steps+hp.steps by omega,Function.iterate_add_apply]
    change (fun o => o.bind (seq P Q).step)^[hq.steps]
      ((fun o => o.bind (seq P Q).step)^[hp.steps]
        (some (linkCfg Sum.inl (.inr Q.main) (P.start d)))) = _
    rw [hs]
    exact ht
  · have := hp.steps_le_m
    have := hq.steps_le_m
    omega

/-- A stack guard peeks once and runs a body as long as its finite predicate succeeds. -/
abbrev whilePeek (k : K) (p : Option Bool → Bool) (P : Code K) : Code K where
  Label := Option P.Label
  main := none
  program
    | none => .peek k (fun _ b=>b) (.branch p (.goto (fun _=>some P.main)) .halt)
    | some l => linkStmt some none (P.program l)

theorem while_false (k : K) (p : Option Bool → Bool) (P : Code K) (d : Data K)
    (hp : p (d.2 k).head?=false) :
    (whilePeek k p P).Exec d ((d.2 k).head?,d.2) 1 := by
  refine ⟨{steps := 1,steps_le_m := le_rfl,evals_in_steps := ?_}⟩
  change some (TM2.stepAux ((whilePeek k p P).program none) d.1 d.2)=_
  simp [whilePeek,TM2.stepAux,hp,start,halt]

theorem while_true (k : K) (p : Option Bool → Bool) (P : Code K) {d e f : Data K} {m n : ℕ}
    (hp : p (d.2 k).head?=true)
    (hbody : P.Exec ((d.2 k).head?,d.2) e m)
    (htail : (whilePeek k p P).Exec e f n) : (whilePeek k p P).Exec d f (1+m+n) := by
  obtain ⟨hb⟩ := hbody
  obtain ⟨ht⟩ := htail
  have hs := successful_iterate_simulation P.step (whilePeek k p P).step
    (linkCfg some none) (link_step P (whilePeek k p P) some none (fun _=>rfl))
    hb.steps (P.start ((d.2 k).head?,d.2)) (P.halt e) hb.evals_in_steps
  have hg : (whilePeek k p P).step ((whilePeek k p P).start d) =
      some (linkCfg some none (P.start ((d.2 k).head?,d.2))) := by
    simp [step,TM2.step,start,whilePeek,TM2.stepAux,hp,linkCfg]
  refine ⟨{ steps := 1+hb.steps+ht.steps, steps_le_m := ?_, evals_in_steps := ?_ }⟩
  · rw [show 1+hb.steps+ht.steps=ht.steps+(hb.steps+1) by omega,
      Function.iterate_add_apply,Function.iterate_add_apply,Function.iterate_one]
    change (fun o => o.bind (whilePeek k p P).step)^[ht.steps]
      ((fun o => o.bind (whilePeek k p P).step)^[hb.steps]
        ((whilePeek k p P).step ((whilePeek k p P).start d))) = _
    rw [hg,hs]
    exact ht.evals_in_steps
  · have := hb.steps_le_m
    have := ht.steps_le_m
    omega

/-- Increase a proved runtime bound without changing the machine. -/
theorem exec_mono (P : Code K) {d e : Data K} {m n : ℕ}
    (h : P.Exec d e m) (hm : m ≤ n) : P.Exec d e n := by
  obtain ⟨h⟩ := h
  exact ⟨{ steps := h.steps, evals_in_steps := h.evals_in_steps, steps_le_m := h.steps_le_m.trans hm }⟩

abbrev ifPeek (k : K) (p : Option Bool → Bool) (P Q : Code K) : Code K where
  Label := Option (P.Label ⊕ Q.Label)
  main := none
  program
    | none => .peek k (fun _ b=>b) (.branch p
        (.goto (fun _=>some (.inl P.main))) (.goto (fun _=>some (.inr Q.main))))
    | some (.inl l) => Statement.mapLabels (fun l=>some (.inl l)) (P.program l)
    | some (.inr l) => Statement.mapLabels (fun l=>some (.inr l)) (Q.program l)

theorem ifPeek_true (k : K) (p : Option Bool → Bool) (P Q : Code K)
    {d e : Data K} {m : ℕ} (hp : p (d.2 k).head?=true)
    (h : P.Exec ((d.2 k).head?,d.2) e m) : (ifPeek k p P Q).Exec d e (m+1) := by
  obtain ⟨h⟩ := h
  have hs := successful_iterate_simulation P.step (ifPeek k p P Q).step
    (Statement.mapCfgLabels (fun l=>some (.inl l)))
    (mapped_step P (ifPeek k p P Q) (fun l=>some (.inl l)) (fun _=>rfl))
    h.steps (P.start ((d.2 k).head?,d.2)) (P.halt e) h.evals_in_steps
  refine ⟨{ steps := h.steps+1, evals_in_steps := ?_, steps_le_m := by have := h.steps_le_m; omega }⟩
  rw [Function.iterate_succ_apply]
  change (fun o=>o.bind (ifPeek k p P Q).step)^[h.steps]
    ((ifPeek k p P Q).step ((ifPeek k p P Q).start d)) = _
  have hg : (ifPeek k p P Q).step ((ifPeek k p P Q).start d) =
      some (Statement.mapCfgLabels (fun l=>some (.inl l)) (P.start ((d.2 k).head?,d.2))) := by
    simp [step,TM2.step,ifPeek,TM2.stepAux,hp,start,Statement.mapCfgLabels]
  rw [hg]
  exact hs

theorem ifPeek_false (k : K) (p : Option Bool → Bool) (P Q : Code K)
    {d e : Data K} {m : ℕ} (hp : p (d.2 k).head?=false)
    (h : Q.Exec ((d.2 k).head?,d.2) e m) : (ifPeek k p P Q).Exec d e (m+1) := by
  obtain ⟨h⟩ := h
  have hs := successful_iterate_simulation Q.step (ifPeek k p P Q).step
    (Statement.mapCfgLabels (fun l=>some (.inr l)))
    (mapped_step Q (ifPeek k p P Q) (fun l=>some (.inr l)) (fun _=>rfl))
    h.steps (Q.start ((d.2 k).head?,d.2)) (Q.halt e) h.evals_in_steps
  refine ⟨{ steps := h.steps+1, evals_in_steps := ?_, steps_le_m := by have := h.steps_le_m; omega }⟩
  rw [Function.iterate_succ_apply]
  change (fun o=>o.bind (ifPeek k p P Q).step)^[h.steps]
    ((ifPeek k p P Q).step ((ifPeek k p P Q).start d)) = _
  have hg : (ifPeek k p P Q).step ((ifPeek k p P Q).start d) =
      some (Statement.mapCfgLabels (fun l=>some (.inr l)) (Q.start ((d.2 k).head?,d.2))) := by
    simp [step,TM2.step,ifPeek,TM2.stepAux,hp,start,Statement.mapCfgLabels]
  rw [hg]
  exact hs

abbrev toMachine [Fintype K] (P : Code K) (input output : K) : FinTM2 where
  K := K
  k₀ := input
  k₁ := output
  Γ _ := Bool
  Λ := P.Label
  main := P.main
  σ := Option Bool
  initialState := none
  m := P.program

/-- Turn a structured-program proof into the actual bundled machine required by the platform. -/
noncomputable def outputs [Fintype K] (P : Code K) (input output : K) (s t : List Bool) (m : ℕ)
    (h : P.Exec (none,Function.update (fun _=>[]) input s)
      (none,Function.update (fun _=>[]) output t) m) :
    TM2OutputsInTime (toMachine P input output) s (some t) m := by
  let hr := Classical.choice h
  have hi : initList (toMachine P input output) s =
      P.start (none,Function.update (fun _=>[]) input s) := by
    simp only [initList,start,toMachine]
    congr 1
    funext k
    by_cases hk : k=input <;> simp [initList,toMachine,start,hk]
  have ho : haltList (toMachine P input output) t =
      P.halt (none,Function.update (fun _=>[]) output t) := by
    simp only [haltList,halt,toMachine]
    congr 1
    funext k
    by_cases hk : k=output <;> simp [haltList,toMachine,halt,hk]
  unfold TM2OutputsInTime
  simp only [Option.map_some,hi,ho]
  exact hr

end Code
end QMAPerfectCompleteness.Uniformity.StructuredStack
Source
Formalization auxiliary for ~/research/qma1z/main.tex, the uniform circuit implementation supporting Section 3.3 and the proof of Theorem 1.1. Original Lean source: commit bbe19efbde567e5c8f7fe21655fd0c4da3573e4d, Solutions/StructuredStackCode.lean, retained declaration span lines 9–257.

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