AFTD Auto-Formalizing Theoretical Domains

op75_tm2_empty_comp

theoremverified

Polynomial-time finite stack machines compose when their intermediate alphabet is empty, for arbitrary input and output alphabets.

Statement

theorem op75_tm2_empty_comp {Γ₀ Γ₁ Γ₂ : Type} [IsEmpty Γ₁] {f : List Γ₀ → List Γ₁} {g : List Γ₁ → List Γ₂} :
    Nonempty (Turing.TM2ComputableInPolyTime (id : List Γ₀ → List Γ₀) (id : List Γ₁ → List Γ₁) f) →
    Nonempty (Turing.TM2ComputableInPolyTime (id : List Γ₁ → List Γ₁) (id : List Γ₂ → List Γ₂) g) →
    Nonempty (Turing.TM2ComputableInPolyTime (id : List Γ₀ → List Γ₀) (id : List Γ₂ → List Γ₂) (g ∘ f))
Source
OP-75: the empty-intermediate-alphabet case of machine composition
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
  • op75_tm2_bool_compPolynomial-time finite stack machines compose when their intermediate alphabet is Boolean, for arbitrary input and output alphabets.
  • Cslib.SKI.Polynomial.evalSubstitute terms for the free variables of a polynomial
Used by 1
  • op75_karp_reducible_transPolynomial-time many-one reducibility is transitive for languages over arbitrary alphabets under the repository TM2 definition.

Lean source view module on GitHub

open Turing Turing.TM2

namespace Op75EmptyComposition

variable {Γ₀ Γ₁ Γ₂ : Type} [IsEmpty Γ₁]
variable {f : List Γ₀ → List Γ₁} {g : List Γ₁ → List Γ₂}
variable (A : Turing.TM2ComputableInPolyTime (id : List Γ₀ → List Γ₀) (id : List Γ₁ → List Γ₁) f)
variable (B : Turing.TM2ComputableInPolyTime (id : List Γ₁ → List Γ₁) (id : List Γ₂ → List Γ₂) g)

abbrev Stacks := Sum A.tm.K B.tm.K
abbrev Labels := Sum A.tm.Λ B.tm.Λ
abbrev State := A.tm.σ × B.tm.σ
abbrev Alphabet : Stacks A B → Type := Sum.elim A.tm.Γ B.tm.Γ

def liftFirst : Turing.TM2.Stmt A.tm.Γ A.tm.Λ A.tm.σ →
    Turing.TM2.Stmt (Alphabet A B) (Labels A B) (State A B)
  | .push k h q => .push (.inl k) (fun v => h v.1) (liftFirst q)
  | .peek k h q => .peek (.inl k) (fun v x => (h v.1 x, v.2)) (liftFirst q)
  | .pop k h q => .pop (.inl k) (fun v x => (h v.1 x, v.2)) (liftFirst q)
  | .load h q => .load (fun v => (h v.1, v.2)) (liftFirst q)
  | .branch h q r => .branch (fun v => h v.1) (liftFirst q) (liftFirst r)
  | .goto h => .goto (fun v => .inl (h v.1))
  | .halt => .goto (fun _ => .inr B.tm.main)

def liftSecond : Turing.TM2.Stmt B.tm.Γ B.tm.Λ B.tm.σ →
    Turing.TM2.Stmt (Alphabet A B) (Labels A B) (State A B)
  | .push k h q => .push (.inr k) (fun v => h v.2) (liftSecond q)
  | .peek k h q => .peek (.inr k) (fun v x => (v.1, h v.2 x)) (liftSecond q)
  | .pop k h q => .pop (.inr k) (fun v x => (v.1, h v.2 x)) (liftSecond q)
  | .load h q => .load (fun v => (v.1, h v.2)) (liftSecond q)
  | .branch h q r => .branch (fun v => h v.2) (liftSecond q) (liftSecond r)
  | .goto h => .goto (fun v => .inr (h v.2))
  | .halt => .halt

