Information-theoretic characterizations of recursive infinite strings
From MaRDI portal
Publication:1226484
DOI10.1016/0304-3975(76)90005-0zbMath0328.02029OpenAlexW1997686864MaRDI QIDQ1226484
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
Analysis of algorithms and problem complexity (68Q25) Information theory (general) (94A15) Applications of computability and recursion theory (03D80)
Related Items
Random Semicomputable Reals Revisited, COMPUTINGK-TRIVIAL SETS BY INCOMPLETE RANDOM SETS, Randomness notions and partial relativization, STRONG JUMP-TRACEABILITY, Enumerations including laconic enumerators, Several results in program size complexity, On the gap between trivial and nontrivial initial segment prefix-free complexity, Lowness, Randomness, and Computable Analysis, A measure-theoretic proof of Turing incomparability, Upper bounds on ideals in the computably enumerable Turing degrees, ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER, Computably enumerable sets below random sets, Universal Recursively Enumerable Sets of Strings, Algorithmic randomness of continuous functions, On the number of infinite sequences with trivial initial segment complexity, On very high degrees, Solovay functions and their applications in algorithmic randomness, Truth-table Schnorr randomness and truth-table reducible randomness, Strong jump-traceability. I: The computably enumerable case, Trivial Reals, Lowness properties and approximations of the jump, The frequent paucity of trivial strings, Universal recursively enumerable sets of strings, Random Continuous Functions, Lowness for effective Hausdorff dimension, Program size complexity for possibly infinite computations, Kolmogorov complexity for possibly infinite computations, Descriptive complexity of computable sequences, Algorithmic entropy of sets, Searching for shortest and least programs, Philosophical issues in Kolmogorov complexity, Randomness and initial segment complexity for measures, Enumerations of the Kolmogorov function, $K$-triviality in computable metric spaces, Inherent enumerability of strong jump-traceability, Lowness properties and randomness, Toward an abstract theory of data compression, Cone avoidance and randomness preservation
Cites Work
