Lowness properties and randomness

DOI10.1016/j.aim.2004.10.006zbMath1141.03017OpenAlexW1997555168MaRDI QIDQ2570074

Publication date: 26 October 2005

Published in: Advances in Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.aim.2004.10.006

zbMATH Keywords

Randomness $K$-trivial Kolmogorov prefix complexity Low for random

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Other Turing degree structures (03D28)

Related Items

Families of permutations and ideals of Turing degrees, Lowness for genericity, Nullifying randomness and genericity using symmetric difference, Reducibilities relating to Schnorr randomness, On Kurtz randomness, Strengthening prompt simplicity, Randomness, Computation and Mathematics, Splitting into degrees with low computational strength, 2009 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '09, Low for random reals and positive-measure domination, Turing incomparability in Scott sets, Cupping with random sets, CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS, Defining a randomness notion via another, Randomness and universal machines, Strong jump-traceability. II: $K$-triviality, Randomness notions and partial relativization, Lowness and logical depth, STRONG JUMP-TRACEABILITY, Universal computably enumerable sets and initial segment prefix-free complexity, $$\textit{K}$$-trivial, $$\textit{K}$$-low and $${{\mathrm{\textit{MLR}}}}$$-low Sequences: A Tutorial, Randomness, lowness and degrees, Characterizing strong randomness via Martin-Löf randomness, Low upper bounds in the LR degrees, On initial segment complexity and degrees of randomness, Relativized depth, Computing from projections of random points, Oscillation in the initial segment complexity of random reals, Extending and interpreting Post's programme, Elementary differences between the degrees of unsolvability and degrees of compressibility, A $K$-trivial set which is not jump traceable at certain orders, Lowness, Randomness, and Computable Analysis, A measure-theoretic proof of Turing incomparability, Upper bounds on ideals in the computably enumerable Turing degrees, Demuth randomness and computational complexity, ON REALS WITH -BOUNDED COMPLEXITY AND COMPRESSIVE POWER, Computably enumerable sets below random sets, A semilattice generated by superlow computably enumerable degrees, Lowness for difference tests, Characterizing the strongly jump-traceable sets via randomness, Algorithmically Independent Sequences, On strongly jump traceable reals, Schnorr trivial reals: a construction, On the number of infinite sequences with trivial initial segment complexity, 2007 European Summer Meeting of the Association for Symbolic Logic: Logic Colloquium '07, On very high degrees, A HIERARCHY OF COMPUTABLY ENUMERABLE DEGREES, Solovay functions and their applications in algorithmic randomness, Truth-table Schnorr randomness and truth-table reducible randomness, A random set which only computes strongly jump-traceable c.e. sets, Two more characterizations of $K$-triviality, Strong jump-traceability. I: The computably enumerable case, Schnorr trivial sets and truth-table reducibility, $\Pi_1^0 $ classes, LR degrees and Turing degrees, Lowness properties and approximations of the jump, Lowness for Demuth Randomness, Algorithmically independent sequences, Schnorr Trivial Reals: A construction, Lowness for integer-valued randomness, Lowness for effective Hausdorff dimension, Schnorr triviality and genericity, The importance of Π₁⁰ classes in effective randomness, Kolmogorov complexity of initial segments of sequences and arithmetical definability, Degrees of enumerations of countable Wehner-like families, Non-cupping, measure and computably enumerable splittings, Hyperimmune-free degrees and Schnorr triviality, Unnamed Item, RELATIVIZING CHAITIN'S HALTING PROBABILITY, Hierarchy of Computably Enumerable Degrees II, Difference randomness, Benign cost functions and lowness properties, 𝐾-trivial degrees and the jump-traceability hierarchy, Low upper bounds of ideals, Lowness for Kurtz randomness, BEING LOW ALONG A SEQUENCE AND ELSEWHERE, Chaitin's halting probability and the compression of strings using oracles, On a conjecture of Dobrinen and Simpson concerning almost everywhere domination, Enumerations of the Kolmogorov function, Tracing and domination in the Turing degrees, Randomness and lowness notions via open covers, Mass problems associated with effectively closed sets, $K$-triviality in computable metric spaces, Promptness does not imply superlow cuppability, Mass Problems and Measure-Theoretic Regularity, 2009 North American Annual Meeting of the Association for Symbolic Logic, Uniform almost everywhere domination, Randomness and Computability: Open Questions, Calibrating Randomness, Inherent enumerability of strong jump-traceability, Degrees of monotone complexity, Non-cupping and randomness, Multiple genericity: a new transfinite hierarchy of genericity notions, A computable analysis of majorizing martingales, Unified characterizations of lowness properties via Kolmogorov complexity, Cone avoidance and randomness preservation, Continuous higher randomness, Schnorr triviality and its equivalent notions, Trivial measures are not so trivial, Denjoy, Demuth and density, Limitwise monotonic spectra and their generalizations, Closure of resource-bounded randomness notions under polynomial time permutations

Cites Work