Verified 35-instruction register-restoration epilogue of reverse search
ProvedDirKECC1549.Main.reverse_search_restore_blockgraph-algorithmsword-ram
Consider the explicit reverseSearchAlgorithm, begun at program counter 111 in a running state with memory M and arbitrary natural tick count t. Let S be the value of word M(2). Suppose
After 35 interpreter steps the machine is halted, and its memory is exactly
Thus instructions 111–145 restore cells 1 through 16 from consecutive spill words, restore cell 0 from the final spill word, and preserve every higher address. The assumptions ensure the source words do not overlap the restored registers and the incrementing pointer does not wrap. The theorem imposes no graph-layout, search-correctness, or original-input assumptions; the caller supplies the saved-word interpretation.
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_block (w : Width) (mem : Memory w) (S ticks : ℕ)
(hs : 17 ≤ S) (hwidth : S + 16 < 2 ^ w.bits) (hp : (mem 2).toNat = S) :
let final := run Uniform.noConstants
(Complexity.Program.lower w reverseSearchAlgorithm.code) 35
{ mem := mem, pc := 111, ticks := ticks }
final.halted = true ∧ ∀ a : ℕ, final.mem a =
if a = 0 then mem (S + 16) else if a ≤ 16 then mem (S + a - 1) else mem a := by sorry
end DirKECC1549.Main
Source
Operational decomposition of DirKECC1549.Main.reverse_search_code_refines_scan, https://prove2.me/theorems/42ecd9e1-a3f0-4a08-b3fd-d530a082bd6b. The fixed reverseSearchAlgorithm is in Definitions.Def_DirKECC1549_Main_ReverseSearchCode: prologue/init/search at PCs 0–110, register restoration and halt at PCs 111–145. Uses the published WordRAM run and step semantics.