Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Primitive unary arithmetic on shared stacks

Definition
QMAPerfectCompleteness_Proof_UnaryStackOps

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

qma-perfect-completeness-bbe19ef

Defines finite shared-register programs for constants, truncated subtraction and halving. Their execution identities state the resulting unary values, cleared temporary operands and preservation of other stack contents.

Definition code
/- Generated from Solutions.UnaryStackOps 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_StackTransfers
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



/-! Unary arithmetic performed by finite structured TM2 programs on shared registers. -/
open Turing StateTransition
set_option backward.isDefEq.respectTransparency false
namespace QMAPerfectCompleteness.Uniformity.StructuredStack.Code
variable {K : Type} [DecidableEq K]
abbrev unary (n : ℕ) : List Bool := List.replicate n true

abbrev constantStmt (dst : K) (n : ℕ) : TM2.Stmt (fun _ : K=>Bool) Unit (Option Bool) :=
  Nat.rec .halt (fun _ q=>.push dst (fun _=>true) q) n
abbrev constant (dst : K) (n : ℕ) : Code K := atomic (constantStmt dst n)

lemma constantStmt_effect (dst : K) (n : ℕ) (v : Option Bool) (S : K → List Bool) :
    TM2.stepAux (constantStmt dst n) v S =
      ⟨none,v,Function.update S dst (unary n++S dst)⟩ := by
  induction n generalizing S with
  | zero => simp [constantStmt,TM2.stepAux,Function.update_eq_self]
  | succ n ih =>
    simp only [constantStmt,TM2.stepAux]
    rw [ih]
    congr 1
    funext k
    by_cases hk : k=dst
    · subst k
      simp only [Function.update_self,unary,List.replicate_succ,List.cons_append]
      change List.replicate n true ++ ([true] ++ S dst) = _
      rw [← List.append_assoc,← List.replicate_succ',List.replicate_succ,List.cons_append]
    · simp [hk]

lemma constant_exec (dst : K) (n : ℕ) (v : Option Bool) (S : K → List Bool) :
    (constant dst n).Exec (v,S) (v,Function.update S dst (unary n++S dst)) 1 := by
  have hh := atomic_exec (constantStmt dst n) (v,S) (by rw [constantStmt_effect])
  simpa [effect,constantStmt_effect] using hh

abbrev subtractBody (src dst : K) : Code K := atomic
  (.pop src (fun _ b=>b) (.pop dst (fun _ b=>b) .halt))
abbrev subtract (src dst : K) : Code K := whilePeek src Option.isSome (subtractBody src dst)

lemma subtractBody_exec (src dst : K) (h : src ≠ dst) (S : K → List Bool)
    (v : Option Bool) (n m : ℕ) (hs : S src=unary (n+1)) (hd : S dst=unary m) :
    (subtractBody src dst).Exec (v,S)
      ((unary m).head?,Function.update (Function.update S src (unary n)) dst (unary (m-1))) 1 := by
  have hh := atomic_exec (.pop src (fun _ b=>b) (.pop dst (fun _ b=>b) .halt)) (v,S) rfl
  simpa [effect,TM2.stepAux,hs,hd,h,Ne.symm h,unary,List.replicate_succ] using hh

theorem subtract_exec (src dst : K) (h : src ≠ dst) (n m : ℕ)
    (S : K → List Bool) (v : Option Bool) (hs : S src=unary n) (hd : S dst=unary m) :
    (subtract src dst).Exec (v,S)
      (none,Function.update (Function.update S src []) dst (unary (m-n))) (2*n+1) := by
  induction n generalizing m S v with
  | zero =>
    have hh := while_false src Option.isSome (subtractBody src dst) (v,S) (by simp [hs])
    have he : Function.update (Function.update S src []) dst (unary (m-0))=S := by
      funext k
      by_cases hks : k=src <;> by_cases hkd : k=dst <;> simp_all
    rw [he]
    simpa [hs] using hh
  | succ n ih =>
    let S' := Function.update (Function.update S src (unary n)) dst (unary (m-1))
    have hb := subtractBody_exec src dst h S (some true) n m hs hd
    have ht := ih (m-1) S' (unary m).head? (by simp [S',h]) (by simp [S'])
    have hh := while_true src Option.isSome (subtractBody src dst)
      (d := (v,S)) (by simp [hs,unary,List.replicate_succ])
      (by simpa [S',hs,unary,List.replicate_succ] using hb) ht
    have he : Function.update (Function.update S' src []) dst (unary (m-1-n)) =
        Function.update (Function.update S src []) dst (unary (m-(n+1))) := by
      have ha : m-1-n=m-(n+1) := by omega
      funext k
      by_cases hks : k=src <;> by_cases hkd : k=dst <;> simp_all [S']
    rw [he] at hh
    convert hh using 1 <;> omega

abbrev halfBody (src dst : K) : Code K := atomic
  (.pop src (fun _ b=>b) (.pop src (fun _ b=>b)
    (.branch Option.isSome (.push dst (fun _=>true) .halt) .halt)))
abbrev half (src dst : K) : Code K := whilePeek src Option.isSome (halfBody src dst)

lemma halfBody_one (src dst : K) (S : K → List Bool) (v : Option Bool) (hs : S src=unary 1) :
    (halfBody src dst).Exec (v,S) (none,Function.update S src []) 1 := by
  have hh := atomic_exec (.pop src (fun _ b=>b) (.pop src (fun _ b=>b)
    (.branch Option.isSome (.push dst (fun _=>true) .halt) .halt))) (v,S) (by simp [TM2.stepAux,hs,unary])
  simpa [effect,TM2.stepAux,hs,unary] using hh

lemma halfBody_two (src dst : K) (h : src ≠ dst) (S : K → List Bool)
    (v : Option Bool) (n : ℕ) (hs : S src=unary (n+2)) :
    (halfBody src dst).Exec (v,S)
      (some true,Function.update (Function.update S src (unary n)) dst (true::S dst)) 1 := by
  have hh := atomic_exec (.pop src (fun _ b=>b) (.pop src (fun _ b=>b)
    (.branch Option.isSome (.push dst (fun _=>true) .halt) .halt))) (v,S) (by simp [TM2.stepAux,hs,unary,List.replicate_succ])
  simpa [effect,TM2.stepAux,hs,unary,List.replicate_succ,h,Ne.symm h] using hh

/-- Divide a unary register by two while accumulating its quotient on another stack. -/
theorem half_exec (src dst : K) (h : src ≠ dst) (n : ℕ)
    (S : K → List Bool) (v : Option Bool) (hs : S src=unary n) :
    (half src dst).Exec (v,S)
      (none,Function.update (Function.update S src []) dst (unary (n/2)++S dst)) (2*n+1) := by
  induction n using Nat.twoStepInduction generalizing S v with
  | zero =>
    have hh := while_false src Option.isSome (halfBody src dst) (v,S) (by simp [hs])
    have he : Function.update (Function.update S src []) dst (unary (0/2)++S dst)=S := by
      funext k
      by_cases hks : k=src <;> by_cases hkd : k=dst <;> simp_all
    rw [he]
    simpa [hs] using hh
  | one =>
    let S' := Function.update S src []
    have hb := halfBody_one src dst S (some true) hs
    have ht := while_false src Option.isSome (halfBody src dst) (none,S') (by simp [S'])
    have hh := while_true src Option.isSome (halfBody src dst) (d := (v,S))
      (by simp [hs,unary]) (by simpa [hs,S',unary] using hb) ht
    have he : Function.update (Function.update S src []) dst (unary (1/2)++S dst)=S' := by
      funext k
      by_cases hks : k=src <;> by_cases hkd : k=dst <;> simp_all [S']
    rw [he]
    simpa [S'] using hh
  | more n ih _ =>
    let S' := Function.update (Function.update S src (unary n)) dst (true::S dst)
    have hb := halfBody_two src dst h S (some true) n hs
    have ht := ih S' (some true) (by simp [S',h])
    have hh := while_true src Option.isSome (halfBody src dst) (d := (v,S))
      (by simp [hs,unary,List.replicate_succ])
      (by simpa [S',hs,unary,List.replicate_succ] using hb) ht
    have he : Function.update (Function.update S' src []) dst (unary (n/2)++S' dst) =
        Function.update (Function.update S src []) dst (unary ((n+2)/2)++S dst) := by
      have ha : (n+2)/2=n/2+1 := by omega
      funext k
      by_cases hks : k=src <;> by_cases hkd : k=dst <;>
        simp_all [S',unary,List.replicate_add,List.append_assoc]
    rw [he] at hh
    exact exec_mono _ hh (by 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/UnaryStackOps.lean, retained declaration span lines 8–131.

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