scientific article; zbMATH DE number 2063218

zbMath1044.03027MaRDI QIDQ4460833

Denis R. Hirschfeldt, André Nies, Rodney G. Downey, Frank Stephan

Publication date: 29 March 2004

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

random realprogram-size complexity\(H\)-trivial reals

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15) Recursively (computably) enumerable sets and degrees (03D25)

Related Items (34)

The Kolmogorov complexity of random reals ⋮ Splitting into degrees with low computational strength ⋮ Almost everywhere domination and superhighness ⋮ Randomness and universal machines ⋮ Differences of halting probabilities ⋮ Strong jump-traceability. II: \(K\)-triviality ⋮ Undecidability of the structure of the Solovay degrees of c.e. reals ⋮ Universal computably enumerable sets and initial segment prefix-free complexity ⋮ $$\textit{K}$$-trivial, $$\textit{K}$$-low and $${{\mathrm{\textit{MLR}}}}$$-low Sequences: A Tutorial ⋮ MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY ⋮ Extending and interpreting Post's programme ⋮ Lowness, Randomness, and Computable Analysis ⋮ Upper bounds on ideals in the computably enumerable Turing degrees ⋮ Computably enumerable sets below random sets ⋮ Characterizing the strongly jump-traceable sets via randomness ⋮ Schnorr trivial reals: a construction ⋮ On the number of infinite sequences with trivial initial segment complexity ⋮ Solovay functions and their applications in algorithmic randomness ⋮ Strong jump-traceability. I: The computably enumerable case ⋮ Lowness properties and approximations of the jump ⋮ Lowness for Demuth Randomness ⋮ Schnorr Trivial Reals: A construction ⋮ Random Continuous Functions ⋮ Program size complexity for possibly infinite computations ⋮ Searching for shortest and least programs ⋮ A minimal pair of 𝐾-degrees ⋮ Hierarchy of Computably Enumerable Degrees II ⋮ Tracing and domination in the Turing degrees ⋮ $K$-triviality in computable metric spaces ⋮ Inherent enumerability of strong jump-traceability ⋮ Non-cupping and randomness ⋮ Lowness properties and randomness ⋮ Multiple genericity: a new transfinite hierarchy of genericity notions ⋮ Unified characterizations of lowness properties via Kolmogorov complexity

This page was built for publication: