Enumerations including laconic enumerators

DOI10.1016/J.TCS.2017.08.001MaRDI QIDQ2410366zbMATH OpenOpenAlexFDO

Authors 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 randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Turing machines and related notions (03D10)

Recommendations

• scientific article; zbMATH DE number 1028226
• scientific article; zbMATH DE number 4006240
• Regular enumerations
• Enumeration by e
• A Course in Enumeration
• Numeration and enumeration
• Exact enumerations
• Exact enumerations
• An Introduction to Enumeration

Cites work

• A proof of Beigel's cardinality conjecture
• Algorithmic randomness and complexity.
• An introduction to Kolmogorov complexity and its applications
• Complexity of complexity and strings with maximal plain and prefix Kolmogorov complexity
• Enumerations of the Kolmogorov function
• Frequency computations and the cardinality theorem
• Index sets and universal numberings
• Information-theoretic characterizations of recursive infinite strings
• On approximate decidability of minimal programs
• Optimal enumerations and optimal gödel numberings
• Short lists for shortest descriptions in short time
• Short lists with short programs from programs of functions and strings
• Short lists with short programs in short time
• Short lists with short programs in short time -- a short proof
• The complexity of the set of nonrandom numbers
• Three approaches to the quantitative definition of information^*

Cited in

(6)

• On approximate decidability of minimal programs
• Enumerations of the Kolmogorov function
• Kolmogorov complexity of enumerating finite sets
• Searching for shortest and least programs
• Enumeration (18th–20th centuries)
• Short lists with short programs from programs of functions and strings

This page was built for publication: Enumerations including laconic enumerators

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2410366)