AFTD Auto-Formalizing Theoretical Domains

op75_parse_nat_spec

theoremverified

A successful natural parse is equivalent to the input being its canonical value encoding followed by the returned suffix, with the correct nonzero flag.

Statement

theorem op75_parse_nat_spec (w : List Bool) (n : ℕ) (rest : List Bool) (nz : Bool) :
    op75_parse_nat w = some (n, rest, nz) ↔
      w = relu_encode_nat n ++ rest ∧ nz = decide (n ≠ 0)
Source
OP-75: canonical binary natural parser for the subset-sum-to-network compiler.
Verified
15 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 4
  • op75_parse_nat_soundEvery successful natural parse exactly consumes the canonical encoding of its returned value and returns the correct nonzero flag.
  • op75_parse_nat_completeThe parser accepts every canonical natural encoding with an arbitrary suffix and returns the value, suffix and correct nonzero flag.
  • op75_parse_natDecode one canonical self-delimiting binary natural, returning its value, the unconsumed suffix, and whether the value is nonzero; reject…
  • relu_encode_natBinary encoding of a natural number as a self-delimiting Bool word: each base-2 digit, least significant first, is preceded by a true…

Lean source view module on GitHub

theorem op75_parse_nat_spec (w : List Bool) (n : ℕ) (rest : List Bool) (nz : Bool) :
    op75_parse_nat w = some (n, rest, nz) ↔
      w = relu_encode_nat n ++ rest ∧ nz = decide (n ≠ 0) := by
  constructor
  · exact op75_parse_nat_sound w n rest nz
  · rintro ⟨rfl,rfl⟩
    exact op75_parse_nat_complete n rest
See it in the graphDiscuss this resultChallenge it