<p>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.)</p>

<p>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.</p>

<p>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$.</p>

<p>But according to Theorem 4.1 of <a href="https://arxiv.org/abs/0901.3933" rel="nofollow noreferrer">my paper with Merkle and Stephan</a>, 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.</p>

CC BY-SA 3.0
2017-10-15T02:56:42.950Z
2017-10-15T03:02:37.590Z
2017-10-15T03:02:37.590Z
Bjørn Kjos-Hanssen
<p>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.</p>

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

CC BY-SA 3.0
2017-10-14T20:11:31.053Z
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
CC BY-SA 3.0
2017-10-14T20:15:29.347Z
@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.
Christopher King
CC BY-SA 3.0
2017-10-15T01:44:02.407Z
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
<kolmogorov-complexity><asymptotics>
Reasonable estimate of an asymptotic limit notion of Kolmogorov complexity
Christopher King
# Reasonable estimate of an asymptotic limit notion of Kolmogorov complexity

(Asked by: username_0 on 2017-10-14)

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?

**Tags:** kolmogorov-complexity, asymptotics

> **Comments:**
> **username_1**: Very interesting. Intuitively I think that $f$'s grow rate is lower than that of any computable non-constant function $g \in \Omega(1)$.  
> **username_0**: @username_1 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.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2017-10-15. Score: 2

As commenters @username_1 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](https://arxiv.org/abs/0901.3933), 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.


---

