Information-theoretic characterizations of recursive infinite strings
From MaRDI portal
Publication:1226484
DOI10.1016/0304-3975(76)90005-0zbMath0328.02029MaRDI 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
68Q25: Analysis of algorithms and problem complexity
94A15: Information theory (general)
03D80: Applications of computability and recursion theory
Related Items
Trivial Reals, Random Continuous Functions, On very high degrees, Enumerations of the Kolmogorov function, Descriptive complexity of computable sequences, Randomness notions and partial relativization, Computably enumerable sets below random sets, 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, 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, Truth-table Schnorr randomness and truth-table reducible randomness, Universal Recursively Enumerable Sets of Strings
Cites Work
