AFTD Auto-Formalizing Theoretical Domains

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

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
See it in the graphDiscuss this resultChallenge it