Universality probability of a prefix-free machine

DOI10.1098/RSTA.2011.0319MaRDI QIDQ2941600zbMATH OpenOpenAlexWikidataFDO

Authors George Barmpalias, David L. Dowe

Publication date 21 August 2015

Published in Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1098/rsta.2011.0319

zbMATH Keywords

algorithmic randomnessKolmogorov complexityprefix-free complexityuniversality probability

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Recommendations

• Random numbers as probabilities of machine behavior
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• Random reals à la Chaitin with or without prefix-freeness
• Universal Recursively Enumerable Sets of Strings
• Randomness and halting probabilities

Cites work

• A formal theory of inductive inference. Part I
• A Theory of Program Size Formally Identical to Information Theory
• scientific article; zbMATH DE number 3427210 (Why is no real title available?)
• scientific article; zbMATH DE number 1886067 (Why is no real title available?)
• Logical basis for information theory and probability theory
• Minimum Message Length and Kolmogorov Complexity
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Random reals à la Chaitin with or without prefix-freeness
• Randomness and halting probabilities
• Randomness and recursive enumerability
• Randomness and universal machines
• Recursively enumerable reals and Chaitin \(\Omega\) numbers
• RELATIVIZING CHAITIN'S HALTING PROBABILITY
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The definition of random sequences
• Von Mises' definition of random sequences reconsidered

Cited in

(12)

• Stationary algorithmic probability
• Random reals à la Chaitin with or without prefix-freeness
• The foundations of computation, physics and mentality: the Turing legacy
• On universal computably enumerable prefix codes
• Simplicity via provability for universal prefix-free Turing machines
• Random numbers as probabilities of machine behavior
• Universal recursively enumerable sets of strings
• Simplicity via provability for universal prefix-free Turing machines
• Representation of left-computable \(\varepsilon \)-random reals
• Computing halting probabilities from other halting probabilities
• Randomness and universal machines
• The probability of ``undefined (non-converging) output in generating the universal probability distribution

This page was built for publication: Universality probability of a prefix-free machine

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941600)