noncomputable def machine : Turing.FinTM2 := by
  letI : DecidableEq A.tm.K := A.tm.kDecidableEq
  letI : DecidableEq B.tm.K := B.tm.kDecidableEq
  letI : Fintype A.tm.K := A.tm.kFin
  letI : Fintype B.tm.K := B.tm.kFin
  letI : Fintype A.tm.Λ := A.tm.ΛFin
  letI : Fintype B.tm.Λ := B.tm.ΛFin
  letI : Fintype A.tm.σ := A.tm.σFin
  letI : Fintype B.tm.σ := B.tm.σFin
  letI : Fintype (Alphabet A B (.inl A.tm.k₀)) := A.tm.Γk₀Fin
  exact {
    K := Stacks A B
    k₀ := .inl A.tm.k₀
    k₁ := .inr B.tm.k₁
    Γ := Alphabet A B
    Λ := Labels A B
    main := .inl A.tm.main
    σ := State A B
    initialState := (A.tm.initialState, B.tm.initialState)
    m := fun l => match l with
      | .inl a => liftFirst A B (A.tm.m a)
      | .inr b => liftSecond A B (B.tm.m b) }

def firstStacks (S : ∀ k, List (A.tm.Γ k)) : ∀ k, List (Alphabet A B k)
  | .inl k => S k
  | .inr _ => []

theorem firstStacks_update (S : ∀ k, List (A.tm.Γ k)) (k : A.tm.K) (xs : List (A.tm.Γ k)) :
    firstStacks A B (Function.update S k xs) = Function.update (firstStacks A B S) (.inl k) xs := by
  classical
  funext j
  cases j with
  | inl j =>
      by_cases h : j = k
      · subst j; simp [Function.update, firstStacks] <;> rfl
      · simp [Function.update, firstStacks, h] <;> rfl
  | inr j => simp [Function.update, firstStacks]

def firstCfg (v : A.tm.σ) (S : ∀ k, List (A.tm.Γ k)) (l : Option A.tm.Λ) :
    (machine A B).Cfg where
  l := match l with
    | some x => some (.inl x)
    | none => some (.inr B.tm.main)
  var := (v, B.tm.initialState)
  stk := firstStacks A B S

theorem liftFirst_stepAux (q : Turing.TM2.Stmt A.tm.Γ A.tm.Λ A.tm.σ)
    (v : A.tm.σ) (S : ∀ k, List (A.tm.Γ k)) :
    Turing.TM2.stepAux (liftFirst A B q) (v, B.tm.initialState) (firstStacks A B S) =
      firstCfg A B (Turing.TM2.stepAux q v S).var (Turing.TM2.stepAux q v S).stk
        (Turing.TM2.stepAux q v S).l := by
  classical
  induction q generalizing v S with
  | push k h q ih =>
      simp only [liftFirst, Turing.TM2.stepAux]
      have hh := ih v (Function.update S k (h v :: S k))
      simp only [firstStacks_update] at hh
      convert hh using 1 <;> rfl
  | peek k h q ih => simp only [liftFirst, Turing.TM2.stepAux, firstStacks]; exact ih _ _
  | pop k h q ih =>
      simp only [liftFirst, Turing.TM2.stepAux, firstStacks]
      have hh := ih (h v (S k).head?) (Function.update S k (S k).tail)
      simp only [firstStacks_update] at hh
      exact hh
  | load h q ih => simp only [liftFirst, Turing.TM2.stepAux]; exact ih _ _
  | branch h q r ihq ihr =>
      simp only [liftFirst, Turing.TM2.stepAux]
      cases hv : h v <;> simp only [hv, Bool.false_eq_true, cond_false, cond_true] <;> first | exact ihq v S | exact ihr v S
  | goto h => rfl
  | halt => rfl

def secondStacks (S : ∀ k, List (B.tm.Γ k)) : ∀ k, List (Alphabet A B k)
  | .inl _ => []
  | .inr k => S k

theorem secondStacks_update (S : ∀ k, List (B.tm.Γ k)) (k : B.tm.K) (xs : List (B.tm.Γ k)) :
    secondStacks A B (Function.update S k xs) = Function.update (secondStacks A B S) (.inr k) xs := by
  classical
  funext j
  cases j with
  | inl j => simp [Function.update, secondStacks]
  | inr j =>
      by_cases h : j = k
      · subst j; simp [Function.update, secondStacks] <;> rfl
      · simp [Function.update, secondStacks, h] <;> rfl

def secondCfg (v : B.tm.σ) (S : ∀ k, List (B.tm.Γ k)) (l : Option B.tm.Λ) :
    (machine A B).Cfg where
  l := l.map Sum.inr
  var := (A.tm.initialState, v)
  stk := secondStacks A B S

