Program size complexity for possibly infinite computations

DOI10.1305/NDJFL/1107220673MaRDI QIDQ558440zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Verónica Becher, Santiago Figueira, André Nies, Silvana Picchi

Publication date 6 July 2005

Published in Notre Dame Journal of Formal Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1305/ndjfl/1107220673

zbMATH Keywords

Kolmorogov complexityTuring monotone machines

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Kolmogorov complexity for possibly infinite computations
• Random reals and possibly infinite computations Part I: Randomness in ∅′
• Kolmogorov-Complexity Based on Infinite Computations
• On minimal-program complexity measures
• Chaitin complexity, Shannon information content of a single event, and infinite random sequences. II

Cites work

• scientific article; zbMATH DE number 1633149 (Why is no real title available?)
• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• scientific article; zbMATH DE number 3489017 (Why is no real title available?)
• scientific article; zbMATH DE number 3492569 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 2063218 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic entropy of sets
• Information-theoretic characterizations of recursive infinite strings
• Process complexity and effective random tests
• Relations between varieties of kolmogorov complexities
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences

Cited in

(8)

• Randomness and universal machines
• On the information carried by programs about the objects they compute
• Kolmogorov complexity in perspective. I: Information theory and randomness
• Kolmogorov complexities \(K_{\max}\), \(K_{\min}\) on computable partially ordered sets
• Kolmogorov-Complexity Based on Infinite Computations
• Kolmogorov complexity for possibly infinite computations
• Degrees of monotone complexity
• Random numbers as probabilities of machine behavior

This page was built for publication: Program size complexity for possibly infinite computations

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