2
$\begingroup$

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

$\endgroup$
11
  • 2
    $\begingroup$ 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. $\endgroup$
    – WhatsUp
    Mar 14 '20 at 18:32
  • 1
    $\begingroup$ Yes, part 1 is now a clear statement to me. $\endgroup$
    – WhatsUp
    Mar 14 '20 at 19:42
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 15 '20 at 3:57
  • 1
    $\begingroup$ @DanTuretsky But what if for given $x$, the computation of $g(x)$ converges even though $g$ is not total? $\endgroup$
    – Wojowu
    Mar 15 '20 at 10:18
  • 1
    $\begingroup$ @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. $\endgroup$ Mar 16 '20 at 6:24
1
$\begingroup$

Alexander Shen gave the full answer: https://arxiv.org/abs/2004.02844

$\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.