Definition 2.2 — complete ordered variable-arity tree evaluation
DefinitionCatalyticTreeEval_Main_Supplement_HigherEncodingFor integers , and , a complete ordered -ary tree of height has an arbitrary -bit label at each leaf and an arbitrary function from labels to one label at each internal node. Its value is obtained by applying each gate to its children's values. The required output is the whole root label.
The serialization lists each gate's full truth table in lexicographic argument order, followed by its children in position order; leaves contribute their labels. Thus
Height and label length use the published binary headers; arity is provided in the framework header. At , the embedding from the published binary tree has exactly the same payload and headers. Full truth tables remain input data, without an oracle that reads them at unit cost. This is the source model needed for the higher-arity companion theorem.
import Definitions.Def_CatalyticTreeEval_Main_Encoding
set_option autoImplicit false
namespace CatalyticTreeEval.Main.Supplement
/-- Ordered r-tuples in lexicographic order, first coordinate most significant. -/
def tuples (r l : ℕ) : List (Fin r → Label l) :=
(List.finRange ((2 ^ l) ^ r)).map fun a i =>
⟨(a.val / (2 ^ l) ^ (r - 1 - i.val)) % (2 ^ l), Nat.mod_lt _ (by positivity)⟩
/-- The complete ordered r-ary tree; no promise is made about node functions. -/
inductive ArityTree (r l : ℕ) : ℕ → Type
| leaf : Label l → ArityTree r l 0
| node {h : ℕ} : ((Fin r → Label l) → Label l) →
(Fin r → ArityTree r l h) → ArityTree r l (h + 1)
def ArityTree.value {r l h : ℕ} : ArityTree r l h → Label l
| .leaf v => v
| .node f children => f (fun i => (children i).value)
def arityTableCode {r l : ℕ} (f : (Fin r → Label l) → Label l) : List Bool :=
(tuples r l).flatMap fun y => bits l (f y).val
def ArityTree.payload {r l h : ℕ} : ArityTree r l h → List Bool
| .leaf v => bits l v.val
| .node f children => arityTableCode f ++
(List.finRange r).flatMap (fun i => (children i).payload)
/-- At r=2 the payload and h,l headers agree with the binary encoding.
The arity is supplied in the separate framework parameter header. -/
def ArityTree.encode {r l h : ℕ} (I : ArityTree r l h) : List Bool :=
natCode h ++ natCode l ++ I.payload
/-- Explicit embedding for checking agreement with the published binary model. -/
def fromBinary {l h : ℕ} : Tree l h → ArityTree 2 l h
| .leaf v => .leaf v
| .node f a b => .node (fun x => f (x 0) (x 1))
(fun i => if i = 0 then fromBinary a else fromBinary b)
end CatalyticTreeEval.Main.Supplement