$\newcommand{\Prog}{\operatorname{Prog}}\newcommand{\kol}{\operatorname{kol}}$ Disclaimer: I do not have a formal background in algorithmic complexity theory so apologies if I use non-standard notation.

Fix a language $L$. Let $C$ be the set of computable functions $\mathbb N\to\mathbb N$. Further, denote with

$$ \Prog(f) = \{p\in L\mid p\text{ describes }f\}$$

the set of (computable) descriptions of $f$ in the language $L$ and the length of a program by $|p|$.

Given a function $f\in C$ and a (computable) description $p_f\in\Prog(f)$, let's define the following:

Call $p_f$ "kolmogorov efficient" if and only if it is shorter than the description of any program of any other computable function $g\in C$, if $f$ and $g$ agree for sufficiently many inputs. That is $p_f$ is efficient if and only if

$$\forall g\in C\exists n_0\in\mathbb N\forall n\ge n_0 \Big[f\big|_{[0, n]} = g\big|_{[0,n]} \implies\forall q\in\Prog(g) : |p_f|\le |q| \Big]$$

Note that since we are allowed to choose $g=f$, $p_f$ must be a shortest description of $f$. Further, we call $f\in C$ "simple" if and only if $$\exists p_f \in \Prog(f): p_f \text{ is kolmogorov efficient} $$

My questions:

  1. Does this notion exists already? Maybe under another name?
  2. Are all computable functions simple?
  3. If not, is there a way to figure out if a function is simple (sufficient/necessary criteria?)

Remark I came up with this definition whilst pondering how to formalize Occam's razor & inductive learning. Consider for example a classical intelligence test question:

extent the sequence 1,2,4,8,16, ...

Of course, given a finite length sequence there are infinitely many ways to continue it (e.g. take any interpolating polynomial). However the "obvious" answer, $f(n) = 2^n$, stands out in regards to having low kolmogorov complexity. So given that we only observe a finite sequence, the simple function is supposedly the preferred solution.

  • $\begingroup$ Your notion appears related to a "minimal Turing machine". $\endgroup$
    – Aryeh
    Feb 28 '20 at 14:15
  • 2
    $\begingroup$ Is something wrong with your formal definition of $p_f$ being "Kolmogorov efficient"? It is $$\forall g\in C\exists n_0\in\mathbb N\forall n\ge n_0 \Big[f\big|_{[0, n]} = g\big|_{[0,n]} \implies\forall q\in\Prog(g) : |p_f|\le |q| \Big].$$ Given that $|p_f|=K(f)$ (the K-complexity of $f$), the condition $\forall q\in\Prog(g) : |p_f|\le |q|$ is that $K(f) \le K(g)$. This condition is independent of $n$! So the definition simplifies to $$(\forall g\in C)~ K(g)< K(f) \implies g\not\equiv f,$$ which is trivially true. So $p_f$ is efficient" iff $|p_f| = K(f)$. Am I missing something? $\endgroup$
    – Neal Young
    Feb 28 '20 at 17:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.