Randomness and Recursive Enumerability
From MaRDI portal
Publication:2784448
DOI10.1137/S0097539799357441zbMath0992.68079OpenAlexW2038458144MaRDI QIDQ2784448
Theodore A. Slaman, Antonín Kučera
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/s0097539799357441
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
Randomness and reducibility ⋮ Random Semicomputable Reals Revisited ⋮ Phase Transition between Unidirectionality and Bidirectionality ⋮ On Kurtz randomness ⋮ What Percentage of Programs Halt? ⋮ The Kolmogorov complexity of random reals ⋮ Randomness, Computation and Mathematics ⋮ Time-Bounded Kolmogorov Complexity and Solovay Functions ⋮ Partial Randomness and Dimension of Recursively Enumerable Reals ⋮ There are 2^{ℵ₀} many 𝐻-degrees in the random reals ⋮ Schnorr randomness ⋮ Natural halting probabilities, partial randomness, and zeta functions ⋮ Randomness and universal machines ⋮ Differences of halting probabilities ⋮ Universality probability of a prefix-free machine ⋮ Undecidability of the structure of the Solovay degrees of c.e. reals ⋮ Simplicity via provability for universal prefix-free Turing machines ⋮ Π11‐Martin‐Löf randomness and Π11‐Solovay completeness ⋮ EXACT APPROXIMATIONS OF OMEGA NUMBERS ⋮ Time-bounded Kolmogorov complexity and Solovay functions ⋮ A Note on the Differences of Computably Enumerable Reals ⋮ On Work of Barmpalias and Lewis-Pye: A Derivation on the D.C.E. Reals ⋮ Universal Recursively Enumerable Sets of Strings ⋮ On the hierarchy and extension of monotonically computable real numbers. ⋮ Algorithmic information theory and its statistical mechanical interpretation ⋮ Solovay functions and their applications in algorithmic randomness ⋮ Randomness and Solovay degrees ⋮ Kolmogorov Complexity as a Language ⋮ Randomness, relativization and Turing degrees ⋮ Random numbers as probabilities of machine behavior ⋮ Schnorr Randomness ⋮ Trivial Reals ⋮ Things that can be made into themselves ⋮ Kobayashi compressibility ⋮ Chaitin Ω Numbers and Halting Problems ⋮ Universal recursively enumerable sets of strings ⋮ A Chaitin \(\Omega\) number based on compressible strings ⋮ Recursively enumerable reals and Chaitin \(\Omega\) numbers ⋮ Working with strong reducibilities above totally $\omega $-c.e. and array computable degrees ⋮ Representation of left-computable \(\varepsilon \)-random reals ⋮ Computing halting probabilities from other halting probabilities ⋮ Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega ⋮ RELATIVIZING CHAITIN'S HALTING PROBABILITY ⋮ Information: The Algorithmic Paradigm ⋮ Computing a Glimpse of Randomness ⋮ Calibrating Randomness ⋮ Randomness and halting probabilities ⋮ SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS ⋮ Computability of Real Numbers ⋮ Chaitin \(\Omega\) numbers, Solovay machines, and Gödel incompleteness. ⋮ The closure properties on real numbers under limits and computable operators.