theorem liftSecond_stepAux (q : Turing.TM2.Stmt B.tm.Γ B.tm.Λ B.tm.σ)
    (v : B.tm.σ) (S : ∀ k, List (B.tm.Γ k)) :
    Turing.TM2.stepAux (liftSecond A B q) (A.tm.initialState, v) (secondStacks A B S) =
      secondCfg A B (Turing.TM2.stepAux q v S).var (Turing.TM2.stepAux q v S).stk
        (Turing.TM2.stepAux q v S).l := by
  classical
  induction q generalizing v S with
  | push k h q ih =>
      simp only [liftSecond, Turing.TM2.stepAux]
      have hh := ih v (Function.update S k (h v :: S k))
      simp only [secondStacks_update] at hh
      convert hh using 1 <;> rfl
  | peek k h q ih => simp only [liftSecond, Turing.TM2.stepAux, secondStacks]; exact ih _ _
  | pop k h q ih =>
      simp only [liftSecond, Turing.TM2.stepAux, secondStacks]
      have hh := ih (h v (S k).head?) (Function.update S k (S k).tail)
      simp only [secondStacks_update] at hh
      exact hh
  | load h q ih => simp only [liftSecond, Turing.TM2.stepAux]; exact ih _ _
  | branch h q r ihq ihr =>
      simp only [liftSecond, Turing.TM2.stepAux]
      cases hv : h v <;> simp only [hv, Bool.false_eq_true, cond_false, cond_true] <;> first | exact ihq v S | exact ihr v S
  | goto h => rfl
  | halt => rfl

def packFirst (c : A.tm.Cfg) := firstCfg A B c.var c.stk c.l
def packSecond (c : B.tm.Cfg) := secondCfg A B c.var c.stk c.l

theorem packFirst_step (c d : A.tm.Cfg) (h : A.tm.step c = some d) :
    (machine A B).step (packFirst A B c) = some (packFirst A B d) := by
  rcases c with ⟨label, v, S⟩
  cases label with
  | none => simp [Turing.FinTM2.step, Turing.TM2.step] at h
  | some l =>
      change some (Turing.TM2.stepAux (A.tm.m l) v S) = some d at h
      cases Option.some.inj h
      change some (Turing.TM2.stepAux (liftFirst A B (A.tm.m l)) _ _) = _
      exact congrArg some (liftFirst_stepAux A B (A.tm.m l) v S)

theorem packSecond_step (c d : B.tm.Cfg) (h : B.tm.step c = some d) :
    (machine A B).step (packSecond A B c) = some (packSecond A B d) := by
  rcases c with ⟨label, v, S⟩
  cases label with
  | none => simp [Turing.FinTM2.step, Turing.TM2.step] at h
  | some l =>
      change some (Turing.TM2.stepAux (B.tm.m l) v S) = some d at h
      cases Option.some.inj h
      change some (Turing.TM2.stepAux (liftSecond A B (B.tm.m l)) _ _) = _
      exact congrArg some (liftSecond_stepAux A B (B.tm.m l) v S)

theorem packFirst_init (xs : List (A.tm.Γ A.tm.k₀)) :
    packFirst A B (Turing.initList A.tm xs) = Turing.initList (machine A B) xs := by
  classical
  simp [packFirst, firstCfg, firstStacks, Turing.initList, machine]
  congr 1
  funext k
  cases k with
  | inl k => by_cases h : k = A.tm.k₀ <;> simp [firstStacks, Turing.initList, h] <;> rfl
  | inr k => simp [firstStacks, Turing.initList]

theorem empty_transition :
    packFirst A B (Turing.haltList A.tm []) = packSecond A B (Turing.initList B.tm []) := by
  classical
  simp [packFirst, packSecond, firstCfg, secondCfg, firstStacks, secondStacks,
    Turing.haltList, Turing.initList]
  congr 1
  funext k
  cases k with
  | inl k =>
      by_cases h : k = A.tm.k₁
      · subst k; simp [firstStacks, secondStacks, Turing.haltList, Turing.initList]
      · simp [firstStacks, secondStacks, Turing.haltList, Turing.initList, h]
  | inr k =>
      by_cases h : k = B.tm.k₀
      · subst k; simp [firstStacks, secondStacks, Turing.haltList, Turing.initList]
      · simp [firstStacks, secondStacks, Turing.haltList, Turing.initList, h]

