Enumerations including laconic enumerators

We show that it is possible, for every machine universal for Kolmogorov complexity, to enumerate the lexicographically least description of a length n string in O ( n ) attempts. In contrast to this positive result for strings, we find that, in any Kolmogorov numbering, no enumerator of nontrivial size can generate a list containing the minimal index of a given partial-computable function. One cannot even achieve a laconic enumerator for nearly-minimal indices of partial-computable functions.

Authors

• Sanjay Jain
• Jason Teutsch

Keywords

• List approximations
• Minimal programs
• Kolmogorov complexity
• Kolmogorov numberings
• Recursion theory