Short lists with short programs for functions

Nikolay Vereshchagin

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)$ i…