<p><span class="math-container">$\newcommand{\Prog}{\operatorname{Prog}}\newcommand{\kol}{\operatorname{kol}}$</span>
<strong>Disclaimer:</strong> I do not have a formal background in algorithmic complexity theory so apologies if I use non-standard notation.</p>

<p>Fix a language <span class="math-container">$L$</span>. Let <span class="math-container">$C$</span> be the set of computable functions <span class="math-container">$\mathbb N\to\mathbb N$</span>. Further, denote with</p>

<p><span class="math-container">$$ \Prog(f) = \{p\in L\mid p\text{ describes }f\}$$</span></p>

<p>the set of (computable) descriptions of <span class="math-container">$f$</span> in the language <span class="math-container">$L$</span> and the length of a program by <span class="math-container">$|p|$</span>.</p>

<p>Given a function <span class="math-container">$f\in C$</span> and a (computable) description <span class="math-container">$p_f\in\Prog(f)$</span>, let's define the following:</p>

<p>Call <span class="math-container">$p_f$</span> <strong>"kolmogorov efficient"</strong> if and only if it is shorter than the description of any program of any other computable function <span class="math-container">$g\in C$</span>, if <span class="math-container">$f$</span> and <span class="math-container">$g$</span> agree for sufficiently many inputs. That is <span class="math-container">$p_f$</span> is efficient if and only if</p>

<p><span class="math-container">$$\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]$$</span></p>

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

<p><strong>My questions:</strong></p>

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

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

<blockquote>
  <p>extent the sequence 1,2,4,8,16, ... </p>
</blockquote>

<p>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, <span class="math-container">$f(n) = 2^n$</span>, 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. </p>

CC BY-SA 4.0
2020-02-28T14:15:43.750Z
Your notion appears related to a "minimal Turing machine".
Aryeh
CC BY-SA 4.0
2020-02-28T17:07:40.420Z
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?
Neal Young
<cc.complexity-theory><kolmogorov-complexity>
existence & characterization of "kolmogorov efficient" programs
Hyperplane
# existence & characterization of "kolmogorov efficient" programs

(Asked by: username_0 on 2020-02-28)

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

**Tags:** cc.complexity-theory, kolmogorov-complexity
> **Comments:**
> **username_1**: Your notion appears related to a "minimal Turing machine".  
> **username_2**: 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?  

---

## 0 answers

