Charged randomized machine interface and prefix encodings
DefinitionOddPermSum_Evaluation_Supplement_bitModelThe published bit-RAM has one finite program, bounded address words of bits for a fixed program parameter , bit memory, and one charged step for every instruction. Its only operations are word bookkeeping, bit Boolean operations, load/store/input, fair coins, output, jumps, and halt. Advice is empty throughout this supplement. Finite fields, irreducible-polynomial construction, algebraic evaluation and matrix multiplication must all be implemented by these instructions.
The input is unary , a delimiter, and the directed adjacency bits in row-major order. Natural-number outputs use a prefix code consisting of a unary bit length, a delimiter and binary digits. A length- fair tape has the exact uniform law on :
No infinite mass is converted to a finite real. Positive logarithmic factors use .
import Definitions.Def_OddPermSum_Evaluation_Supplement_digraph
import Definitions.Def_MaoLowDegree_Counterexample_bitRAM
set_option autoImplicit false
namespace OddPermSum.Evaluation.Supplement
abbrev BitProgram := MaoLowDegree.Counterexample.BitProgram
abbrev BitState := MaoLowDegree.Counterexample.BitState
abbrev runBits := MaoLowDegree.Counterexample.runBits
abbrev extendCoins {t : ℕ} (c : Fin t → Bool) := MaoLowDegree.Counterexample.extendCoins c
/-- Prefix code: unary bit length, delimiter, then little-endian binary digits. -/
def encodeNat (n : ℕ) : List Bool :=
List.replicate n.bits.length true ++ [false] ++ n.bits
def encodeNats (xs : List ℕ) : List Bool :=
encodeNat xs.length ++ xs.flatMap encodeNat
/-- An input adjacency matrix preceded by unary n and its delimiter. -/
noncomputable def directedInput {n : ℕ} (D : Digraph n) : List Bool := by
classical
exact List.replicate n true ++ [false] ++
((List.finRange n).flatMap fun i => (List.finRange n).map fun j => decide ((i,j) ∈ D.arcs))
/-- Uniform finite fair tape; all programs below halt within the sampled prefix. -/
noncomputable def fairProbability (t : ℕ) (E : (Fin t → Bool) → Prop) : ℝ := by
classical
exact ((Finset.univ.filter E).card : ℝ) / (2 : ℝ)^t
/-- Log factors are positive, even at n=0. -/
noncomputable def logFactor (n : ℕ) (k : ℕ) : ℝ :=
(Real.logb 2 (n+1) + 1)^k
end OddPermSum.Evaluation.Supplement