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$?

a function $f$ with complexity not greater than $d+O(1)$exactly mean? It's as ambiguous as the phrasea 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. $\endgroup$6more comments