Two sweep accumulators agree with the column transformation
ProvedCookPvsNP.stack_sweep_algebrapolynomial-timeturing-machines
The right accumulator preserves the length of its written prefix; a subsequent left accumulator followed by the final carry column equals the specified column transformation.
Preamble
import Definitions.Def_CookPvsNP_StackModel
Formal statement
namespace CookPvsNP
theorem stack_sweep_algebra {K A : Type} (a : K → StackAct A) (r : List (StackCol K A)) :
let z := stackRight a (stackPushCarry a) r
z.2.length = r.length ∧
(stackLeft a z.1 z.2.reverse).2.reverse ++ [z.1] =
stackBackward a (stackForward a (stackPushCarry a) r) := by sorry
end CookPvsNPSource
New auxiliary formalization for the ResourceScheduling Q2 reduction. The target is the unchanged CookPvsNP one-tape machine model, following Cook, The P versus NP problem, Clay Mathematics Institute (2000), Appendix. This explicit finite-column stack compiler and its simulation lemmas are new contributions, not numbered claims from Cook or the scheduling source paper.