On minimal-program complexity measures

DOI10.1145/800169.805422MaRDI QIDQ5402506zbMATH OpenOpenAlexFDO

Authors Donald W. Loveland

Publication date 14 March 2014

Published in Proceedings of the first annual ACM symposium on Theory of computing - STOC '69 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/800169.805422

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computability and recursion theory (03D99)

Recommendations

• Binary sequences. I: Complexity
• Descriptive complexity of computable sequences
• scientific article; zbMATH DE number 1304316
• Kolmogorov-Complexity Based on Infinite Computations
• scientific article; zbMATH DE number 3999902

Cited in

(25)

• Program size complexity for possibly infinite computations
• Strict process machine complexity
• scientific article; zbMATH DE number 5117088 (Why is no real title available?)
• Binary sequences. I: Complexity
• Descriptive complexity of computable sequences revisited
• scientific article; zbMATH DE number 4047104 (Why is no real title available?)
• Kolmogorov-Complexity Based on Infinite Computations
• A unified approach to the definition of random sequences
• Straight-line program length as a parameter for complexity measures
• On the problem of finding minimal programs for tables
• Descriptive complexity of computable sequences
• The extent and density of sequences within the minimal-program complexity hierarchies
• A note on Blum static complexity measures
• On the complexity of semantic self-minimization
• scientific article; zbMATH DE number 3847369 (Why is no real title available?)
• On the Turing degrees of minimal index sets
• Kolmogorov complexity of enumerating finite sets
• Sequential predictions based on algorithmic complexity
• Measuring static complexity
• Computation of recursive functionals using minimal initial segments
• scientific article; zbMATH DE number 4045148 (Why is no real title available?)
• LISP program-size complexity. III
• scientific article; zbMATH DE number 3596250 (Why is no real title available?)
• scientific article; zbMATH DE number 3999902 (Why is no real title available?)
• Minimal-program complexity of pseudo-recursive and pseudo-random sequences

This page was built for publication: On minimal-program complexity measures

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