Randomness and universal machines
DOI10.1016/J.JCO.2006.05.001zbMATH Open1110.03030OpenAlexW2027029138MaRDI QIDQ864423FDOQ864423
Authors: Santiago Figueira, Frank Stephan, 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
Recommendations
Kolmogorov complexityalgorithmic randomnessrecursion theoryuniversal machinestruth-table degreeshalting probability\(\Omega\)-numbers
Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Turing machines and related notions (03D10)
Cites Work
- Title not available (Why is that?)
- Algorithmic randomness and complexity.
- Title not available (Why is that?)
- A Theory of Program Size Formally Identical to Information Theory
- The definition of random sequences
- Lowness properties and randomness
- Randomness, relativization and Turing degrees
- Zufälligkeit und Wahrscheinlichkeit. Eine algorithmische Begründung der Wahrscheinlichkeitstheorie. (Randomness and probability. An algorithmic foundation of probability theory)
- ∏ 0 1 Classes and Degrees of Theories
- The Degrees of Hyperimmune Sets
- Classical recursion theory. The theory of functions and sets of natural numbers
- Random reals and possibly infinite computations Part I: Randomness in ∅′
- Title not available (Why is that?)
- Randomness and Computability: Open Questions
- Calibrating Randomness
- Title not available (Why is that?)
- RELATIVIZING CHAITIN'S HALTING PROBABILITY
- The degrees of bi‐immune sets
- Title not available (Why is that?)
- Title not available (Why is that?)
- Using random sets as oracles
- Randomness and recursive enumerability
- Title not available (Why is that?)
- Randomness and halting probabilities
- Program size complexity for possibly infinite computations
- Computing and Combinatorics
- Recursively enumerable reals and Chaitin \(\Omega\) numbers
- Title not available (Why is that?)
Cited In (14)
- \(\Pi_1^0 \) classes, LR degrees and Turing degrees
- Computing halting probabilities from other halting probabilities
- Universal recursively enumerable sets of strings
- Random reals à la Chaitin with or without prefix-freeness
- A Note on the Differences of Computably Enumerable Reals
- Lowness properties and approximations of the jump
- Universality probability of a prefix-free machine
- Constant compression and random weights
- Chaitin's \(\Omega\) as a continuous function
- Searching for shortest and least programs
- Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega
- Differences of halting probabilities
- An incomplete set of shortest descriptions
- Random numbers as probabilities of machine behavior
This page was built for publication: Randomness and universal machines
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q864423)
