Abstract
The minimal Kolmogorov complexity of a total computable function that exceeds everywhere all total computable functions of complexity at most n, is 2 n+O(1). If "everywhere" is replaced by "for all sufficiently large inputs", the answer is n + O(1). The notion of Kolmogorov complexity of computable function was first considered by Schnorr [1]. The (plain) complexity of a computable function is the minimal length of a program that computes this function. As usual, we require that the programming language is optimal, i.e., leads to a minimal complexity up to O(1). One can also define the plain complexity of a function as the minimal complexity of its programs. In this case we may use any Gödel numbering of programs. Consider all total computable functions that have complexity at most n. Alexey Milovanov asked the following question: What is a minimal complexity of a total computable function that exceeds all of them?