input-expression machine: zero numeric component makes test (.input w) constantly false
ProvedCookLevin.boundedExpr_input_machinecliquecook-levinnp-completenesssource-faithful-child
The input channel of a bounded expression carries no numeric value: eval (.input w) env x y = (0, ...) for every witness bit w, so test (.input w) x y = false for every w, every instance list x and every witness list y. Hence the Boolean predicate denoted by .input w is the constant-false function, decidable in O(1) time by a well-formed finite-alphabet multitape machine (writing the single verdict bit), polynomial in the combined input lengths with any constants c, d. This is the per-constructor instance of CookLevin.boundedExpr_test_turingMachine_polynomial for the input case.
Preamble
import Definitions.Def_CookLevin_Cost import Definitions.Def_CookLevin_BoundedExpr
Formal statement
namespace CookLevin
/-- Child 3 (easy-first): `eval (.input w)` has numeric component 0, so
`test (.input w) x y = false` for every `w`. Constant machine. -/
theorem boundedExpr_input_machine (w : Bool) :
∃ (M : CookLevin.Machine) (k G c d : Nat),
CookLevin.TuringMachine k G M ∧
∀ (x y : List Bool),
CookLevin.DecidesIn M k
(CookLevin.boolsToSymbols x) (CookLevin.boolsToSymbols y)
(CookLevin.polyBound c d (x.length + y.length))
(CookLevin.BoundedExpr.test (CookLevin.BoundedExpr.input w) x y) := by
sorry
end CookLevin
Source
Decomposition child of CookLevin.boundedExpr_test_turingMachine_polynomial (22e0a9d5-d4cf-4db5-836c-e5478d836f54, Open). Per-constructor instance for the `input` case of CookLevin.BoundedExpr. Statement elab-validated verbatim against the genuine Def_CookLevin_BoundedExpr source (definition record 430ef97b-7797-4bcd-bbb5-8fe7f3282e0e); see ~/workspace/p2m_harness/work/cooklevin_boundedexpr/CHILD_SPECS_VALIDATED.lean.