# Kolmogorov Complexity of the composition of two computable functions

Let's suppose we encode two computable functions $$f$$ and $$g$$ as binary strings so $$f,g \in \{0,1\}^*$$. What I am curious about is whether we can find good upper and lower bounds for:

$$$$K(f \circ g) \tag{1}$$$$

where $$K(\cdot)$$ denotes Kolmogorov Complexity.

My intuition suggests that we can compress each function separately and therefore:

$$$$K(f \circ g) \leq K(f) + K(g) \tag{2}$$$$

and in general I think we can demonstrate that:

$$$$K(f_n \circ f_{n-1} \circ ... \circ f_1) \leq \sum_{i=1}^n K(f_i) \tag{3}$$$$

However, my intuition also suggests that this is probably not the best upper bound and I am also curious about tight lower bounds.

Might there be a general theorem that gives the best possible upper and lower bounds?

• Wouldn't there be a logarithmic overhead to separate the descriptions of $f$ and $g$? Or is this prefix-free Kolmogorov complexity? – Emil Jeřábek Jan 9 at 8:09
• Function composition should be no easier than ordered pairs. Given functions $f(x)$ and $g(x)$, let $f'$ and $g'$ be the functions $f'(x)=(f(x),x)$ and $g'((x,y))=(x,g(y))$. Then $K(f')=K(f)+O(1)$, $K(g')=K(g)+O(1)$, and $K((f,g))\le K(g'\circ f')+O(1)$. – Emil Jeřábek Jan 9 at 9:41