Program size complexity for possibly infinite computations
From MaRDI portal
Publication:558440
DOI10.1305/NDJFL/1107220673zbMATH Open1102.68036DBLPjournals/ndjfl/BecherFNP05OpenAlexW2021017634WikidataQ61927042 ScholiaQ61927042MaRDI QIDQ558440FDOQ558440
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
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
- Title not available (Why is that?)
- Process complexity and effective random tests
- A Theory of Program Size Formally Identical to Information Theory
- 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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Information-theoretic characterizations of recursive infinite strings
- Title not available (Why is that?)
- Relations between varieties of kolmogorov complexities
- Algorithmic entropy of sets
- Title not available (Why is that?)
Cited In (8)
- Randomness and universal machines
- Kolmogorov-Complexity Based on Infinite Computations
- Kolmogorov complexity for possibly infinite computations
- Degrees of monotone complexity
- Kolmogorov complexity in perspective. I: Information theory and randomness
- On the information carried by programs about the objects they compute
- Kolmogorov complexities \(K_{\max}\), \(K_{\min}\) on computable partially ordered sets
- 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)
