On Extremal Relations between Additive Loss Functions and the Kolmogorov Complexity

Conditions are presented under which the maximum of the Kolmogorov complexity (algorithmic entropy) $K(\omega_1\dots\omega_N)$ is attained, given the cost $\sum_{i=1}^Nf(\omega_i)$ of a message $\omega_1\dots\omega_N$. Various extremal relations between the message cost and the Kolmogorov complexity are also considered; in particular, the minimization problem for the function $\sum_{i=1}^Nf(\omega_i)-\theta K(\omega_1\dots\omega_N)$ is studied. Here, $\theta$ is a parameter, called the temperature by analogy with thermodynamics. We also study domains of small variation of this function.