op75_tm2_iter_measure_bound
If every transition of a partial state machine increases a natural-valued measure by at most C, then any n-step run increases it by at most C times n.
Statement
theorem op75_tm2_iter_measure_bound {α : Type} (f : α → Option α) (measure : α → ℕ) (C : ℕ) (hstep : ∀ a b, f a = some b → measure b ≤ measure a + C) (n : ℕ) (a b : α) (h : ((fun o : Option α => o.bind f))^[n] (some a) = some b) : measure b ≤ measure a + C*n
- Source
- OP-75 Karp-reduction composition: finite-statement stack-growth bound in the repository TM2 model.
- Verified
- 15 Nov 2026
- Axioms
Quot.soundpropext- 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
The theorem is proved by induction on the number of steps n, generalizing over the final state b. For n = 0, the state is unchanged (a = b) and the bound is trivial. For n + 1 steps, the run is decomposed into an n-step prefix reaching an intermediate state mid followed by one final step to b; applying the induction hypothesis to the prefix and the single-step bound to the last transition gives the result by linear arithmetic.
The base case n = 0 holds because running zero steps leaves the state unchanged, so a = b.
We proceed by induction on n, keeping the destination b general. In the base case n = 0, applying zero transitions is the identity function (Function.iterate_zero, id_eq), reducing the run hypothesis to some a = some b. By injectivity of the some constructor (Option.some.inj), we have a = b. The goal then simplifies to measure a ≤ measure a + C * 0, which holds trivially.
uses
Function.iterate_zero,id_eq,Option.some.injinduction n generalizing b with | zero => simp only [Function.iterate_zero, id_eq] at h cases Option.some.inj h simp
In the inductive step for n + 1, the computation factors into an n-step run reaching an intermediate state mid and a final step from mid to b.
For n + 1 iterations, we rewrite the (n + 1)-fold application as the transition f applied to the result of n iterations (Function.iterate_succ_apply'). We then case-split on whether the first n steps terminate in none or reach some state mid. If they yielded none, binding f would immediately yield none, contradicting the assumption that the run reached some b. Therefore, after n steps the state must be some mid.
uses
Function.iterate_succ_apply'| succ n ih => rw [Function.iterate_succ_apply'] at h cases hp : ((fun o : Option α => o.bind f))^[n] (some a) with | none => simp [hp] at h | some mid =>The measure of mid is bounded by measure a + C * n, and the measure of b is bounded by measure mid + C.
Applying the induction hypothesis (ih) to the n-step run reaching mid bounds the measure of mid by measure a + C * n. Simplifying the full run equation with this intermediate state reveals that the final transition is f mid = some b. Applying the assumption on single transitions (hstep) to this final step gives measure b ≤ measure mid + C.
have hm := ih mid hp have hf : f mid = some b := by simpa [hp] using h have hs := hstep mid b hf
The bound measure b ≤ measure a + C * (n + 1) follows by linear arithmetic.
Rewriting C * (n + 1) as C * n + C (Nat.mul_succ) and combining the bound on mid from the induction hypothesis with the single-step bound from mid to b yields the desired inequality by linear arithmetic (omega).
uses
Nat.mul_succsimp only [Nat.mul_succ] omega
Function.iterate_zero- Iterating any function zero times is the identity function: f^[0] = id.
id_eq- Applying the identity function returns the argument unchanged: id a = a.
Option.some.inj- The some constructor is injective: some x = some y implies x = y.
Function.iterate_succ_apply'- Iterating a function n + 1 times equals applying it once to the result of iterating it n times: f^[n + 1] x = f (f^[n] x).
Nat.mul_succ- Multiplication distributes over successor for natural numbers: n * (m + 1) = n * m + n.
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_iter_measure_bound {α : Type} (f : α → Option α) (measure : α → ℕ) (C : ℕ) (hstep : ∀ a b, f a = some b → measure b ≤ measure a + C) (n : ℕ) (a b : α) (h : ((fun o : Option α => o.bind f))^[n] (some a) = some b) : measure b ≤ measure a + C*n := by induction n generalizing b with | zero => simp only [Function.iterate_zero, id_eq] at h cases Option.some.inj h simp | succ n ih => rw [Function.iterate_succ_apply'] at h cases hp : ((fun o : Option α => o.bind f))^[n] (some a) with | none => simp [hp] at h | some mid => have hm := ih mid hp have hf : f mid = some b := by simpa [hp] using h have hs := hstep mid b hf simp only [Nat.mul_succ] omega