Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Complexity of majorants

Alexander Shen 1
1 ESCAPE - Systèmes complexes, automates et pavages
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
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?
Document type :
Preprints, Working Papers, ...
Complete list of metadata
Contributor : Alexander Shen <>
Submitted on : Saturday, December 12, 2020 - 11:45:14 PM
Last modification on : Friday, May 21, 2021 - 8:22:02 PM


Files produced by the author(s)


Distributed under a Creative Commons Attribution 4.0 International License


  • HAL Id : lirmm-03059689, version 1



Alexander Shen. Complexity of majorants. 2020. ⟨lirmm-03059689⟩



Record views


Files downloads