# Reasonable estimate of an asymptotic limit notion of Kolmogorov complexity

Let $$f(c)=\min_{x \ge c} K(x)$$ where $K(x)$ is the kolmogorov complexity of $x$. Since $K(x)$ is always a natural number, there will always be a minimum. My question is, what is the growth rate of $f$? We know that $$f \in \mathcal O(1) + \log c$$ since $f(c)\le K(c) \in \mathcal O(1) + \log c$. We also know $f$ is increasing, since if $c_1 \ge c_2$, then $\min_{x \ge c_1} K(x) \ge \min_{x \ge c_2} K(x)$. We also know that $$\lim_{c\to\infty}f(c)=\infty$$ since otherwise a finite number of programs would be able to generate arbitrarily large outputs.

Can we get a tigher bounds on $f$? What is $f$'s growth rate?

• Very interesting. Intuitively I think that $f$'s grow rate is lower than that of any computable non-constant function $g \in \Omega(1)$. – Lwins Oct 14 '17 at 20:11
• @Lwins Even more interesting if to consider $c$ such that $f(c)=K(c)$. This are maximally compressible strings, in the sense that they compress at least as well as any larger string. – PyRulez Oct 14 '17 at 20:15
• I am not qualified to answer, but I think $O(1) + \log_2 B^{-1}(n)$ is an upper bound, where $B^{-1}$ is the inverse of the Busy Beaver function. Maybe this is tight as well. – Sasho Nikolov Oct 15 '17 at 1:44

## 1 Answer

As commenters @Lwins and @SashaNikolov have already stated, it is non-computably hard to compute a function as slow-growing as $f$. (So no really humanly comprehensible rate can be given.)

Namely, suppose we just have one direction of your equality: $f(c)\le\min_{x\ge c} K(x)$, but suppose $f$ does goes to infinity monotonically.

Then $x\ge c$ implies $K(x)\ge f(c)$. So given $n$, if we find $c$ with $f(c)\ge n$ then $K(c)\ge n$. So letting $F(n)=c$ we have a function $F$ with $K(F(n))\ge n$ for all $n$.

But according to Theorem 4.1 of my paper with Merkle and Stephan, this allows us to compute a diagonally non-computable function with finite range, i.e., it allows us to compute a complete extension of Peano arithmetic.