# Complexity of majorants

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?
Keywords :
Document type :
Preprints, Working Papers, ...
Domain :

https://hal-lirmm.ccsd.cnrs.fr/lirmm-03059689
Contributor : Alexander Shen <>
Submitted on : Saturday, December 12, 2020 - 11:45:14 PM
Last modification on : Friday, May 21, 2021 - 8:22:02 PM

### File

2004.02844.pdf
Files produced by the author(s)

### Identifiers

• HAL Id : lirmm-03059689, version 1

### Citation

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

Record views