Cook–Levin machines: advance head counters to the next logical tape
ProvedCookLevin.machine_advance_head_tape_counterscomplexitycook-levinloopsturing-machines
Advance the three counters left by a runtime-sized exactly-one head block to position zero of the next logical tape. Restore the inner position fuel and preserve output, flag and saved tapes. Runtime 14*(T+1)+28.
Preamble
import Definitions.Def_CookLevin_Tableau import Definitions.Def_CookLevin_Complexity open CookLevin set_option autoImplicit false
Formal statement
theorem CookLevin.machine_advance_head_tape_counters {k G : Nat} (hk : 7 ≤ k) (hG : 4 ≤ G) :
∃ R : Machine, TuringMachine k G R ∧
∀ (sh : Shape) (t j : Nat) (input out flag : Tape)
(fuel : Nat → Symbol) (saved : List Tape),
fuel 0 ≠ oneSymbol →
(∀ i, i < sh.T + 1 → fuel (1 + i) = oneSymbol) →
fuel (1 + (sh.T + 1)) ≠ oneSymbol →
let a := fun j p => literalN (.Neg (sh.headVar t j p))
let c := fun j p => literalN (.Pos (sh.headVar t j p))
Transforms R
(input :: (contents (boolsToSymbols (List.replicate (a j (sh.T + 1)) true)), 1 + a j (sh.T + 1)) ::
(contents (boolsToSymbols (List.replicate (a j 0) true)), 1 + a j 0) ::
(contents (boolsToSymbols (List.replicate (c j (sh.T + 1)) true)), 1 + c j (sh.T + 1)) ::
out :: flag :: (fuel, 1) :: saved)
(14 * (sh.T + 1) + 28)
(input :: (contents (boolsToSymbols (List.replicate (a (j + 1) 0) true)), 1 + a (j + 1) 0) ::
(contents (boolsToSymbols (List.replicate (a (j + 1) 0) true)), 1 + a (j + 1) 0) ::
(contents (boolsToSymbols (List.replicate (c (j + 1) 0) true)), 1 + c (j + 1) 0) ::
out :: flag :: (fuel, 1) :: saved) := by sorrySource
Runtime-sized distinct-position filtering for the Cook–Levin head constraints.