A generalized characterization of algorithmic probability

DOI10.1007/S00224-017-9774-9MaRDI QIDQ1694008zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Tom F. Sterkenburg

Publication date 1 February 2018

Published in Theory of Computing Systems (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1508.05733, https://ir.cwi.nl/pub/25779

zbMATH Keywords

algorithmic probabilityOccam's razorprinciple of indifferencea priori semimeasuremonotone Turing machinessemicomputable semimeasures

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Other connections with logic and set theory (28E15)

Abstract: An a priori semimeasure (also known as "algorithmic probability" or "the Solomonoff prior" in the context of inductive inference) is defined as the transformation, by a given universal monotone Turing machine, of the uniform measure on the infinite strings. It is shown in this paper that the class of a priori semimeasures can equivalently be defined as the class of transformations, by all compatible universal monotone Turing machines, of any continuous computable measure in place of the uniform measure. Some consideration is given to possible implications for the prevalent association of algorithmic probability with certain foundational statistical principles.

Recommendations

• The semimeasure property of algorithmic probability -- ``feature or ``bug?
• Algorithmic Probability: Theory and Applications
• On the existence and convergence of computable universal priors
• On generalized computable universal priors and their convergence
• Stationary algorithmic probability

Cites work

• scientific article; zbMATH DE number 3489016 (Why is no real title available?)
• scientific article; zbMATH DE number 3492569 (Why is no real title available?)
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• (Non-)Equivalence of Universal Priors
• A Theory of Program Size Formally Identical to Information Theory
• A formal theory of inductive inference. Part II
• A philosophical treatise of universal induction
• Algorithmic randomness and complexity.
• An introduction to Kolmogorov complexity and its applications
• Computability and randomness
• Elements of Information Theory
• Gödel numberings of partial recursive functions
• Increasing the gap between descriptional complexity and algorithmic probability
• Mechanizing induction
• On the computational power of random strings
• On universal prediction and Bayesian confirmation
• Philosophical issues in Kolmogorov complexity
• Process complexity and effective random tests
• THE COMPLEXITY OF FINITE OBJECTS AND THE DEVELOPMENT OF THE CONCEPTS OF INFORMATION AND RANDOMNESS BY MEANS OF THE THEORY OF ALGORITHMS
• The discovery of algorithmic probability
• Universal artificial intelligence. Sequential decisions based on algorithmic probability.

Cited in

(13)

• Algorithmic Probability: Theory and Applications
• scientific article; zbMATH DE number 4079400 (Why is no real title available?)
• scientific article; zbMATH DE number 6019532 (Why is no real title available?)
• Relativized questions involving probabilistic algorithms
• Algorithms and Applications for the Same-Decision Probability
• On the relation between descriptional complexity and algorithmic probability
• A relation between correctness and randomness in the computation of probabilistic algorithms
• The semimeasure property of algorithmic probability -- ``feature or ``bug?
• Stationary algorithmic probability
• A Probabilistic Analysis of Christofides’ Algorithm
• scientific article; zbMATH DE number 5201472 (Why is no real title available?)
• scientific article; zbMATH DE number 1507353 (Why is no real title available?)
• Ergodic-Type Characterizations of Algorithmic Randomness

This page was built for publication: A generalized characterization of algorithmic probability

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