AFTD Auto-Formalizing Theoretical Domains

op75_tm2_machine_one_step_bound

theoremverified

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.

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

    lines 4–8

      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, ?_⟩
  2. 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.

    lines 9–16

    uses Turing.FinTM2.step, Turing.TM2.step, Option.some.inj

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

    lines 17–19

    uses Finset.le_sup, Finset.mem_univ

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

    line 20

    uses le_trans, op75_tm2_step_aux_length, Nat.add_le_add_left

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

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