Short lists with short programs for functions

Abstract

Let $\{{\varphi }_p\}$ be an optimal Gödel numbering of the family of computable functions (in Schnorr's sense), where $p$ ranges over binary strings. Assume that a list of strings $L(p)$ is computable from $p$ and for all $p$ contains a $\varphi$-program for ${\varphi }_p$ whose length is at most $\epsilon$ bits larger that the length of the shortest $\varphi$-program for ${\varphi }_p$. We show that for infinitely many $p$ the list $L(p)$ must have $2^{|p|-\epsilon -O(1)}$ strings. Here $\epsilon$ is an arbitrary function of $p$.

References in corpus (1)

• On approximate decidability of minimal programs