Randomness and universal machines

DOI10.1016/j.jco.2006.05.001zbMath1110.03030OpenAlexW2027029138MaRDI QIDQ864423

Frank Stephan, Santiago Figueira, Guohua Wu

Publication date: 8 February 2007

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jco.2006.05.001

zbMATH Keywords

Kolmogorov complexityhalting probabilityrecursion theoryalgorithmic randomnessuniversal machinestruth-table degrees\(\Omega\)-numbers

Mathematics Subject Classification ID

Related Items (11)

Differences of halting probabilities ⋮ Universality probability of a prefix-free machine ⋮ A Note on the Differences of Computably Enumerable Reals ⋮ An incomplete set of shortest descriptions ⋮ Random reals à la Chaitin with or without prefix-freeness ⋮ \(\Pi_1^0 \) classes, LR degrees and Turing degrees ⋮ Lowness properties and approximations of the jump ⋮ Universal recursively enumerable sets of strings ⋮ Computing halting probabilities from other halting probabilities ⋮ Searching for shortest and least programs ⋮ Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Program size complexity for possibly infinite computations
• Classical recursion theory. The theory of functions and sets of natural numbers
• Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
• Lowness properties and randomness
• Randomness and Recursive Enumerability
• Algorithmic Randomness and Complexity
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Randomness and Computability: Open Questions
• Calibrating Randomness
• Randomness and halting probabilities
• A Theory of Program Size Formally Identical to Information Theory
• Using random sets as oracles
• The degrees of bi‐immune sets
• The Degrees of Hyperimmune Sets
• The definition of random sequences
• ∏ 0 1 Classes and Degrees of Theories
• Computing and Combinatorics
• Randomness, relativization and Turing degrees
• Random reals and possibly infinite computations Part I: Randomness in ∅′
• Recursively enumerable reals and Chaitin \(\Omega\) numbers

This page was built for publication: Randomness and universal machines