The Semimeasure Property of Algorithmic Probability -- “Feature‘ or “Bug‘?

In David L. Dowe (ed.), Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence: Papers From the Ray Solomonoff 85th Memorial Conference, Melbourne, Vic, Australia, November 30 -- December 2, 2011. Springer. pp. 79--90 (2013)
  Copy   BIBTEX


An unknown process is generating a sequence of symbols, drawn from an alphabet, A. Given an initial segment of the sequence, how can one predict the next symbol? Ray Solomonoff’s theory of inductive reasoning rests on the idea that a useful estimate of a sequence’s true probability of being outputted by the unknown process is provided by its algorithmic probability (its probability of being outputted by a species of probabilistic Turing machine). However algorithmic probability is a “semimeasure”: i.e., the sum, over all x∈A, of the conditional algorithmic probabilities of the next symbol being x, may be less than 1. Prevailing wisdom has it that algorithmic probability must be normalized, to eradicate this semimeasure property, before it can yield acceptable probability estimates. This paper argues, to the contrary, that the semimeasure property contributes substantially to the power and scope of an algorithmic-probability-based theory of induction, and that normalization is unnecessary.



    Upload a copy of this work     Papers currently archived: 93,098

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

A generalized characterization of algorithmic probability.Tom F. Sterkenburg - 2017 - Theory of Computing Systems 61 (4):1337-1352.
Universal Algorithmic Intelligence: A Mathematical Top-Down Approach.Marcus Hutter - 2007 - In Ben Goertzel & Cassio Pennachin (eds.), Artificial General Intelligence. Springer Verlag. pp. 227-290.
Probability and Randomness.Antony Eagle - 2016 - In Alan Hájek & Christopher Hitchcock (eds.), The Oxford Handbook of Probability and Philosophy. Oxford: Oxford University Press. pp. 440-459.
Solomonoff Prediction and Occam’s Razor.Tom F. Sterkenburg - 2016 - Philosophy of Science 83 (4):459-479.
A Dilemma for Solomonoff Prediction.Sven Neth - 2023 - Philosophy of Science 90 (2):288-306.


Added to PP

71 (#237,004)

6 months
11 (#272,000)

Historical graph of downloads
How can I increase my downloads?

Author's Profile

Douglas Ian Campbell
University of Canterbury

Citations of this work

No citations found.

Add more citations

References found in this work

No references found.

Add more references