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, 2017 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$ Oct 14, 2017 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$ Oct 15, 2017 at 1:44

1 Answer 1

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 and acknowledge you have read our privacy policy.

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