Publication:4460833
From MaRDI portal
zbMath1044.03027MaRDI QIDQ4460833
Denis R. Hirschfeldt, André Nies, Rodney G. Downey, Frank Stephan
Publication date: 29 March 2004
68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)
03D15: Complexity of computation (including implicit computational complexity)
03D25: Recursively (computably) enumerable sets and degrees
Related Items
Schnorr Trivial Reals: A construction, Random Continuous Functions, Almost everywhere domination and superhighness, Inherent enumerability of strong jump-traceability, MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY, Strong jump-traceability. II: \(K\)-triviality, Universal computably enumerable sets and initial segment prefix-free complexity, Computably enumerable sets below random sets, Characterizing the strongly jump-traceable sets via randomness, Solovay functions and their applications in algorithmic randomness, Program size complexity for possibly infinite computations, Extending and interpreting Post's programme, Upper bounds on ideals in the computably enumerable Turing degrees, On the number of infinite sequences with trivial initial segment complexity, Tracing and domination in the Turing degrees, Randomness and universal machines, Undecidability of the structure of the Solovay degrees of c.e. reals, Schnorr trivial reals: a construction, The Kolmogorov complexity of random reals, Multiple genericity: a new transfinite hierarchy of genericity notions, Searching for shortest and least programs, Unified characterizations of lowness properties via Kolmogorov complexity, Differences of halting probabilities, Strong jump-traceability. I: The computably enumerable case, Lowness properties and approximations of the jump, Lowness properties and randomness, Splitting into degrees with low computational strength, $K$-triviality in computable metric spaces, $$\textit{K}$$-trivial, $$\textit{K}$$-low and $${{\mathrm{\textit{MLR}}}}$$-low Sequences: A Tutorial, Lowness, Randomness, and Computable Analysis, A minimal pair of 𝐾-degrees, Hierarchy of Computably Enumerable Degrees II, Non-cupping and randomness, Lowness for Demuth Randomness
