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

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

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

(39)

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

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)