# The fastest growing function of given complexity

Let $$f$$ be a computable function $$\mathbb{N} \to \mathbb{N}$$ be a computable function. Since a program of a computable function is a finite object we can define plain Kolmogorov complexity of $$f$$ (we can identify programs as Turing machines, for example).

Now I will talk only about total computable functions.

1) Is there a function $$f$$ with complexity not greater than $$d + O(1)$$ such that for every $$g \in \mathcal{F}_d$$---the set of function with complexity atmost $$d$$---and for every $$x \in \mathbb{N}$$ it holds that $$f(x) \ge g(x)$$?

More precisely: Is there $$C$$ such that for every $$d$$ there exists $$f$$ with Kolmogorov complexity at most $$d + C$$ such that for every $$g$$ with Kolmogorov complexity at most $$d$$ and for every $$x \in \mathbb{N}$$ it holds that $$f(x) \ge g(x)$$?

2) Is there a function $$f$$ with complexity not greater than $$d + O(1)$$ that growing at $$\infty$$ faster than any function in $$\mathcal{F}_d$$, i.e. there exists $$C$$ such that for every $$g \in \mathcal{F}_d$$ and for every $$x >C$$ it holds that $$f(x) \ge g(x)$$?

3) Is there a rather small subset $$F$$ (say, $$|F| = \text{poly}(d)$$) of functions with complexity not greater than $$d + O(1)$$ such that for every $$g\in \mathcal{F}_d$$ there exists $$f \in F$$ that grows faster than $$g$$?

• To me the question is even more confusing after changing to $d+O(1)$. What does a function $f$ with complexity not greater than $d+O(1)$ exactly mean? It's as ambiguous as the phrase a number not greater than $d+O(1)$. I suggest that you rephrase your question in standard first order logic statements instead of notions such as $O(1)$. For the ambiguity of Kolmogorov complexity, it's perhaps better to fix a language first and then argue the effect of changing the language. Mar 14 '20 at 18:32
• Yes, part 1 is now a clear statement to me. Mar 14 '20 at 19:42
• Is this plain complexity or prefix-free? With plain, the answer to 2 is yes, since d + O(1) bits is enough to specify how many functions of complexity at most d are total. So a function can wait until that many have converged up to a given value, then output the max. Mar 15 '20 at 3:57
• @DanTuretsky But what if for given $x$, the computation of $g(x)$ converges even though $g$ is not total? Mar 15 '20 at 10:18
• @Wojowu You wait until you see the appropriate number converging on all $y \le x$. For sufficiently large $x$, all non-total $g$ of complexity $\le d$ will fail to converge on some $y \le x$. This is why it works for 2 but not 1. Mar 16 '20 at 6:24