op75_tm2_output_linear_bound
For 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 input length plus C times n.
Statement
theorem op75_tm2_output_linear_bound (tm : Turing.FinTM2) :
∃ C : ℕ, ∀ (i : List (tm.Γ tm.k₀)) (o : List (tm.Γ tm.k₁)) (n : ℕ),
Nonempty (Turing.TM2OutputsInTime tm i (some o) n) → o.length ≤ i.length + C*n- 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 4
- 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.
- op75_tm2_iter_measure_boundIf 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…
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- Used by 2
- op75_tm2_poly_output_sizeEvery function computed by a polynomial-time TM2 has output encoding length bounded by a polynomial in its input encoding length.
- op75_karp_bool_transPolynomial-time many-one reductions compose when their intermediate language uses the Boolean alphabet, even if the source and target…
The proof, explained
For any finite TM2 machine, each step can increase the length of the output tape by at most a fixed constant C, as established by op75_tm2_machine_one_step_bound. An iteration lemma (op75_tm2_iter_measure_bound) accumulates this per-step bound over all steps, showing that after k steps the output tape grows by at most C * k. Since the computation halts in at most n steps and starts with at most the input length on the output tape, the final output length is bounded by the input length plus C * n.
There is a constant C bounding the increase in the length of the output tape in any single transition of the machine.
Applying op75_tm2_machine_one_step_bound to the designated output tape tm.k₁ yields a constant C such that any single transition step of tm increases the length of tape tm.k₁ by at most C. We provide this C as the witness for the existential quantifier.
uses
op75_tm2_machine_one_step_boundclassical obtain ⟨C, hstep⟩ := op75_tm2_machine_one_step_bound tm tm.k₁ refine ⟨C, ?_⟩
Assume the machine runs on input i and halts with output o within n steps; let h be the record witnessing this execution in h.steps steps.
We introduce the input list i, output list o, step bound n, and the hypothesis hh asserting that the computation terminates with output o within n steps. Extracting the execution witness h gives the exact step count h.steps and the equation (hiter) stating that iterating the step function h.steps times from Turing.initList tm i produces Turing.haltList tm o.
intro i o n hh obtain ⟨h⟩ := hh have hiter : (fun x : Option tm.Cfg => x.bind tm.step)^[h.steps] (some (Turing.initList tm i)) = some (Turing.haltList tm o) := h.evals_in_steps
After h.steps steps, the length of the output tape is at most its initial length plus C * h.steps.
Using op75_tm2_iter_measure_bound with the measure defined as the length of the stack on tape tm.k₁, the one-step bound C implies that running the machine for h.steps steps from Turing.initList tm i to Turing.haltList tm o increases the length of tape tm.k₁ by at most C * h.steps.
uses
op75_tm2_iter_measure_boundhave hb := op75_tm2_iter_measure_bound tm.step (fun c : tm.Cfg => (c.stk tm.k₁).length) C hstep h.steps (Turing.initList tm i) (Turing.haltList tm o) hiter
The length of the output tape in the halting configuration equals o.length.
By definition of Turing.haltList, the halting configuration places the list o onto tape tm.k₁, so the length of tape tm.k₁ is exactly the length of o.
uses
Turing.haltListhave hout : ((Turing.haltList tm o).stk tm.k₁).length = o.length := by simp [Turing.haltList]
The length of tape tm.k₁ in the initial configuration is at most i.length.
We perform a case analysis on whether the output tape tm.k₁ equals the input tape tm.k₀. If tm.k₁ = tm.k₀, tape tm.k₁ is initialized with list i, so its length is exactly i.length (and thus ≤ i.length by le_of_eq). If tm.k₁ ≠ tm.k₀, tape tm.k₁ is initialized to the empty list with length 0, which is also ≤ i.length.
uses
Turing.initList,le_of_eqhave hin : ((Turing.initList tm i).stk tm.k₁).length ≤ i.length := by by_cases he : tm.k₁ = tm.k₀ · have helper : ∀ k : tm.K, k = tm.k₀ → ((Turing.initList tm i).stk k).length = i.length := by intro k hk subst k simp [Turing.initList] exact le_of_eq (helper tm.k₁ he) · simp [Turing.initList, he]
o.length ≤ i.length + C * n. automation
Substituting the halting tape length o.length into the iterated bound, and combining it with the initial length bound (tape tm.k₁ length ≤ i.length) and the time bound h.steps ≤ n, the final inequality is closed by non-linear arithmetic.
rw [hout] at hb have hs := h.steps_le_m nlinarith
op75_tm2_machine_one_step_bound- For any tape j in a finite TM2 machine, there exists a constant C bounding the increase in length of tape j in a single transition step.
op75_tm2_iter_measure_bound- If each transition step increases a measure on states by at most C, then iterating the transition function for n steps increases the measure by at most C * n.
Turing.haltList- The halting configuration of a TM2 machine for a given output list, which places the list on the designated output tape k₁ and leaves all other tapes empty.
Turing.initList- The initial configuration of a TM2 machine for a given input list, which places the list on the designated input tape k₀ and leaves all other tapes empty.
le_of_eq- If a = b, then a ≤ b in any preorder.
- The formal proof includes a case analysis on whether the output tape k₁ is the same tape as the input tape k₀ to verify that the output tape initially has length at most the input length; on paper, this is typically treated as an obvious initial condition.
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_output_linear_bound (tm : Turing.FinTM2) : ∃ C : ℕ, ∀ (i : List (tm.Γ tm.k₀)) (o : List (tm.Γ tm.k₁)) (n : ℕ), Nonempty (Turing.TM2OutputsInTime tm i (some o) n) → o.length ≤ i.length + C*n := by classical obtain ⟨C, hstep⟩ := op75_tm2_machine_one_step_bound tm tm.k₁ refine ⟨C, ?_⟩ intro i o n hh obtain ⟨h⟩ := hh have hiter : (fun x : Option tm.Cfg => x.bind tm.step)^[h.steps] (some (Turing.initList tm i)) = some (Turing.haltList tm o) := h.evals_in_steps have hb := op75_tm2_iter_measure_bound tm.step (fun c : tm.Cfg => (c.stk tm.k₁).length) C hstep h.steps (Turing.initList tm i) (Turing.haltList tm o) hiter have hout : ((Turing.haltList tm o).stk tm.k₁).length = o.length := by simp [Turing.haltList] have hin : ((Turing.initList tm i).stk tm.k₁).length ≤ i.length := by by_cases he : tm.k₁ = tm.k₀ · have helper : ∀ k : tm.K, k = tm.k₀ → ((Turing.initList tm i).stk k).length = i.length := by intro k hk subst k simp [Turing.initList] exact le_of_eq (helper tm.k₁ he) · simp [Turing.initList, he] rw [hout] at hb have hs := h.steps_le_m nlinarith