Information-theoretic characterizations of recursive infinite strings

DOI10.1016/0304-3975(76)90005-0MaRDI QIDQ1226484zbMATH OpenOpenAlexFDO

Authors Gregory J. Chaitin

Publication date 1976

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

Full work available at URL https://doi.org/10.1016/0304-3975(76)90005-0

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) Applications of computability and recursion theory (03D80)

Cites work

• A Theory of Program Size Formally Identical to Information Theory
• A variant of the Kolmogorov concept of complexity
• Information-Theoretic Incompleteness
• Process complexity and effective random tests

Cited in

(38)

• Program size complexity for possibly infinite computations
• Random semicomputable reals revisited
• Randomness and initial segment complexity for measures
• Universal recursively enumerable sets of strings
• Algorithmic entropy of sets
• Kolmogorov complexity for possibly infinite computations
• \(K\)-triviality in computable metric spaces
• On the gap between trivial and nontrivial initial segment prefix-free complexity
• Oreals with \(\Delta_2^0\)-bounded complexity and compressive power
• Strong jump-traceability. I: The computably enumerable case
• Lowness properties and approximations of the jump
• The frequent paucity of trivial strings
• Computably enumerable sets below random sets
• Descriptive complexity of computable sequences
• Several results in program size complexity
• Inherent enumerability of strong jump-traceability
• Philosophical issues in Kolmogorov complexity
• Lowness for effective Hausdorff dimension
• Lowness, Randomness, and Computable Analysis
• On very high degrees
• Enumerations of the Kolmogorov function
• A measure-theoretic proof of Turing incomparability
• Upper bounds on ideals in the computably enumerable Turing degrees
• Searching for shortest and least programs
• Universal Recursively Enumerable Sets of Strings
• Enumerations including laconic enumerators
• Strong jump-traceability
• Lowness properties and randomness
• Solovay functions and their applications in algorithmic randomness
• Cone avoidance and randomness preservation
• On the number of infinite sequences with trivial initial segment complexity
• Trivial Reals
• Truth-table Schnorr randomness and truth-table reducible randomness
• Toward an abstract theory of data compression
• Algorithmic randomness of continuous functions
• Random Continuous Functions
• Randomness notions and partial relativization
• Computuing \(K\)-trivial sets by incomplete random sets

This page was built for publication: Information-theoretic characterizations of recursive infinite strings

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