Randomness, computability, and density

DOI10.1137/S0097539700376937MaRDI QIDQ2784497zbMATH OpenFDO

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

Publication date 23 April 2002

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/S0097539700376937

zbMATH Keywords

algorithmic information theorycomputably enumerable realsKolmogorov complexityrandomnessSolovay reducibility

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Applications of computability and recursion theory (03D80) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• scientific article; zbMATH DE number 1688364
• scientific article; zbMATH DE number 1408348
• scientific article; zbMATH DE number 1834658
• Randomness and reducibility
• Computing and Combinatorics

Cited in

(39)

• On randomness, determinism and computability
• Randomness and reducibility
• On Kurtz randomness
• Randomness below complete theories of arithmetic
• Differences of halting probabilities
• The ibT degrees of computably enumerable sets are not dense
• scientific article; zbMATH DE number 1688364 (Why is no real title available?)
• Randomness and recursive enumerability
• Demuth's path to randomness
• Reducibilities relating to Schnorr randomness
• Random semicomputable reals revisited
• A Note on the Differences of Computably Enumerable Reals
• On Work of Barmpalias and Lewis-Pye: A Derivation on the D.C.E. Reals
• Lowness, Randomness, and Computable Analysis
• Some Questions in Computable Mathematics
• Mass Problems and Randomness
• Calibrating Randomness
• Degrees of monotone complexity
• Randomness and halting probabilities
• Non-cupping, measure and computably enumerable splittings
• scientific article; zbMATH DE number 4091486 (Why is no real title available?)
• Universal computably enumerable sets and initial segment prefix-free complexity
• scientific article; zbMATH DE number 2080190 (Why is no real title available?)
• Randomness and Solovay degrees
• Computing and Combinatorics
• There are 2^{ℵ₀} many 𝐻-degrees in the random reals
• Trivial Reals
• SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS
• Computability of Real Numbers
• Π11‐Martin‐Löf randomness and Π11‐Solovay completeness
• Random numbers as probabilities of machine behavior
• Entropy, Randomization, Derandomization, and Discrepancy
• Computing and Combinatorics
• Random reals and possibly infinite computations Part I: Randomness in ∅′
• Reordered computable numbers
• Regainingly approximable numbers and sets
• Speedability of computably approximable reals and their approximations
• Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
• Randomness and the linear degrees of computability

This page was built for publication: Randomness, computability, and density

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