# 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:

$$\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?

• 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 '20 at 8:09
• There are certainly examples where you need much less. For example, if $g$ is addition of a large constant, and $f$ is subtraction of the same constant, then $f\circ g$ is just the identity. The question is what is true for general $f$ and $g$, not for a particular example. – Emil Jeřábek Jan 9 '20 at 8:46
• 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 '20 at 9:41