Documentation

MIPRE.Background.Introspection.DecisionKernelGameInterface

Identification of the kernel's finite semantics with the explicit game #

theorem MIPRE.Introspection.DecisionKernel.program_sound_numbered (W : Cost.ClockedUniversalMachine) {lam n : ℕ} (V : Verifier 7) (hV : V.IsBounded lam) (hn : 1 ≤ n) (k : ℕ) (hk : 1 ≤ k) [NeZero k] (hodd : Odd k) (j : ℕ) (hj : j ≤ k) (hm : 2 ^ j ∣ Fintype.card (SAT.shoupBinField k hk).carrier) (hs : V.sampler.dim (2 ^ n) ≤ 2 ^ 2 ^ j * k) (hQ : 4 ≤ 2 ^ 2 ^ j * k) (hR : 3 * (2 ^ n) ^ lam ≤ 2 ^ 2 ^ j * k) (χ : (SAT.shoupBinField k hk).carrier → Fin (2 ^ j)) (T U : Label) (x y : Fin ((3 * 2 ^ j + 3) * k) → CL.𝔽₂) (a b : Cost.BitStr) (h : (program W).toFun (canonicalInput V lam n (2 ^ 2 ^ j * k) ((2 ^ n) ^ lam) (Cost.unary k, Cost.unary j, Cost.unary (2 ^ j)) T U (CL.toBits x) (CL.toBits y) a b) = true) :

Raw kernel acceptance gives the exact finite game used by the source soundness theorem, including the executable full-register numbering.