Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite stack transfer, copy and clearing

Definition
QMAPerfectCompleteness_Proof_StackTransfers

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

qma-perfect-completeness-bbe19ef

Defines shared-stack programs for moving, copying and clearing finite binary words. Execution bounds and framing identities describe reversal during transfer, restoration of copied sources and cleanup of temporary registers.

Definition code
/- Generated from Solutions.StackTransfers 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_StructuredStackCode
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



/-! Concrete shared-stack copying routines for unary circuit-generation registers. -/
open Turing StateTransition
set_option backward.isDefEq.respectTransparency false
namespace QMAPerfectCompleteness.Uniformity.StructuredStack.Code
variable {K : Type} [DecidableEq K]

abbrev moveBody (src dst : K) : Code K := atomic
  (.pop src (fun _ b=>b) (.push dst (fun v=>v.getD false) .halt))
abbrev transfer (src dst : K) : Code K := whilePeek src Option.isSome (moveBody src dst)

lemma moveBody_exec (src dst : K) (h : src ≠ dst) (S : K → List Bool)
    (v : Option Bool) (b : Bool) (xs : List Bool) (hx : S src=b::xs) :
    (moveBody src dst).Exec (v,S)
      (some b,Function.update (Function.update S src xs) dst (b::S dst)) 1 := by
  have hh := atomic_exec (.pop src (fun _ b=>b) (.push dst (fun v=>v.getD false) .halt)) (v,S) rfl
  simpa [effect,TM2.stepAux,hx,h,Ne.symm h] using hh

