Correctness and linear overhead of the pancake input parser
ProvedPancakeHard.ReductionCompiler.parse_stage_correctFix the concrete RAM transducer, an input string , an auxiliary input , a word width , and a continuation bound . Write and assume
Suppose that, for each valid input, the construction stage beginning at instruction 100 produces the prescribed final output within further steps, for every scratch-register value and initial tick count. Then the transducer started in its initial state halts with the prescribed output within
steps. The state passed to the continuation contains the raw occurrence pairs, the shifted/padded literal array, and the correct clause count. The width recognizer and padding pass reject malformed encodings, excessive clause widths, and empty clauses with the empty output.
This is an implementation lemma for the total normalization required by the proof of Theorem 19; the program and continuation state are specified in the reduction-program interface.
import Mathlib import Definitions.Def_PancakeHard_ReductionProgram set_option autoImplicit false
namespace PancakeHard.ReductionCompiler
theorem parse_stage_correct {w : WordRAM.Width} {budget : Bool} (x y : List Bool)
(hroom : PancakeHard.ReductionCompiler.InputRoom x w) (K : Nat)
(hpost : PancakeHard.ReductionProof.validInput x → ∀ count value ticks,
PancakeHard.ReductionCompiler.Reach budget K
(PancakeHard.ReductionCompiler.PM (w := w) x y (8+x.length)
(PancakeHard.ReductionCompiler.arrOf (CookLevin.formulaN (CookLevin.decodeFormula x)) 0)
(PancakeHard.ReductionCompiler.padArrays (CookLevin.formulaN (CookLevin.decodeFormula x)))
(8+x.length+(PancakeHard.ReductionCompiler.arrOf (CookLevin.formulaN (CookLevin.decodeFormula x)) 0).length)
(CookLevin.decodeFormula x).length (CookLevin.decodeFormula x).length count value 100 ticks)
(PancakeHard.ReductionCompiler.Good budget x)) :
PancakeHard.ReductionCompiler.Reach budget (150*(x.length+1)+K)
(WordRAM.Complexity.initialState w x y) (PancakeHard.ReductionCompiler.Good budget x) := by sorry
end PancakeHard.ReductionCompiler