Kolmogorov Complexity of the composition of two computable functions

Question

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:

\begin{equation} K(f \circ g) \tag{1} \end{equation}

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

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

\begin{equation} K(f \circ g) \leq K(f) + K(g) \tag{2} \end{equation}

and in general I think we can demonstrate that:

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

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?

Answer 1

Your bound is correct, for exactly the reasons you give. It is also unimprovable in general. Suppose that each function is multiplication by a large constant, where both constants are subwords of some infinite incomprehensible sequence. If you could compress the composition, you would be able to compress at least one of the constants—a contradiction.

Edit: You might need to pay additional bits for the composition, as for ordered pairings -- as observed by Emil Jeřábek in the comments.