PR #6453: the replay composes and is deterministic
ProvedPr6453.replay_composescomplexity-theoryinteger-multiplication
The two structural facts about the replay of a word: it composes over concatenation of programs, and it is deterministic.
Composition: replaying p ++ q from a state is replaying p and then q. That is the induction principle a proof of the replay condition for the full 17 926-event program would use — it lets the program be broken into the segments the construction's stages are made of, each replays its own segment, and the segments compose. Determinism: a successful replay has a unique end state, so the frame and row charts the certificate records are the ones the program determines.
Preamble
import Definitions.Def_Pr6453_Replay set_option autoImplicit false
Formal statement
namespace Pr6453
theorem replay_composes :
(∀ (n : ℕ) (p q : List (Event n)) (st : State n),
replay? (p ++ q) st = (replay? p st).bind (replay? q)) ∧
(∀ (n : ℕ) (prog : List (Event n)) (st fin fin' : State n),
replay? prog st = some fin → replay? prog st = some fin' → fin = fin') := by
sorry
end Pr6453Source
CrocSwap/integer-mult-bounds, PR #6453, head b1a3e525793eca35c56324aa7ffd0b714cf606d4: the guarded replay of research/p104-clean-piggyback/construct.py.