op75_tm2_inhabited_comp
theoremverified
Polynomial-time finite stack machines compose whenever their intermediate alphabet is inhabited; the input and output alphabets are arbitrary.
Statement
theorem op75_tm2_inhabited_comp {Γ₀ Γ₁ Γ₂ : Type} [Inhabited Γ₁] {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: generalization of op75_tm2_bool_comp to inhabited finite intermediate alphabets
- Verified
- 15 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 3
- 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.
- monomialFor a natural number s and a finite subset T of Fin s, the monomial associated with T is the function from (Fin s → ZMod 2) to ZMod 2…
- 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 Op75GeneralComposition variable {Γ₀ Γ₁ Γ₂ : Type} [Inhabited Γ₁] {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 (Sum B.tm.K Unit) abbrev Labels := Sum A.tm.Λ (Sum B.tm.Λ Bool) abbrev State := A.tm.σ × B.tm.σ × Option Γ₁ abbrev Alphabet : Stacks A B → Type | .inl k => A.tm.Γ k | .inr (.inl k) => B.tm.Γ k | .inr (.inr _) => Γ₁ 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 (.inr false)) 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 (.inl k)) (fun v => h v.2.1) (liftSecond q) | .peek k h q => .peek (.inr (.inl k)) (fun v x => (v.1, h v.2.1 x, v.2.2)) (liftSecond q) | .pop k h q => .pop (.inr (.inl k)) (fun v x => (v.1, h v.2.1 x, v.2.2)) (liftSecond q) | .load h q => .load (fun v => (v.1, h v.2.1, v.2.2)) (liftSecond q) | .branch h q r => .branch (fun v => h v.2.1) (liftSecond q) (liftSecond r) | .goto h => .goto (fun v => .inr (.inl (h v.2.1))) | .halt => .halt def copyFirst : Turing.TM2.Stmt (Alphabet A B) (Labels A B) (State A B) := .pop (.inl A.tm.k₁) (fun v x => (v.1, v.2.1, x.map A.outputAlphabet)) (.branch (fun v => v.2.2.isSome) (.push (.inr (.inr ())) (fun v => v.2.2.getD default) (.goto (fun _ => .inr (.inr false)))) (.goto (fun _ => .inr (.inr true)))) def copySecond : Turing.TM2.Stmt (Alphabet A B) (Labels A B) (State A B) := .pop (.inr (.inr ())) (fun v x => (v.1, v.2.1, x)) (.branch (fun v => v.2.2.isSome) (.push (.inr (.inl B.tm.k₀)) (fun v => B.inputAlphabet.invFun (v.2.2.getD default)) (.goto (fun _ => .inr (.inr true)))) (.goto (fun _ => .inr (.inl B.tm.main)))) 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 (B.tm.Γ B.tm.k₀) := B.tm.Γk₀Fin letI : Fintype Γ₁ := Fintype.ofEquiv (B.tm.Γ B.tm.k₀) B.inputAlphabet 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 (.inl B.tm.k₁) Γ := Alphabet A B Λ := Labels A B main := .inl A.tm.main σ := State A B initialState := (A.tm.initialState, B.tm.initialState, none) m := fun l => match l with | .inl a => liftFirst A B (A.tm.m a) | .inr (.inl b) => liftSecond A B (B.tm.m b) | .inr (.inr false) => copyFirst A B | .inr (.inr true) => copySecond A B } end Op75GeneralComposition namespace Op75GeneralComposition variable {Γ₀ Γ₁ Γ₂ : Type} [Inhabited Γ₁] {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) 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 (.inr false)) var := (v, B.tm.initialState, none) 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, none) (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 end Op75GeneralComposition namespace Op75GeneralComposition variable {Γ₀ Γ₁ Γ₂ : Type} [Inhabited Γ₁] {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) def secondStacks (S : ∀ k, List (B.tm.Γ k)) : ∀ k, List (Alphabet A B k) | .inl _ => [] | .inr (.inl k) => S k | .inr (.inr _) => [] 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 (.inl k)) xs := by classical funext j cases j with | inl j => simp [Function.update, secondStacks] | inr j => cases j with | inl j => by_cases h : j = k · subst j simp [Function.update, secondStacks] <;> rfl · simp [Function.update, secondStacks, h] <;> rfl | inr j => simp [Function.update, secondStacks] def secondCfg (v : B.tm.σ) (S : ∀ k, List (B.tm.Γ k)) (l : Option B.tm.Λ) : (machine A B).Cfg where l := l.map (fun x => .inr (.inl x)) var := (A.tm.initialState, v, none) 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, none) (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 end Op75GeneralComposition namespace Op75GeneralComposition variable {Γ₀ Γ₁ Γ₂ : Type} [Inhabited Γ₁] {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) theorem firstMachine_step (l : A.tm.Λ) (v : A.tm.σ) (S : ∀ k, List (A.tm.Γ k)) : (machine A B).step (firstCfg A B v S (some l)) = some (firstCfg A B (Turing.TM2.stepAux (A.tm.m l) v S).var (Turing.TM2.stepAux (A.tm.m l) v S).stk (Turing.TM2.stepAux (A.tm.m l) v S).l) := by change some (Turing.TM2.stepAux (liftFirst A B (A.tm.m l)) _ _) = _ rw [liftFirst_stepAux] rfl theorem secondMachine_step (l : B.tm.Λ) (v : B.tm.σ) (S : ∀ k, List (B.tm.Γ k)) : (machine A B).step (secondCfg A B v S (some l)) = some (secondCfg A B (Turing.TM2.stepAux (B.tm.m l) v S).var (Turing.TM2.stepAux (B.tm.m l) v S).stk (Turing.TM2.stepAux (B.tm.m l) v S).l) := by change some (Turing.TM2.stepAux (liftSecond A B (B.tm.m l)) _ _) = _ rw [liftSecond_stepAux] rfl end Op75GeneralComposition namespace Op75GeneralComposition variable {Γ₀ Γ₁ Γ₂ : Type} [Inhabited Γ₁] {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) 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 exact firstMachine_step A B 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 exact secondMachine_step A B l v S theorem iter_simulation {α β : Type} (f : α → Option α) (g : β → Option β) (e : α → β) (hs : ∀ c d, f c = some d → g (e c) = some (e d)) (n : ℕ) (c d : α) (h : (fun x : Option α => x.bind f)^[n] (some c) = some d) : (fun x : Option β => x.bind g)^[n] (some (e c)) = some (e d) := by induction n generalizing d with | zero => simp only [Function.iterate_zero, id_eq, Option.some.injEq] at h subst d rfl | succ n ih => rw [Function.iterate_succ_apply'] at h ⊢ cases hm : (fun x : Option α => x.bind f)^[n] (some c) with | none => simp [hm] at h | some m => have he := ih m hm simp only [he, Option.bind_some] exact hs m d (by simpa [hm] using h) end Op75GeneralComposition namespace Op75GeneralComposition variable {Γ₀ Γ₁ Γ₂ : Type} [Inhabited Γ₁] {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) noncomputable def transferStacks (xs : List (A.tm.Γ A.tm.k₁)) (ys : List Γ₁) (zs : List (B.tm.Γ B.tm.k₀)) : ∀ k, List (Alphabet A B k) := by classical intro k cases k with | inl k => exact if h : k = A.tm.k₁ then (by subst k; exact xs) else [] | inr k => cases k with | inl k => exact if h : k = B.tm.k₀ then (by subst k; exact zs) else [] | inr _ => exact ys noncomputable def transferCfg (phase : Bool) (x : Option Γ₁) (xs : List (A.tm.Γ A.tm.k₁)) (ys : List Γ₁) (zs : List (B.tm.Γ B.tm.k₀)) : (machine A B).Cfg where l := some (.inr (.inr phase)) var := (A.tm.initialState, B.tm.initialState, x) stk := transferStacks A B xs ys zs theorem transferFirst_aux (a : A.tm.Γ A.tm.k₁) (xs : List (A.tm.Γ A.tm.k₁)) (ys : List Γ₁) (x : Option Γ₁) : Turing.TM2.stepAux (copyFirst A B) (A.tm.initialState, B.tm.initialState, x) (transferStacks A B (a :: xs) ys []) = ⟨some (.inr (.inr false)), (A.tm.initialState, B.tm.initialState, some (A.outputAlphabet a)), transferStacks A B xs (A.outputAlphabet a :: ys) []⟩ := by classical simp [copyFirst, Turing.TM2.stepAux, transferStacks, Function.update] congr 1 funext k cases k with | inl k => by_cases h : k = A.tm.k₁ · subst k simp [transferStacks, Function.update] · simp [transferStacks, Function.update, h] | inr k => cases k with | inl k => by_cases h : k = B.tm.k₀ <;> simp [transferStacks, Function.update, h] <;> rfl | inr k => cases k <;> simp [transferStacks, Function.update] <;> rfl theorem transferFirst_nil (ys : List Γ₁) (x : Option Γ₁) : Turing.TM2.stepAux (copyFirst A B) (A.tm.initialState, B.tm.initialState, x) (transferStacks A B [] ys []) = ⟨some (.inr (.inr true)), (A.tm.initialState, B.tm.initialState, none), transferStacks A B [] ys []⟩ := by classical simp [copyFirst, Turing.TM2.stepAux, transferStacks, Function.update] theorem transferSecond_aux (b : Γ₁) (ys : List Γ₁) (zs : List (B.tm.Γ B.tm.k₀)) (x : Option Γ₁) : Turing.TM2.stepAux (copySecond A B) (A.tm.initialState, B.tm.initialState, x) (transferStacks A B [] (b :: ys) zs) = ⟨some (.inr (.inr true)), (A.tm.initialState, B.tm.initialState, some b), transferStacks A B [] ys (B.inputAlphabet.invFun b :: zs)⟩ := by classical simp [copySecond, Turing.TM2.stepAux, transferStacks, Function.update] congr 1 funext k cases k with | inl k => by_cases h : k = A.tm.k₁ <;> simp [transferStacks, Function.update, h] | inr k => cases k with | inl k => by_cases h : k = B.tm.k₀ · subst k simp [transferStacks, Function.update] · simp [transferStacks, Function.update, h] | inr k => cases k <;> simp [transferStacks, Function.update] theorem transferSecond_nil (zs : List (B.tm.Γ B.tm.k₀)) (x : Option Γ₁) : Turing.TM2.stepAux (copySecond A B) (A.tm.initialState, B.tm.initialState, x) (transferStacks A B [] [] zs) = ⟨some (.inr (.inl B.tm.main)), (A.tm.initialState, B.tm.initialState, none), transferStacks A B [] [] zs⟩ := by classical simp [copySecond, Turing.TM2.stepAux, transferStacks, Function.update] theorem transferFirst_step (a : A.tm.Γ A.tm.k₁) (xs : List (A.tm.Γ A.tm.k₁)) (ys : List Γ₁) (x : Option Γ₁) : (machine A B).step (transferCfg A B false x (a :: xs) ys []) = some (transferCfg A B false (some (A.outputAlphabet a)) xs (A.outputAlphabet a :: ys) []) := by change some (Turing.TM2.stepAux (copyFirst A B) _ _) = _ exact congrArg some (transferFirst_aux A B a xs ys x) theorem transferFirst_finish (ys : List Γ₁) (x : Option Γ₁) : (machine A B).step (transferCfg A B false x [] ys []) = some (transferCfg A B true none [] ys []) := by change some (Turing.TM2.stepAux (copyFirst A B) _ _) = _ exact congrArg some (transferFirst_nil A B ys x) theorem transferSecond_step (b : Γ₁) (ys : List Γ₁) (zs : List (B.tm.Γ B.tm.k₀)) (x : Option Γ₁) : (machine A B).step (transferCfg A B true x [] (b :: ys) zs) = some (transferCfg A B true (some b) [] ys (B.inputAlphabet.invFun b :: zs)) := by change some (Turing.TM2.stepAux (copySecond A B) _ _) = _ exact congrArg some (transferSecond_aux A B b ys zs x) theorem transferSecond_finish (zs : List (B.tm.Γ B.tm.k₀)) (x : Option Γ₁) : (machine A B).step (transferCfg A B true x [] [] zs) = some ⟨some (.inr (.inl B.tm.main)), (A.tm.initialState, B.tm.initialState, none), transferStacks A B [] [] zs⟩ := by change some (Turing.TM2.stepAux (copySecond A B) _ _) = _ exact congrArg some (transferSecond_nil A B zs x) noncomputable def runStep (c : Option (machine A B).Cfg) : Option (machine A B).Cfg := c.bind (machine A B).step theorem transferFirst_run (xs : List (A.tm.Γ A.tm.k₁)) (ys : List Γ₁) (x : Option Γ₁) : (runStep A B)^[xs.length + 1] (some (transferCfg A B false x xs ys [])) = some (transferCfg A B true none [] ((xs.map A.outputAlphabet).reverse ++ ys) []) := by induction xs generalizing ys x with | nil => change (machine A B).step (transferCfg A B false x [] ys []) = _ exact transferFirst_finish A B ys x | cons a xs ih => change (runStep A B)^[Nat.succ (xs.length + 1)] _ = _ rw [Function.iterate_succ_apply] simp only [runStep, Option.bind_some, transferFirst_step] simpa [List.map_cons, List.reverse_cons, List.append_assoc] using ih (A.outputAlphabet a :: ys) (some (A.outputAlphabet a)) theorem transferSecond_run (ys : List Γ₁) (zs : List (B.tm.Γ B.tm.k₀)) (x : Option Γ₁) : (runStep A B)^[ys.length + 1] (some (transferCfg A B true x [] ys zs)) = some ⟨some (.inr (.inl B.tm.main)), (A.tm.initialState, B.tm.initialState, none), transferStacks A B [] [] ((ys.map B.inputAlphabet.invFun).reverse ++ zs)⟩ := by induction ys generalizing zs x with | nil => change (machine A B).step (transferCfg A B true x [] [] zs) = _ exact transferSecond_finish A B zs x | cons b ys ih => change (runStep A B)^[Nat.succ (ys.length + 1)] _ = _ rw [Function.iterate_succ_apply] simp only [runStep, Option.bind_some, transferSecond_step] simpa [List.map_cons, List.reverse_cons, List.append_assoc] using ih (B.inputAlphabet.invFun b :: zs) (some b) 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₀ · subst k simp [firstStacks, Turing.initList] rfl · simp [firstStacks, Turing.initList, h] | inr k => simp [firstStacks, Turing.initList] theorem packFirst_halt (xs : List (A.tm.Γ A.tm.k₁)) : packFirst A B (Turing.haltList A.tm xs) = transferCfg A B false none xs [] [] := by classical simp [packFirst, firstCfg, firstStacks, Turing.haltList, transferCfg, transferStacks] congr 1 funext k cases k with | inl k => by_cases h : k = A.tm.k₁ · subst k simp [firstStacks, Turing.haltList, transferStacks] · simp [firstStacks, Turing.haltList, transferStacks, h] | inr k => cases k with | inl k => by_cases h : k = B.tm.k₀ · subst k simp [firstStacks, transferStacks] · simp [firstStacks, transferStacks, h] | inr k => cases k <;> simp [firstStacks, transferStacks] theorem packSecond_init (zs : List (B.tm.Γ B.tm.k₀)) : packSecond A B (Turing.initList B.tm zs) = ⟨some (.inr (.inl B.tm.main)), (A.tm.initialState, B.tm.initialState, none), transferStacks A B [] [] zs⟩ := by classical simp [packSecond, secondCfg, secondStacks, Turing.initList, transferStacks] congr 1 funext k cases k with | inl k => by_cases h : k = A.tm.k₁ · subst k simp [secondStacks, Turing.initList, transferStacks] · simp [secondStacks, Turing.initList, transferStacks, h] | inr k => cases k with | inl k => by_cases h : k = B.tm.k₀ · subst k simp [secondStacks, Turing.initList, transferStacks] · simp [secondStacks, Turing.initList, transferStacks, h] | inr k => cases k <;> simp [secondStacks, Turing.initList, transferStacks] 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 => cases k with | inl k => by_cases h : k = B.tm.k₁ · subst k simp [secondStacks, Turing.haltList] rfl · simp [secondStacks, Turing.haltList, h] | inr k => cases k <;> simp [secondStacks, Turing.haltList] theorem transfer_both (xs : List (A.tm.Γ A.tm.k₁)) : (runStep A B)^[(xs.length + 1) + (xs.length + 1)] (some (transferCfg A B false none xs [] [])) = some (packSecond A B (Turing.initList B.tm ((xs.map A.outputAlphabet).map B.inputAlphabet.invFun))) := by rw [Function.iterate_add_apply, transferFirst_run] have h := transferSecond_run A B ((xs.map A.outputAlphabet).reverse) [] none rw [packSecond_init] simpa [List.map_reverse, List.reverse_reverse] using h 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 + ((f a).length + 1) + ((f a).length + 1) + (A.outputsFun a).steps) := by let u := a.map A.inputAlphabet.invFun let v := (f a).map A.outputAlphabet.invFun let w := (g (f a)).map B.outputAlphabet.invFun have hA := 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 v) (A.outputsFun a).evals_in_steps rw [packFirst_init, packFirst_halt] at hA change (runStep A B)^[(A.outputsFun a).steps] (some (Turing.initList (machine A B) u)) = _ at hA have hB := 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 rw [packSecond_halt] at hB change (runStep A B)^[(B.outputsFun (f a)).steps] (some (packSecond A B (Turing.initList B.tm ((f a).map B.inputAlphabet.invFun)))) = _ at hB have hcopy := transfer_both A B v have hconvert : (v.map A.outputAlphabet).map B.inputAlphabet.invFun = (f a).map B.inputAlphabet.invFun := by simp [v, List.map_map] rw [hconvert] at hcopy have hlen : v.length = (f a).length := by simp [v] rw [hlen] at hcopy refine ⟨⟨(B.outputsFun (f a)).steps + ((f a).length + 1) + ((f a).length + 1) + (A.outputsFun a).steps, ?_⟩, le_rfl⟩ change (runStep A B)^[_] (some (Turing.initList (machine A B) u)) = some (Turing.haltList (machine A B) w) rw [Function.iterate_add_apply, hA, Nat.add_assoc, Function.iterate_add_apply, hcopy, hB] theorem poly_eval_mono (p : Polynomial ℕ) : Monotone p.eval := by intro a b hab induction p using Polynomial.induction_on' with | add p q hp hq => simp only [Polynomial.eval_add] change p.eval a ≤ p.eval b at hp change q.eval a ≤ q.eval b at hq exact Nat.add_le_add hp hq | monomial n c => simp only [Polynomial.eval_monomial] exact Nat.mul_le_mul_left c (Nat.pow_le_pow_left hab n) noncomputable def composePoly : Turing.TM2ComputableInPolyTime (id : List Γ₀ → List Γ₀) (id : List Γ₂ → List Γ₂) (g ∘ f) := by classical let q := Classical.choose (op75_tm2_poly_output_size A) have hq : ∀ a, (f a).length ≤ q.eval a.length := Classical.choose_spec (op75_tm2_poly_output_size A) refine { tm := machine A B inputAlphabet := A.inputAlphabet outputAlphabet := B.outputAlphabet time := B.time.comp q + (q + 1) + (q + 1) + A.time 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 hm := poly_eval_mono B.time (hq a) simp only [Polynomial.eval_add, Polynomial.eval_comp, Polynomial.eval_one] change (B.outputsFun (f a)).steps + ((f a).length + 1) + ((f a).length + 1) + (A.outputsFun a).steps ≤ B.time.eval (q.eval a.length) + (q.eval a.length + 1) + (q.eval a.length + 1) + A.time.eval a.length change B.time.eval (f a).length ≤ B.time.eval (q.eval a.length) at hm have hs := hq a simp only [id_eq] at hA hB omega end Op75GeneralComposition theorem op75_tm2_inhabited_comp {Γ₀ Γ₁ Γ₂ : Type} [Inhabited Γ₁] {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 ⟨Op75GeneralComposition.composePoly A B⟩