Enumerations including laconic enumerators

DOI10.1016/j.tcs.2017.08.001zbMath1383.68040OpenAlexW2747848014MaRDI QIDQ2410366

Sanjay Jain, Jason Teutsch

Publication date: 17 October 2017

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2017.08.001

zbMATH Keywords

Kolmogorov complexityrecursion theoryKolmogorov numberingslist approximationsminimal programs

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Turing machines and related notions (03D10) Algorithmic randomness and dimension (03D32)

Related Items (2)

Searching for shortest and least programs ⋮ On Approximate Decidability of Minimal Programs

Cites Work

• Unnamed Item
• Short lists for shortest descriptions in short time
• Index sets and universal numberings
• Information-theoretic characterizations of recursive infinite strings
• Short lists with short programs from programs of functions and strings
• Short lists with short programs in short time
• On Approximate Decidability of Minimal Programs
• COMPLEXITY OF COMPLEXITY AND STRINGS WITH MAXIMAL PLAIN AND PREFIX KOLMOGOROV COMPLEXITY
• Algorithmic Randomness and Complexity
• A proof of Beigel's cardinality conjecture
• Frequency computations and the cardinality theorem
• Optimal enumerations and optimal gödel numberings
• Short Lists with Short Programs in Short Time – A Short Proof
• Enumerations of the Kolmogorov function
• Three approaches to the quantitative definition of information^*
• An introduction to Kolmogorov complexity and its applications

This page was built for publication: Enumerations including laconic enumerators