# The expressiveness of functions computable on trees

## Motivation:

Let's define a function computable on a $$k$$-ary tree as a function composed with simpler computable functions defined at each node such that a function of this kind defined on a binary tree of depth $$N$$ receives $$2^{N-1}$$ inputs:

While thinking about the expressiveness of functions $$F_k^N$$ computable on $$k$$-ary trees it occurred to me that the 'combinatorial power' of such functions must grow exponentially as a function of tree depth. This would be very nice because it's natural to execute parallel algorithms with $$O(N)$$ time complexity on $$k$$-ary trees with depth $$N$$.

Intuitively, if there are $$k^n$$ functions at the nth level the expressiveness for $$F_k^N$$ on a tree of depth $$N$$ should grow on the order of:

$$$$\sim k^N \tag{1}$$$$

Might there be a theorem which expresses this idea using algorithmic information theory(i.e. Kolmogorov Complexity)?

## Probabilistic argument using Kolmogorov Complexity:

If $$F_k^N$$ is a composition of functions in $$S$$ where $$\lvert S \rvert = \frac{k^{N}-1}{k-1}$$ and $$K(\cdot)$$ denotes Kolmogorov Complexity then we may define:

$$$$Q = \min_{f_i \in S} K(f_i) \tag{2}$$$$

and we may show that for almost all $$F_k^N$$ we must have:

$$$$K(F_k^N) \geq \frac{Q}{2} \cdot k^{N-1} \tag{3}$$$$

Proof:

Let's suppose each $$f_i \in S$$ has an encoding as a binary string so $$\forall i, f_i \in \{0,1\}^*$$. If we compress each $$f_i$$ then $$F_k^N$$ is reduced to a program of length greater than:

$$$$n= Qk^{N -1} \tag{4}$$$$

Now, the number of programs of length less than or equal to $$\frac{n}{2}$$ is given by:

$$$$\sum_{l=1}^{\frac{n}{2}} 2^l \leq 2^{\frac{n}{2}+1}-1 \tag{5}$$$$

and so, using the principle of maximum entropy(i.e. uniform distribution) [4], we find that:

$$$$\lim_{n \to \infty} P(K(F_k^N) \geq \frac{n}{2}) \geq \lim_{n \to \infty} 1 - \frac{2^{\frac{n}{2}}}{2^n} = 1 \tag{6}$$$$

## Question:

My question is whether this result (3) in the setting of algorithmic information theory may be significantly improved upon and whether there might be other interesting results of this kind.

## References:

1. Vladimir I Arnold. Representation of continuous functions of three variables by the superposition of continuous functions of two variables. Collected Works: Representations of Functions, Celestial Mechanics and KAM Theory, 1957–1965, pages 47–133, 2009.
2. Roozbeh Farhoodi, Khashayar Filom, Ilenna Simone Jones, Konrad Paul Kording. On functions computed on trees. Arxiv. 2019.
3. M. Li and P. Vitányi. An Introduction to Kolmogorov Complexity and Its Applications. Graduate Texts in Computer Science. Springer, New York, second edition, 1997.
4. Edwin Jaynes. Information Theory and Statistical Mechanics. The Physical Review. Vol. 106. No 4. 620-630. May 15, 1957.
• Where does your ${N\choose 2}$ term come from? That's not the count of either internal, external or total nodes of the tree, and I'm not sure what its origin is here. Commented Jan 9, 2020 at 0:09
• @StevenStadnicki Thanks for pointing that out. This was a counting error. Commented Jan 9, 2020 at 0:18
• I wonder whether it would be better to use the existing tag (computability-theory) rather than creating a new tag (computable-functions). Commented Jan 12, 2020 at 9:08