stack program correct
ProvedCookPvsNP.stack_program_correctalgorithmspolynomial-time
Every structured source execution yields exactly the same store at a halting label of its fixed finite-control machine.
Preamble
import Definitions.Def_CookPvsNP_StackProgram open CookPvsNP
Formal statement
namespace CookPvsNP
theorem stack_program_correct {K A : Type} {p : StackProg K A} {s t : K → List A} {n : ℕ}
(h : p.Exec s t n) : ∃ l : p.Label, p.done l = true ∧
(p.machine.step^[n]) ⟨p.entry, s⟩ = ⟨l, t⟩ := 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.