Evaluation correctness and bounding for the satVerifier multi-tape Turing machine
DisprovedCookLevin.satVerifierMachine_decides_eval_corecook-levindecides-inverifier
For any 6-tape, 4-symbol multi-tape machine , decides the SAT verifier predicate satVerifier x w in polynomial time bounded by .
Formal statement
import Definitions.Def_CookLevin_Basic
import Definitions.Def_CookLevin_Satisfiability
import Definitions.Def_CookLevin_Complexity
import Definitions.Def_CookLevin_Verifier
open CookLevin
theorem CookLevin.satVerifierMachine_decides_eval_core :
∀ (M : Machine), TuringMachine 6 4 M → ∀ x w : List Bool, DecidesIn M 6 (boolsToSymbols x) (boolsToSymbols w) (polyBound 1 2 (x.length + w.length)) (satVerifier x w) := by sorrySource