bounded loop of a poly-time step decider with a linearly-bounded fuel: run M per index, aggregate with every, stay polynomial
DisprovedCookLevin.boundedExpr_boundedLoop_machineComposition-kit lemma for the CLIQUE Cook-Levin lane: bounded-loop iteration of a polynomial-time step decider. If a well-formed machine M decides a body relation Rb (loop index i on the tape as the tape-encoded encodeNat i ++ y, the mission's own encoding apparatus from Def_CookLevin_Satisfiability) within a polynomial bound polyBound c1 d1, and the loop bound bl is linear in the input lengths (bl x y ≤ c0 * (x.length + y.length) + d0), then there exists a well-formed machine Mloop deciding the iterated relation (List.range (bl x y)).all (fun i => Rb i x y) within a polynomial bound polyBound c d. The machine runs M once per index below the bound and aggregates with every; the count variant aggregates the same loop run with count ≠ 0, so this loop machine is the shared primitive behind both BoundedExpr.count and BoundedExpr.every. The composite constants c, d absorb the per-iteration cost times the linear loop count. This is the bounded-loop primitive used to assemble per-constructor machines for CookLevin.BoundedExpr evaluation from sub-expression machines.
import Definitions.Def_CookLevin_Cost import Definitions.Def_CookLevin_BoundedExpr import Definitions.Def_CookLevin_Satisfiability
namespace CookLevin
/-- Composition-kit child 3/3 (bounded loop): iterating a poly-time step
decider up to a linearly-bounded number of times stays poly-time. -/
theorem boundedExpr_boundedLoop_machine
(Rb : Nat → List Bool → List Bool → Bool)
(M : CookLevin.Machine)
(bl : List Bool → List Bool → Nat)
(k G c1 d1 c0 d0 : Nat)
(hwf : CookLevin.TuringMachine k G M)
(hlin : ∀ (x y : List Bool),
bl x y ≤ c0 * (x.length + y.length) + d0)
(hdec : ∀ (i : Nat) (x y : List Bool),
CookLevin.DecidesIn M k
(CookLevin.boolsToSymbols x)
(CookLevin.boolsToSymbols (CookLevin.encodeNat i ++ y))
(CookLevin.polyBound c1 d1 (x.length + y.length + i))
(Rb i x y)) :
∃ (Mloop : CookLevin.Machine) (k' G' c d : Nat),
CookLevin.TuringMachine k' G' Mloop ∧
∀ (x y : List Bool),
CookLevin.DecidesIn Mloop k'
(CookLevin.boolsToSymbols x) (CookLevin.boolsToSymbols y)
(CookLevin.polyBound c d (x.length + y.length))
((List.range (bl x y)).all (fun i => Rb i x y)) := by
sorry
end CookLevin