Recursively enumerable reals and Chaitin \(\Omega\) numbers

DOI10.1016/S0304-3975(99)00159-0zbMath0974.68072OpenAlexW2118139375WikidataQ57001730 ScholiaQ57001730MaRDI QIDQ5941066

Yongge Wang, Cristian S. Calude, Peter H. Hertling, Bakhadyr Khoussainov

Publication date: 20 August 2001

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(99)00159-0

zbMATH Keywords

halting probabilityuniversal self-delimiting Turing machine

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Related Items (max. 100)

A Computability Challenge: Asymptotic Bounds for Error-Correcting Codes ⋮ Phase Transition between Unidirectionality and Bidirectionality ⋮ Partial Randomness and Dimension of Recursively Enumerable Reals ⋮ 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 ⋮ A computation model with automatic functions and relations as primitive operations ⋮ EXACT APPROXIMATIONS OF OMEGA NUMBERS ⋮ 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 ⋮ Kolmogorov Complexity as a Language ⋮ Random numbers as probabilities of machine behavior ⋮ Trivial Reals ⋮ Things that can be made into themselves ⋮ Kobayashi compressibility ⋮ Chaitin Ω Numbers and Halting Problems ⋮ Universal recursively enumerable sets of strings ⋮ Classification of the Computable Approximations by Divergence Boundings ⋮ Representation of left-computable \(\varepsilon \)-random reals ⋮ On the hierarchies of Δ₂⁰-real numbers ⋮ Computing halting probabilities from other halting probabilities ⋮ Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega ⋮ Information: The Algorithmic Paradigm ⋮ Classification of computably approximable real numbers ⋮ Algorithmic networks: central time to trigger expected emergent open-endedness ⋮ Calibrating Randomness ⋮ Randomness and halting probabilities ⋮ SOME QUESTIONS OF UNIFORMITY IN ALGORITHMIC RANDOMNESS ⋮ Computability of Real Numbers

Cites Work

• Computational depth and reducibility
• Process complexity and effective random tests
• Randomness and Recursive Enumerability
• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic Information Theory
• On the Length of Programs for Computing Finite Binary Sequences
• The definition of random sequences
• A formal theory of inductive inference. Part I
• Computability and Recursion
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Recursively enumerable reals and Chaitin \(\Omega\) numbers