AFTD Auto-Formalizing Theoretical Domains

op75_tm2_output_linear_bound

theoremverified

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
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.

  1. 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.

    lines 4–6

    uses op75_tm2_machine_one_step_bound

      classical
      obtain ⟨C, hstep⟩ := op75_tm2_machine_one_step_bound tm tm.k₁
      refine ⟨C, ?_⟩
  2. 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.

    lines 7–10

      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
  3. 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.

    lines 11–12

    uses op75_tm2_iter_measure_bound

      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
  4. 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.

    lines 13–14

    uses Turing.haltList

      have hout : ((Turing.haltList tm o).stk tm.k₁).length = o.length := by
        simp [Turing.haltList]
  5. 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.

    lines 15–22

    uses Turing.initList, le_of_eq

      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]
  6. 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.

    lines 23–25

      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.

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

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