Short lists with short programs from programs of functions and strings

DOI10.1007/S00224-017-9773-XzbMath1423.03140OpenAlexW2613435100MaRDI QIDQ1694012

Nikolai K. Vereshchagin

Publication date: 1 February 2018

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-017-9773-x

zbMATH Keywords

Gödel numberingKolmogorov numberingoptimal Gödel numberingshort list problem

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Recursive functions and relations, subrecursive hierarchies (03D20) Algorithmic randomness and dimension (03D32)

Related Items (2)

Enumerations including laconic enumerators ⋮ Searching for shortest and least programs

Cites Work

• Short lists with short programs in short time
• On Approximate Decidability of Minimal Programs
• Optimal enumerations and optimal gödel numberings

This page was built for publication: Short lists with short programs from programs of functions and strings