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...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2017-11, Vol.700, p.89-95
Main Authors: Jain, Sanjay, Teutsch, Jason
Format: Article
Language:English
Subjects:
Kolmogorov complexity
Kolmogorov numberings
List approximations
Minimal programs
Recursion theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2017.08.001