Information-theoretic characterizations of recursive infinite strings

DOI10.1016/0304-3975(76)90005-0zbMath0328.02029MaRDI QIDQ1226484

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

68Q25: Analysis of algorithms and problem complexity

94A15: Information theory (general)

03D80: Applications of computability and recursion theory

Related Items

STRONG JUMP-TRACEABILITY, Trivial Reals, Random Continuous Functions, Lowness for effective Hausdorff dimension, On very high degrees, Enumerations of the Kolmogorov function, Inherent enumerability of strong jump-traceability, Descriptive complexity of computable sequences, Randomness notions and partial relativization, Computably enumerable sets below random sets, Solovay functions and their applications in algorithmic randomness, Universal recursively enumerable sets of strings, Program size complexity for possibly infinite computations, 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, Toward an abstract theory of data compression, Algorithmic randomness of continuous functions, 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, The frequent paucity of trivial strings, 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, COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS, Lowness, Randomness, and Computable Analysis, ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER, Truth-table Schnorr randomness and truth-table reducible randomness, Universal Recursively Enumerable Sets of Strings

Cites Work

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