op75_tm2_step_aux_length
Executing one TM2 statement increases any chosen stack length by at most the syntactic push bound.
Statement
theorem op75_tm2_step_aux_length {K : Type} [DecidableEq K] {Γ : K → Type} {Λ σ : Type} (s : Turing.TM2.Stmt Γ Λ σ) (v : σ) (S : ∀ k, List (Γ k)) (j : K) : ((Turing.TM2.stepAux s v S).stk j).length ≤ (S j).length + op75_tm2_pushes s
- Source
- OP-75 Karp-reduction composition: finite-statement stack-growth bound in the repository TM2 model.
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- op75_tm2_pushesA syntactic upper bound on how many pushes a single TM2 statement can execute, using a maximum at branches.
- Used by 1
- 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.
The proof, explained
Executing one step of a TM2 machine on a statement s increases the length of any chosen stack j by at most op75_tm2_pushes s. The proof proceeds by structural induction on the statement s, generalizing over the internal state and stack configuration. Push instructions add at most one element to the targeted stack plus whatever remaining instructions push, while peek, pop, load, jump, and halt instructions do not increase stack sizes on their own, and branching instructions take the maximum push count of the two branches.
We proceed by structural induction on the statement s, generalizing over the local state v and stack configuration S.
The statement s is an inductively defined TM2 command. Inducting on s while generalizing v and S ensures that the induction hypotheses apply to whatever local state and stack configuration arise during intermediate steps.
induction s generalizing v S with
For a push statement `push k f q`, the length of stack j increases by at most 1 + op75_tm2_pushes q.
Executing `push k f q` pushes the value f(v) onto stack k and proceeds with statement q, while the static push bound increments by 1. By the induction hypothesis on q applied to the updated stacks, the remaining execution adds at most op75_tm2_pushes q to stack j. If j = k, stack k grew by 1 initially, and linear arithmetic gives that the total length is at most (S k).length + 1 + op75_tm2_pushes q. If j ≠ k, stack j was unchanged by the push, so its final length is bounded by (S j).length + op75_tm2_pushes q, which is strictly within the allowed bound.
uses
Function.update_self,List.length_cons,Function.update_of_ne| push k f q ih => simp only [Turing.TM2.stepAux, op75_tm2_pushes] have h := ih v (Function.update S k (f v :: S k)) by_cases hj : j = k · subst j simp only [Function.update_self, List.length_cons] at h omega · simp only [Function.update_of_ne hj] at h omegaFor a peek statement `peek k f q`, the length of stack j increases by at most op75_tm2_pushes q.
Peeking at stack k updates only the local state based on the top element (S k).head? and leaves all stacks unmodified. Because the push count for peek is simply op75_tm2_pushes q, the induction hypothesis applied to the updated state and original stacks directly gives the result.
| peek k f q ih => simp only [Turing.TM2.stepAux, op75_tm2_pushes] exact ih _ _For a pop statement `pop k f q`, the length of stack j increases by at most op75_tm2_pushes q.
Popping from stack k updates the state and replaces stack k by its tail, leaving all other stacks unchanged. Applying the induction hypothesis to this new configuration bounds the final length of stack j by (new stack j).length + op75_tm2_pushes q. If j = k, the new stack is the tail, whose length is at most (S k).length; linear arithmetic then closes the inequality. If j ≠ k, stack j was untouched, so the induction hypothesis directly matches the goal.
uses
Function.update_self,Function.update_of_ne| pop k f q ih => simp only [Turing.TM2.stepAux, op75_tm2_pushes] have h := ih (f v (S k).head?) (Function.update S k (S k).tail) by_cases hj : j = k · subst j simp only [Function.update_self] at h have ht : (S k).tail.length ≤ (S k).length := by simp omega · simp only [Function.update_of_ne hj] at h exact hFor a load statement `load f q`, the length of stack j increases by at most op75_tm2_pushes q.
A load instruction updates the local state to f(v) without altering any stacks. The push bound is defined as op75_tm2_pushes q, so applying the induction hypothesis with state f(v) immediately proves the bound.
| load f q ih => simp only [Turing.TM2.stepAux, op75_tm2_pushes] exact ih _ _For a branch statement `branch f q r`, the length of stack j increases by at most max (op75_tm2_pushes q) (op75_tm2_pushes r).
We case-split on the boolean condition f(v). If false, execution proceeds with r, whose push count is bounded by op75_tm2_pushes r ≤ max (op75_tm2_pushes q) (op75_tm2_pushes r). If true, execution proceeds with q, whose push count is bounded by op75_tm2_pushes q ≤ max (op75_tm2_pushes q) (op75_tm2_pushes r). In both cases, the induction hypothesis combined with the maximum inequality yields the result.
uses
le_max_right,le_max_left| branch f q r ihq ihr => simp only [Turing.TM2.stepAux, op75_tm2_pushes] cases hb : f v with | false => change ((Turing.TM2.stepAux r v S).stk j).length ≤ (S j).length + max (op75_tm2_pushes q) (op75_tm2_pushes r) have h := ihr v S have hm := le_max_right (op75_tm2_pushes q) (op75_tm2_pushes r) omega | true => change ((Turing.TM2.stepAux q v S).stk j).length ≤ (S j).length + max (op75_tm2_pushes q) (op75_tm2_pushes r) have h := ihq v S have hm := le_max_left (op75_tm2_pushes q) (op75_tm2_pushes r) omegaFor jump (`goto f`) and termination (`halt`) statements, stacks are unchanged and push bounds are zero.
Both `goto` and `halt` terminate the current step auxiliary execution without altering any stack, and their static push count is defined to be 0. Thus the inequality reduces to (S j).length ≤ (S j).length + 0, which holds trivially.
| goto f => simp [Turing.TM2.stepAux, op75_tm2_pushes] | halt => simp [Turing.TM2.stepAux, op75_tm2_pushes]
Function.update_self- Updating a function at key a with value v and evaluating at a yields v.
Function.update_of_ne- Updating a function at key a' and evaluating at a distinct key a ≠ a' leaves the value at a unchanged.
List.length_cons- The length of a list with an element prepended is one plus the original length: (a :: as).length = as.length + 1.
le_max_right- For any elements a and b in a linear order, b ≤ max a b.
le_max_left- For any elements a and b in a linear order, a ≤ max a b.
- The tactic `omega` is used to discharge linear natural number arithmetic inequalities in the push, pop, and branch cases.
- On line 23, `simp` automatically discharges the list fact that taking the tail of a list does not increase its length.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem op75_tm2_step_aux_length {K : Type} [DecidableEq K] {Γ : K → Type} {Λ σ : Type} (s : Turing.TM2.Stmt Γ Λ σ) (v : σ) (S : ∀ k, List (Γ k)) (j : K) : ((Turing.TM2.stepAux s v S).stk j).length ≤ (S j).length + op75_tm2_pushes s := by induction s generalizing v S with | push k f q ih => simp only [Turing.TM2.stepAux, op75_tm2_pushes] have h := ih v (Function.update S k (f v :: S k)) by_cases hj : j = k · subst j simp only [Function.update_self, List.length_cons] at h omega · simp only [Function.update_of_ne hj] at h omega | peek k f q ih => simp only [Turing.TM2.stepAux, op75_tm2_pushes] exact ih _ _ | pop k f q ih => simp only [Turing.TM2.stepAux, op75_tm2_pushes] have h := ih (f v (S k).head?) (Function.update S k (S k).tail) by_cases hj : j = k · subst j simp only [Function.update_self] at h have ht : (S k).tail.length ≤ (S k).length := by simp omega · simp only [Function.update_of_ne hj] at h exact h | load f q ih => simp only [Turing.TM2.stepAux, op75_tm2_pushes] exact ih _ _ | branch f q r ihq ihr => simp only [Turing.TM2.stepAux, op75_tm2_pushes] cases hb : f v with | false => change ((Turing.TM2.stepAux r v S).stk j).length ≤ (S j).length + max (op75_tm2_pushes q) (op75_tm2_pushes r) have h := ihr v S have hm := le_max_right (op75_tm2_pushes q) (op75_tm2_pushes r) omega | true => change ((Turing.TM2.stepAux q v S).stk j).length ≤ (S j).length + max (op75_tm2_pushes q) (op75_tm2_pushes r) have h := ihq v S have hm := le_max_left (op75_tm2_pushes q) (op75_tm2_pushes r) omega | goto f => simp [Turing.TM2.stepAux, op75_tm2_pushes] | halt => simp [Turing.TM2.stepAux, op75_tm2_pushes]