A word-RAM algorithm recovers the padded encoding from a long enough zero-padded prefix
OpenTwoFoldOPI.padFromPrefix_RAMFor an instance of Theorem 7.4, with public encoding and size parameter , let be the first bits of , and let .
For each word-RAM instruction set there are an algorithm and a function on bit strings such that computes in polynomial time and
Composed with any polynomial-time algorithm that works on padded encodings, this gives an algorithm that works on long enough raw prefixes. That is how the uniformity bridge runs the constructor of a RAM-serializable family.
Formalization Note. The statement is for an arbitrary WordRAM.Model, so that the composition with a given algorithm stays within one instruction set. is unconstrained on other inputs.
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_RAMSerializable
namespace TwoFoldOPI
theorem padFromPrefix_RAM (m : WordRAM.Model) :
∃ (A : WordRAM.Complexity.Algorithm m) (h : List Bool → List Bool),
WordRAM.Complexity.RAMPolyTimeComputable A h ∧
∀ (x : Input) (s : ℕ), x.encode.length ≤ s → x.scale ≤ s →
h ((x.encode ++ List.replicate s false).take s) = x.padded := by sorry
end TwoFoldOPI