A word-RAM test of whether a zero-padded prefix contains the whole instance and covers its size
OpenTwoFoldOPI.encodeLengthDecider_RAMFor an instance of Theorem 7.4 let be its public bit encoding (field presentation, , , tag, matrix, forbidden values, precision) and . For let be the first bits of .
There are a word-RAM algorithm in the restricted instruction set and a function on bit strings such that computes in polynomial time and, for every instance and every ,
The algorithm parses the self-delimiting encoding, using only the lengths it determines, and compares the size parameter with .
This is the test the uniformity bridge uses to locate the end of an encoding that carries no end marker.
Formalization Note. The output is the one-bit list [decide (…)]. RAMPolyTimeComputable is the published WordRAM.Complexity notion (time at the canonical word width). is unconstrained on strings that are not padded prefixes of encodings.
Retired. Superseded by TwoFoldOPI.uniformFamily_of_RAMSerializableF: uniformity is now reduced through RAM-serializability on raw prefixes (TwoFoldOPI.RAMSerializableF), where the constructor itself recognises when a zero-padded prefix is long enough. This removes the separate parser lemmas.
import Mathlib import Definitions.Def_TwoFoldOPI_Input import Definitions.Def_WordRAM_Complexity_BitIO
namespace TwoFoldOPI
theorem encodeLengthDecider_RAM :
∃ (A : WordRAM.Complexity.Algorithm .restricted) (v : List Bool → List Bool),
WordRAM.Complexity.RAMPolyTimeComputable A v ∧
∀ (x : Input) (s : ℕ), v ((x.encode ++ List.replicate s false).take s) =
[decide (x.encode.length ≤ s ∧ x.scale ≤ s)] := by sorry
end TwoFoldOPI