Randomness and universal machines

DOI10.1016/J.JCO.2006.05.001MaRDI QIDQ864423zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

Kolmogorov complexityalgorithmic randomnessrecursion theoryuniversal machinestruth-table degreeshalting probability\(\Omega\)-numbers

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Applications of computability and recursion theory (03D80) Turing machines and related notions (03D10)

Recommendations

• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Randomness and halting probabilities
• Universality probability of a prefix-free machine
• Constant compression and random weights
• Chaitin numbers, Solovay machines, and Gödel incompleteness.

Cites work

• scientific article; zbMATH DE number 3987247 (Why is no real title available?)
• scientific article; zbMATH DE number 3700811 (Why is no real title available?)
• scientific article; zbMATH DE number 44959 (Why is no real title available?)
• scientific article; zbMATH DE number 193560 (Why is no real title available?)
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 1010621 (Why is no real title available?)
• scientific article; zbMATH DE number 2063218 (Why is no real title available?)
• scientific article; zbMATH DE number 1543065 (Why is no real title available?)
• A Theory of Program Size Formally Identical to Information Theory
• Algorithmic randomness and complexity.
• Calibrating Randomness
• Classical recursion theory. The theory of functions and sets of natural numbers
• Computing and Combinatorics
• Lowness properties and randomness
• Program size complexity for possibly infinite computations
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Random reals and possibly infinite computations Part I: Randomness in ∅′
• Randomness and Computability: Open Questions
• Randomness and halting probabilities
• Randomness and recursive enumerability
• Randomness, relativization and Turing degrees
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• The Degrees of Hyperimmune Sets
• The definition of random sequences
• The degrees of bi‐immune sets
• Using random sets as oracles
• 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

Cited in

(14)

• An incomplete set of shortest descriptions
• \(\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
• 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)