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)

zbMATH Keywords

Kolmogorov complexityrandomnessalgorithmic information theorycomputably enumerable realsSolovay reducibility

Mathematics Subject Classification ID

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

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

(38)

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

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)