Kolmogorov entropy in the context of computability theory

AbstractWe consider the overgraph of the Kolmogorov entropy function and study whether it is a complete enumerable set with respect to different types of reductions. It turns out that (for any type of entropy) the overgraph of the conditional entropy function is m-complete, but the overgraph of the unconditional entropy function is not m-complete (and also not bT-complete). For tt-completeness, the situation is more subtle: the overgraph of the unconditional prefix entropy may be tt-complete or incomplete depending on the optimal programming system used in the definition of entropy. To prove these results we use the notion of r-separability and its effective version introduced in this article for the first time