Theorem 4.11 (companion theorem; not used in the proof of the goal) — variable-arity register algorithm
OpenCatalyticTreeEval.Main.Supplement.theorem_4_11In the arity- framework, for every integer , take , a positive label length , an -noncancelling score set containing zero, an -matching family of exact size and dimension , and an -decoder of sparsity . Let fixed uniform access procedures have common space . A single deterministic binary machine evaluates every complete ordered -ary tree of every positive height , outputs all root bits, and restores all initially arbitrary dimension- ring registers. Its simultaneous bounds are
All positive constants and the integer degree precede the varying arity, frames, trees and register contents. There is no upper bound on relative to . This companion theorem extends the binary framework and supplies the higher-arity bound used in blocking.
Differences from the source:
- encoding: asymptotic algorithmic resource bounds → a finite binary machine and positive uniform constants, with fixed polynomial degrees where needed; reason: expands O/poly using actual transitions and visited work cells; constants precede varying inputs and tapes
- encoding: uniform access algorithms and common space s in the section setting → a parameterized frame, two fixed binary printers, a common bound A, and auxiliary-parameter length at most 2^(A s); reason: makes Remark 3.8 access and input-size conventions explicit; constants depend on the fixed access procedures, never on their inputs
- encoding: r-ary trees and r+1 registers of dimension d → Fin r child positions, lexicographic full tables and binary serialization of exactly r+1 original-dimension registers; reason: encodes the same data, extends the published binary preorder, and charges any initialized zero padding to local workspace
- encoding: log k in bookkeeping → L(k)=1+log₂(k+1); reason: the additive constant is absorbed by log m and log r for m>1 and r≥2
import Definitions.Def_CatalyticTreeEval_Main_Supplement_HigherFramework set_option autoImplicit false
namespace CatalyticTreeEval.Main.Supplement
theorem theorem_4_11 (F : List Bool → Frame) (domain : Set (List Bool))
(MV MD : Machine) (A : ℕ) (hA : 0 < A)
(h : ∀ a ∈ domain, (F a).valid ∧ a.length ≤ 2 ^ (A * (F a).s) ∧ (F a).access a MV MD A) :
∃ (M : Machine) (Cs Ct Cr B : ℝ) (q : ℕ),
0 < Cs ∧ 0 < Ct ∧ 0 < Cr ∧ 0 < B ∧ 0 < q ∧
∀ a ∈ domain, ∀ h : ℕ, 0 < h →
∀ (I : ArityTree (F a).r (F a).l h)
(R : Registers (F a).r (F a).m (F a).d),
RegisterComputes M (listCode ((F a).params a) ++ I.encode) (bits (F a).l I.value.val) R
(Cs * ((F a).r * (F a).l +
h * (lg (F a).k + log₂ (F a).m + log₂ (F a).r) + (F a).s))
(Ct * exp₂ (Cr * h * log₂ (F a).r) * (B * (F a).k) ^ h *
((2 : ℝ) ^ ((F a).r * (F a).l) + (F a).k + (F a).d + (2 : ℝ) ^ (F a).s) ^ q) := by sorry
end CatalyticTreeEval.Main.Supplement