theorem packSecond_halt (zs : List (B.tm.Γ B.tm.k₁)) :
    packSecond A B (Turing.haltList B.tm zs) = Turing.haltList (machine A B) zs := by
  classical
  simp [packSecond, secondCfg, secondStacks, Turing.haltList, machine]
  congr 1
  funext k
  cases k with
  | inl k => simp [secondStacks, Turing.haltList]
  | inr k => by_cases h : k = B.tm.k₁ <;> simp [secondStacks, Turing.haltList, h] <;> rfl

theorem output_nil (a : List Γ₀) : f a = [] := by
  cases h : f a with
  | nil => rfl
  | cons x xs => exact isEmptyElim x

noncomputable def composed_run (a : List Γ₀) :
    Turing.TM2OutputsInTime (machine A B) (a.map A.inputAlphabet.invFun)
      (some ((g (f a)).map B.outputAlphabet.invFun))
      ((B.outputsFun (f a)).steps + (A.outputsFun a).steps) := by
  let u := a.map A.inputAlphabet.invFun
  let w := (g (f a)).map B.outputAlphabet.invFun
  have hA := Op75BoolComposition.iter_simulation A.tm.step (machine A B).step (packFirst A B)
    (packFirst_step A B) (A.outputsFun a).steps (Turing.initList A.tm u)
    (Turing.haltList A.tm ((f a).map A.outputAlphabet.invFun)) (A.outputsFun a).evals_in_steps
  simp only [output_nil (f := f) a, List.map_nil] at hA
  rw [packFirst_init, empty_transition] at hA
  have hB := Op75BoolComposition.iter_simulation B.tm.step (machine A B).step (packSecond A B)
    (packSecond_step A B) (B.outputsFun (f a)).steps
    (Turing.initList B.tm ((f a).map B.inputAlphabet.invFun)) (Turing.haltList B.tm w)
    (B.outputsFun (f a)).evals_in_steps
  simp only [output_nil (f := f) a, List.map_nil] at hB
  rw [packSecond_halt] at hB
  refine ⟨⟨(B.outputsFun (f a)).steps + (A.outputsFun a).steps, ?_⟩, le_rfl⟩
  change (fun x : Option (machine A B).Cfg => x.bind (machine A B).step)^[_]
    (some (Turing.initList (machine A B) u)) = some (Turing.haltList (machine A B) w)
  rw [Function.iterate_add_apply, hA, hB]

noncomputable def composePoly : Turing.TM2ComputableInPolyTime
    (id : List Γ₀ → List Γ₀) (id : List Γ₂ → List Γ₂) (g ∘ f) := by
  classical
  refine { tm := machine A B
           inputAlphabet := A.inputAlphabet
           outputAlphabet := B.outputAlphabet
           time := A.time + Polynomial.C (B.time.eval 0)
           outputsFun := ?_ }
  intro a
  let run := composed_run A B a
  refine ⟨run.toEvalsTo, ?_⟩
  have hA := (A.outputsFun a).steps_le_m
  have hB := (B.outputsFun (f a)).steps_le_m
  have hflen : (f a).length = 0 := by rw [output_nil (f := f) a]; rfl
  simp only [id_eq, hflen] at hA hB
  simp only [Polynomial.eval_add, Polynomial.eval_C, id_eq]
  change (B.outputsFun (f a)).steps + (A.outputsFun a).steps ≤
    A.time.eval a.length + B.time.eval 0
  omega

end Op75EmptyComposition

theorem op75_tm2_empty_comp {Γ₀ Γ₁ Γ₂ : Type} [IsEmpty Γ₁] {f : List Γ₀ → List Γ₁} {g : List Γ₁ → List Γ₂} :
    Nonempty (Turing.TM2ComputableInPolyTime (id : List Γ₀ → List Γ₀) (id : List Γ₁ → List Γ₁) f) →
    Nonempty (Turing.TM2ComputableInPolyTime (id : List Γ₁ → List Γ₁) (id : List Γ₂ → List Γ₂) g) →
    Nonempty (Turing.TM2ComputableInPolyTime (id : List Γ₀ → List Γ₀) (id : List Γ₂ → List Γ₂) (g ∘ f)) := by
  rintro ⟨A⟩ ⟨B⟩
  exact ⟨Op75EmptyComposition.composePoly A B⟩
See it in the graphDiscuss this resultChallenge it