Stack actions preserve the padded column representation
ProvedCookPvsNP.stack_representationpolynomial-timeturing-machines
If a column list represents a family of stacks, its two-sweep transform represents exactly the family obtained by independently applying the selected source actions.
Preamble
import Definitions.Def_CookPvsNP_StackRepresentation
Formal statement
namespace CookPvsNP
theorem stack_representation {K A : Type} (a : K → StackAct A) (r : List (StackCol K A))
(s : K → List A) (h : StackRep r s) :
StackRep (stackBackward a (stackForward a (stackPushCarry a) r))
(fun k => (a k).apply (s k)) := 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.