Source running-time bound transfers to actual recursive-controller execution
ProvedNearlyOptimalPPR.Computation.controller_source_run_certifiedSuppose , , and the seed has positive degree. Assume the canonical recursive source run has a finite terminal prefix and source work at most . Let a prepared concrete root represent its initial state with heap mass at most one. Choose queue capacity , rank , and array length with
and sufficient cache-potential credit. Then the actual recursive controller has a finite execution, producing a nonnegative ACL-accurate explicit output. Its charged work is at most
where is the heap-cleaning coefficient and the explicit compiler overhead factor. The source termination and work hypotheses are discharged separately when this transfer theorem is applied to the uniform algorithm.
The result derives all reachable allocation bounds and instruction charges from source finite-prefix invariants.
import Definitions.Def_NearlyOptimalPPR_Computation_compiler_runtime open Finset Matrix open scoped ENNReal set_option autoImplicit false noncomputable section attribute [local instance] Classical.propDecidable
namespace NearlyOptimalPPR.Computation
open SparseQueue
theorem controller_source_run_certified (m : SolveModel) {n : ℕ} (g : InputGraph n) (ω : ℕ → Bool)
(s : Fin n) (α ε E : ℝ) (ell length N rank Q : ℕ)
(hα : 0<α ∧ α≤1/2) (hε : 0<ε ∧ ε≤1) (hs : 0<g.graph.degree s)
(hBound : recursiveWork m g s α ε ell [] ≤ ENNReal.ofReal E)
(hWide : ((8*(ell+1) : ℕ) : ℝ≥0∞)*ENNReal.ofReal E ≤ (N : ℝ≥0∞))
(hTermination : ∃ t, (recursiveRun m g s α (rootThreshold ε ell) ell [] t).done=true)
(hCredit : 4*(16*(ell+3))+17 ≤ Q) (hCap : rank<length) (hPow : N<2^rank)
(st : MachineState) (memory : ControllerMemory g s α ε ell length
(recursiveInit g s (rootThreshold ε ell) ell []) st) (hM : memory.mass ≤ 1) :
let P := cleanBodyBound (16*(ell+3)) length rank+2
let F := compilerOverheadFactor ell length rank Q
∃ steps out, MachineEval m g ω recursiveControllerCode st steps out ∧
(∀ v : Fin n, 0 ≤ outputVector out.output v) ∧ ACL g.graph α ε s (outputVector out.output) ∧
out.work ≤ st.work+(P : ℝ≥0∞)+(F : ℝ≥0∞)*ENNReal.ofReal E+1 := by sorry
end NearlyOptimalPPR.Computation