ram basic
ProvedResourceScheduling.Graph.ram_basicalgorithmspolynomial-time
Skip, zero, increment, and truncated decrement implement their register semantics with explicit source-step budgets.
Preamble
import Definitions.Def_ResourceScheduling_Graph_RAMOps open CookPvsNP ResourceScheduling.Graph
Formal statement
namespace ResourceScheduling.Graph
theorem ram_basic {V : Type} [DecidableEq V] (v : V) :
StackImplements RAMRep (ramSkip (V := V)) id (fun _ => 1) ∧
StackImplements RAMRep (ramZero v) (fun s => s.set v 0) (fun s => 3 * s.val v + 1) ∧
StackImplements RAMRep (ramInc v) (fun s => s.set v (s.val v + 1)) (fun _ => 1) ∧
StackImplements RAMRep (ramDec v) (fun s => s.set v (s.val v - 1)) (fun _ => 1) := by sorry
end ResourceScheduling.GraphSource
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.