• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site

Article

Short lists with short programs from programs of functions and strings

Theory of Computing Systems. 2017. Vol. 61. No. 4. P. 1440-1450.

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 than the length of the shortest φ-programs 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. Short lists with short programs from programs of functions and strings.