The queue-empty test is the unique transition into restoration entry
ProvedDirKECC1549.Main.reverse_search_restore_predecessorgraph-algorithmsword-ram
For the fixed reverseSearchAlgorithm at any word width, let s and t be machine states such that one successful step carries s to t and t has program counter 111. Then
and the unsigned words in queue-tail register 10 and queue-head register 9 satisfy
No graph-layout, valid-input, root, initialization, or numeric word-width assumption is needed. The assertion is about any successful single step of the actual lowered instruction list. It identifies the unique entry into the restoration epilogue and the exact queue comparison that selected it.
Preamble
import Definitions.Def_DirKECC1549_Main_Machine import Definitions.Def_DirKECC1549_Main_ReverseSearchCode set_option autoImplicit false open WordRAM
Formal statement
namespace DirKECC1549.Main
theorem reverse_search_restore_predecessor (w : Width) (s t : State w)
(hstep : step Uniform.noConstants
(Complexity.Program.lower w reverseSearchAlgorithm.code) s = some t)
(hpc : t.pc = 111) :
s.pc = 70 ∧ s.halted = false ∧ t.mem = s.mem ∧
(s.mem 10).toNat ≤ (s.mem 9).toNat := by sorry
end DirKECC1549.Main
Source
Decomposition of the restoration-entry invariant https://prove2.me/theorems/12a0367d-b08f-4e35-8f92-9049fe3034d6. Uses the explicit reverseSearchAlgorithm in Definitions.Def_DirKECC1549_Main_ReverseSearchCode: PC 70 tests register 10 <= register 9 and branches to 111; the remaining code has no transition into 111. Abstract scan histories use Definitions.Def_DirKECC1549_Main_ReverseScanTrace.