2
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ Very interesting. Intuitively I think that $f$'s grow rate is lower than that of any computable non-constant function $g \in \Omega(1)$. $\endgroup$ – Lwins Oct 14 '17 at 20:11
  • $\begingroup$ @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. $\endgroup$ – PyRulez Oct 14 '17 at 20:15
  • 2
    $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Oct 15 '17 at 1:44
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.