var-expression machine: empty-env evaluation makes test (.var i) constantly false
ProvedCookLevin.boundedExpr_var_machinecliquecook-levinnp-completenesssource-faithful-child
Bounded-expression evaluation under the empty numeric environment ignores out-of-scope variables: test (.var i) x y = false for every index i, every instance list x and every witness list y. Hence the Boolean predicate denoted by .var i 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 var case.
Preamble
import Definitions.Def_CookLevin_Cost import Definitions.Def_CookLevin_BoundedExpr
Formal statement
namespace CookLevin
/-- Child 2 (easy-first): `test` evaluates under the EMPTY numeric env, so
`test (.var i) x y = false` for every `i`. Constant machine. -/
theorem boundedExpr_var_machine (i : Nat) :
∃ (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.var i) 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 `var` 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.