Randomness, Computability, and Density
From MaRDI portal
Publication:2784497
DOI10.1137/S0097539700376937zbMath1052.68060MaRDI QIDQ2784497
André Nies, Denis R. Hirschfeldt, Rodney G. Downey
Publication date: 23 April 2002
Published in: SIAM Journal on Computing (Search for Journal in Brave)
algorithmic information theoryKolmogorov complexityrandomnesscomputably enumerable realsSolovay reducibility
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Other degrees and reducibilities in computability and recursion theory (03D30)
Related Items
Randomness and reducibility, Reducibilities relating to Schnorr randomness, On Kurtz randomness, There are 2^{ℵ₀} many 𝐻-degrees in the random reals, Differences of halting probabilities, Universal computably enumerable sets and initial segment prefix-free complexity, Π11‐Martin‐Löf randomness and Π11‐Solovay completeness, 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, Randomness and Solovay degrees, Random reals and possibly infinite computations Part I: Randomness in ∅′, Random numbers as probabilities of machine behavior, Trivial Reals, The ibT degrees of computably enumerable sets are not dense, DEMUTH’S PATH TO RANDOMNESS, Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega, Calibrating Randomness, Degrees of monotone complexity, Randomness and halting probabilities, SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS, Computability of Real Numbers