/-- Move a complete stack onto another stack, reversing its order, and clear the scratch value. -/
theorem transfer_exec (src dst : K) (h : src ≠ dst) (xs : List Bool)
    (S : K → List Bool) (v : Option Bool) (hx : S src=xs) :
    (transfer src dst).Exec (v,S)
      (none,Function.update (Function.update S src []) dst (xs.reverse++S dst)) (2*xs.length+1) := by
  induction xs generalizing S v with
  | nil =>
    have hh := while_false src Option.isSome (moveBody src dst) (v,S) (by simp [hx])
    have hs : Function.update (Function.update S src []) dst (List.reverse [] ++ S dst)=S := by
      funext k
      by_cases hks : k=src <;> by_cases hkd : k=dst <;> simp_all
    rw [hs]
    simpa [hx] using hh
  | cons b xs ih =>
    let S' := Function.update (Function.update S src xs) dst (b::S dst)
    have hbody := moveBody_exec src dst h S (some b) b xs hx
    have htail := ih S' (some b) (by simp [S',h,Ne.symm h])
    have hh := while_true src Option.isSome (moveBody src dst)
      (d := (v,S)) (by simp [hx]) (by simpa [hx,S'] using hbody) htail
    have hs : Function.update (Function.update S' src []) dst (xs.reverse++S' dst) =
        Function.update (Function.update S src []) dst ((b::xs).reverse++S dst) := by
      funext k
      by_cases hks : k=src <;> by_cases hkd : k=dst <;>
        simp_all [S',List.reverse_cons,List.append_assoc]
    rw [hs] at hh
    simpa [List.length_cons,Nat.mul_add,Nat.add_assoc,Nat.add_comm,Nat.add_left_comm] using hh

abbrev clearBody (src : K) : Code K := atomic (.pop src (fun _ b=>b) .halt)
abbrev clear (src : K) : Code K := whilePeek src Option.isSome (clearBody src)

theorem clear_exec (src : K) (xs : List Bool) (S : K → List Bool)
    (v : Option Bool) (hx : S src=xs) :
    (clear src).Exec (v,S) (none,Function.update S src []) (2*xs.length+1) := by
  induction xs generalizing S v with
  | nil =>
    have hh := while_false src Option.isSome (clearBody src) (v,S) (by simp [hx])
    have hs : Function.update S src [] = S := by
      funext k
      by_cases hk : k=src <;> simp_all
    rw [hs]
    simpa [hx] using hh
  | cons b xs ih =>
    let S' := Function.update S src xs
    have hbody : (clearBody src).Exec (some b,S) (some b,S') 1 := by
      simpa [effect,TM2.stepAux,hx,S'] using
        atomic_exec (.pop src (fun _ b=>b) .halt) (some b,S) rfl
    have htail := ih S' (some b) (by simp [S'])
    have hh := while_true src Option.isSome (clearBody src)
      (d := (v,S)) (by simp [hx]) (by simpa [hx] using hbody) htail
    simpa [S',Function.update_idem,List.length_cons,Nat.mul_add,
      Nat.add_assoc,Nat.add_comm,Nat.add_left_comm] using hh

abbrev copyBody (src dst tmp : K) : Code K := atomic
  (.pop src (fun _ b=>b) (.push dst (fun v=>v.getD false)
    (.push tmp (fun v=>v.getD false) .halt)))
abbrev copy (src dst tmp : K) : Code K :=
  seq (whilePeek src Option.isSome (copyBody src dst tmp)) (transfer tmp src)

lemma copyBody_exec (src dst tmp : K) (hsd : src ≠ dst) (hst : src ≠ tmp) (hdt : dst ≠ tmp)
    (S : K → List Bool) (v : Option Bool) (b : Bool) (xs : List Bool) (hx : S src=b::xs) :
    (copyBody src dst tmp).Exec (v,S)
      (some b,Function.update (Function.update (Function.update S src xs)
        dst (b::S dst)) tmp (b::S tmp)) 1 := by
  have hh := atomic_exec (.pop src (fun _ b=>b) (.push dst (fun v=>v.getD false)
    (.push tmp (fun v=>v.getD false) .halt))) (v,S) rfl
  simpa [effect,TM2.stepAux,hx,hsd,hst,hdt,Ne.symm hsd,Ne.symm hst,Ne.symm hdt] using hh

lemma copy_loop_exec (src dst tmp : K) (hsd : src ≠ dst) (hst : src ≠ tmp) (hdt : dst ≠ tmp)
    (xs : List Bool) (S : K → List Bool) (v : Option Bool) (hx : S src=xs) :
    (whilePeek src Option.isSome (copyBody src dst tmp)).Exec (v,S)
      (none,Function.update (Function.update (Function.update S src [])
        dst (xs.reverse++S dst)) tmp (xs.reverse++S tmp)) (2*xs.length+1) := by
  induction xs generalizing S v with
  | nil =>
    have hh := while_false src Option.isSome (copyBody src dst tmp) (v,S) (by simp [hx])
    have hs : Function.update (Function.update (Function.update S src [])
        dst (([] : List Bool).reverse++S dst)) tmp ([].reverse++S tmp)=S := by
      funext k
      by_cases hks : k=src <;> by_cases hkd : k=dst <;> by_cases hkt : k=tmp <;> simp_all
    rw [hs]
    simpa [hx] using hh
  | cons b xs ih =>
    let S' := Function.update (Function.update (Function.update S src xs) dst (b::S dst)) tmp (b::S tmp)
    have hbody := copyBody_exec src dst tmp hsd hst hdt S (some b) b xs hx
    have htail := ih S' (some b) (by simp [S',hsd,hst,Ne.symm hsd,Ne.symm hst])
    have hh := while_true src Option.isSome (copyBody src dst tmp)
      (d := (v,S)) (by simp [hx]) (by simpa [hx,S'] using hbody) htail
    have hs : Function.update (Function.update (Function.update S' src [])
        dst (xs.reverse++S' dst)) tmp (xs.reverse++S' tmp) =
        Function.update (Function.update (Function.update S src [])
          dst ((b::xs).reverse++S dst)) tmp ((b::xs).reverse++S tmp) := by
      funext k
      by_cases hks : k=src <;> by_cases hkd : k=dst <;> by_cases hkt : k=tmp <;>
        simp_all [S',List.reverse_cons,List.append_assoc]
    rw [hs] at hh
    simpa [List.length_cons,Nat.mul_add,Nat.add_assoc,Nat.add_comm,Nat.add_left_comm] using hh

/-- Copy a stack while restoring the original and clearing the temporary stack. -/
theorem copy_exec (src dst tmp : K) (hsd : src ≠ dst) (hst : src ≠ tmp) (hdt : dst ≠ tmp)
    (xs : List Bool) (S : K → List Bool) (v : Option Bool) (hx : S src=xs) (ht : S tmp=[]) :
    (copy src dst tmp).Exec (v,S)
      (none,Function.update S dst (xs.reverse++S dst)) (4*xs.length+2) := by
  let S' := Function.update (Function.update (Function.update S src [])
    dst (xs.reverse++S dst)) tmp xs.reverse
  have h₁ := copy_loop_exec src dst tmp hsd hst hdt xs S v hx
  have h₂ := transfer_exec tmp src (Ne.symm hst) xs.reverse S' none (by simp [S'])
  have hh := seq_exec _ _ (by simpa [ht,S'] using h₁) h₂
  have hs : Function.update (Function.update S' tmp []) src (xs.reverse.reverse++S' src) =
      Function.update S dst (xs.reverse++S dst) := by
    funext k
    by_cases hks : k=src <;> by_cases hkd : k=dst <;> by_cases hkt : k=tmp <;>
      simp_all [S']
  rw [hs] at hh
  convert hh using 1 <;> simp only [List.length_reverse] <;> omega

end QMAPerfectCompleteness.Uniformity.StructuredStack.Code
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/StackTransfers.lean, retained declaration span lines 9–133.

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