scientific article; zbMATH DE number 2063218

MaRDI QIDQ4460833zbMATH OpenFDO

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

Publication date 29 March 2004

zbMATH Keywords

\(H\)-trivial realsprogram-size complexityrandom real

Mathematics Subject Classification ID

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

Recommendations

• Trivial Reals
• Schnorr trivial reals: a construction
• Schnorr Trivial Reals: A construction
• scientific article; zbMATH DE number 5657607
• New Computational Paradigms

Cited in

(37)

• 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
• K-trivial, K-low and 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
• 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
• Trivial Reals
• Schnorr Trivial Reals: A construction
• Random Continuous Functions
• Solovay functions and their applications in algorithmic randomness
• Almost everywhere domination and superhighness
• Inherent enumerability of strong jump-traceability
• Program size complexity for possibly infinite computations
• MAXIMAL TOWERS AND ULTRAFILTER BASES IN COMPUTABILITY THEORY
• 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
• Calculus of cost functions
• Compression of enumerations and gain
• 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

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4460833)