op75_tm2_pushes
def
A syntactic upper bound on how many pushes a single TM2 statement can execute, using a maximum at branches.
Statement
def op75_tm2_pushes {K : Type} {Γ : K → Type} {Λ σ : Type} : Turing.TM2.Stmt Γ Λ σ → ℕ
- Source
- OP-75 Karp-reduction composition: finite-statement stack-growth bound in the repository TM2 model.
- Verified
- 15 Nov 2026
- Axioms
- none listed
- Used by 2
- op75_tm2_step_aux_lengthExecuting one TM2 statement increases any chosen stack length by at most the syntactic push bound.
- op75_tm2_machine_one_step_boundFor any finite TM2 and any of its stacks, some constant bounds that stack’s length increase in every machine step.
Lean source view module on GitHub
def op75_tm2_pushes {K : Type} {Γ : K → Type} {Λ σ : Type} : Turing.TM2.Stmt Γ Λ σ → ℕ | .push _ _ q => op75_tm2_pushes q + 1 | .peek _ _ q => op75_tm2_pushes q | .pop _ _ q => op75_tm2_pushes q | .load _ q => op75_tm2_pushes q | .branch _ q r => max (op75_tm2_pushes q) (op75_tm2_pushes r) | .goto _ => 0 | .halt => 0