ИСТИНА

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 ε 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|−ε−O(1) strings. Here ε is an arbitrary function of p.