op75_tm2_machine_one_step_bound
For any finite TM2 and any of its stacks, some constant bounds that stack’s length increase in every machine step.
Statement
theorem op75_tm2_machine_one_step_bound (tm : Turing.FinTM2) (j : tm.K) :
∃ C : ℕ, ∀ c d : tm.Cfg, tm.step c = some d →
(d.stk j).length ≤ (c.stk j).length + C- 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 2
- op75_tm2_pushesA syntactic upper bound on how many pushes a single TM2 statement can execute, using a maximum at branches.
- op75_tm2_step_aux_lengthExecuting one TM2 statement increases any chosen stack length by at most the syntactic push bound.
- Used by 1
- op75_tm2_output_linear_boundFor any finite TM2, there is a constant C such that for every input and output, a halting run of at most n steps has output length at most…
The proof, explained
Because a finite TM2 machine has only finitely many states, there is a global maximum C on the number of push operations that any of its instructions can execute. Any configuration that can take a step must be in a non-halted state, so the step executes that state's instruction. By an auxiliary bound showing that a single instruction increases any stack's length by at most its push count, the stack length increases by at most C.
There exists a uniform bound C on stack growth, namely the maximum number of pushes across all machine instructions.
We activate classical logic and bring into scope the finiteness of the label set Λ and decidable equality on stack keys tm.K. Because Λ is finite, we define C as the supremum (maximum) of the push count op75_tm2_pushes (tm.m l) over all labels l in the universal finset, and provide C as the witness for the existential quantifier.
classical letI : DecidableEq tm.K := tm.kDecidableEq letI : Fintype tm.Λ := tm.ΛFin let C := Finset.univ.sup (fun l : tm.Λ => op75_tm2_pushes (tm.m l)) refine ⟨C, ?_⟩
In any successful step from configuration c to d, c cannot be halted, and d is the result of executing the statement at c's label via stepAux.
Given configurations c = ⟨label, v, S⟩ and d with tm.step c = some d, we analyze the state label. If label were none, the machine would be halted and the step would evaluate to none, contradicting the assumption that a next configuration exists. Thus label is some active state, and unfolding tm.step equates some d with some (Turing.TM2.stepAux (tm.m label) v S). Injectivity of some allows substituting this auxiliary step result for d.
uses
Turing.FinTM2.step,Turing.TM2.step,Option.some.injintro c d h rcases c with ⟨label, v, S⟩ cases label with | none => simp [Turing.FinTM2.step, Turing.TM2.step] at h | some label => change some (Turing.TM2.stepAux (tm.m label) v S) = some d at h have hd := Option.some.inj h subst d
The push count of instruction tm.m label is bounded by C.
By definition, C is the supremum of push counts across all labels in Finset.univ. Because label is an element of Finset.univ, Finset.le_sup immediately yields op75_tm2_pushes (tm.m label) ≤ C.
uses
Finset.le_sup,Finset.mem_univhave hm : op75_tm2_pushes (tm.m label) ≤ C := by dsimp [C] exact Finset.le_sup (f := fun l : tm.Λ => op75_tm2_pushes (tm.m l)) (Finset.mem_univ label)
The length of stack j after the step is at most its initial length plus C.
The lemma op75_tm2_step_aux_length bounds the growth of stack j under stepAux by the push count of the instruction tm.m label. Adding the initial stack length preserves the inequality (Nat.add_le_add_left), and transitivity (le_trans) with the bound on pushes completes the proof.
uses
le_trans,op75_tm2_step_aux_length,Nat.add_le_add_leftexact le_trans (op75_tm2_step_aux_length (tm.m label) v S j) (Nat.add_le_add_left hm _)
Turing.FinTM2.step- The step function of a finite TM2 machine, mapping a machine and a configuration to the successor configuration, or none if halted.
Turing.TM2.step- The core TM2 step function, executing the statement mapped to by the current state label, or halting if the label is none.
Option.some.inj- The constructor Option.some is injective: if some x = some y, then x = y.
Finset.le_sup- For any element b in a finite set s, f b is less than or equal to the supremum of f over s.
Finset.mem_univ- Every element of a finite type belongs to its universal finset Finset.univ.
le_trans- The relation ≤ is transitive: if a ≤ b and b ≤ c, then a ≤ c.
op75_tm2_step_aux_length- Executing a TM2 statement s increases the length of any stack j by at most the number of push operations in s.
Nat.add_le_add_left- Addition on natural numbers preserves inequality: if n ≤ m, then k + n ≤ k + m for any k.
- Lines 5–6 locally register typeclass instances for decidable equality of stack indices and finiteness of the state type, which are bundled fields of the finite machine definition needed to form the supremum over Finset.univ.
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_machine_one_step_bound (tm : Turing.FinTM2) (j : tm.K) : ∃ C : ℕ, ∀ c d : tm.Cfg, tm.step c = some d → (d.stk j).length ≤ (c.stk j).length + C := by classical letI : DecidableEq tm.K := tm.kDecidableEq letI : Fintype tm.Λ := tm.ΛFin let C := Finset.univ.sup (fun l : tm.Λ => op75_tm2_pushes (tm.m l)) refine ⟨C, ?_⟩ intro c d h rcases c with ⟨label, v, S⟩ cases label with | none => simp [Turing.FinTM2.step, Turing.TM2.step] at h | some label => change some (Turing.TM2.stepAux (tm.m label) v S) = some d at h have hd := Option.some.inj h subst d have hm : op75_tm2_pushes (tm.m label) ≤ C := by dsimp [C] exact Finset.le_sup (f := fun l : tm.Λ => op75_tm2_pushes (tm.m l)) (Finset.mem_univ label) exact le_trans (op75_tm2_step_aux_length (tm.m label) v S j) (Nat.add_le_add_left hm _)