# existence & characterization of "kolmogorov efficient" programs

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

• Your notion appears related to a "minimal Turing machine". Feb 28 '20 at 14:15
• 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? Feb 28 '20 at 17:07