Short lists with short programs for functions
Nikolay Vereshchagin · arXiv (Cornell University) · 2014
Let $\{ϕ_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 $ϕ$-program for $ϕ_p$ whose length is at most $\varepsilon$ bits larger that the length of the shortest $ϕ$-program for $ϕ_p$. We show that for infinitely many $p$ the list $L(p)$ must have $2^{|p|-\varepsilon-O(1)}$ strings. Here $\varepsilon$ is an arbitrary function of $p$.