Cook–Levin machines: blank-suffix emission from the standard input configuration
ProvedCookLevin.machine_blank_suffix_transformscomplexitycook-levinloopsturing-machines
Given machines computing unary initial-literal numbers and tableau widths, construct a single machine that starts from the standard input configuration and emits the entire blank-suffix formula on its final tape. The shape may depend on the input, with a fixed symbol bound. For source bounds T1,T2, total runtime is at most 4T1+2T2+a_initial+width*(4a_final+16symbols+16)+10. The resulting machine uses k1+k2+1 tapes.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_blank_suffix_transforms {k₁ k₂ G : Nat} (M₁ M₂ : Machine)
(h₁ : TuringMachine k₁ G M₁) (h₂ : TuringMachine k₂ G M₂)
(T₁ T₂ : Nat → Nat) (shape : List Bool → Shape) (symbols j : Nat)
(hshape : ∀ x, (shape x).G = symbols)
(hc₁ : ComputesInTime M₁ k₁ T₁
(fun x => List.replicate (literalN (.Neg ((shape x).cellVar 0 j 0 blankSymbol))) true))
(hc₂ : ComputesInTime M₂ k₂ T₂ (fun x => List.replicate (shape x).T true)) :
∃ R : Machine, TuringMachine (k₁ + k₂ + 1) G R ∧
∀ x, ∃ (saved : List Tape) (head : Nat), saved.length + 1 = k₁ + k₂ + 1 ∧
let a₀ := literalN (.Neg ((shape x).cellVar 0 j 0 blankSymbol))
let aₙ := literalN (.Neg ((shape x).cellVar 0 j (shape x).T blankSymbol))
Transforms R (startConfig2 (k₁ + k₂ + 1) (boolsToSymbols x) []).2
(4 * T₁ x.length + 2 * T₂ x.length + a₀ +
(shape x).T * (4 * aₙ + 16 * symbols + 16) + 10)
(saved ++ [(contents (boolsToSymbols (encodeFormula (blankSuffixClauses (shape x) j))), head)]) := by sorrySource
Compose two independent computations, reset all heads, pad a fresh output tape, and apply the blank-suffix bank emitter.