On Martin-Löf (non-)convergence of Solomonoff's universal mixture

Tor Lattimore; Marcus Hutter

doi:10.1016/j.tcs.2014.12.004

On Martin-Löf (non-)convergence of Solomonoff's universal mixture

Tor Lattimore^*, Marcus Hutter

^*Corresponding author for this work

Research output: Contribution to journal › Article › peer-review

2 Citations (Scopus)

Abstract

We study the convergence of Solomonoff's universal mixture on individual Martin-Löf random sequences. A new result is presented extending the work of Hutter and Muchnik [3] by showing that there does not exist a universal mixture that converges on all Martin-Löf random sequences. We show that this is not an artifact of the fact that the universal mixture is not a proper measure and that the normalised universal mixture also fails to converge on all Martin-Löf random sequences.

Original language	English
Pages (from-to)	2-15
Number of pages	14
Journal	Theoretical Computer Science
Volume	588
DOIs	https://doi.org/10.1016/j.tcs.2014.12.004
Publication status	Published - 11 Jul 2015

Access to Document

10.1016/j.tcs.2014.12.004

Cite this

@article{c2e0bae9306047b7b9e27291b9028b8a,

title = "On Martin-L{\"o}f (non-)convergence of Solomonoff's universal mixture",

abstract = "We study the convergence of Solomonoff's universal mixture on individual Martin-L{\"o}f random sequences. A new result is presented extending the work of Hutter and Muchnik [3] by showing that there does not exist a universal mixture that converges on all Martin-L{\"o}f random sequences. We show that this is not an artifact of the fact that the universal mixture is not a proper measure and that the normalised universal mixture also fails to converge on all Martin-L{\"o}f random sequences.",

keywords = "Kolmogorov complexity, Solomonoff induction, Theory of computation",

author = "Tor Lattimore and Marcus Hutter",

note = "Publisher Copyright: {\textcopyright} 2015 Published by Elsevier B.V.",

year = "2015",

month = jul,

day = "11",

doi = "10.1016/j.tcs.2014.12.004",

language = "English",

volume = "588",

pages = "2--15",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - On Martin-Löf (non-)convergence of Solomonoff's universal mixture

AU - Lattimore, Tor

AU - Hutter, Marcus

PY - 2015/7/11

Y1 - 2015/7/11

N2 - We study the convergence of Solomonoff's universal mixture on individual Martin-Löf random sequences. A new result is presented extending the work of Hutter and Muchnik [3] by showing that there does not exist a universal mixture that converges on all Martin-Löf random sequences. We show that this is not an artifact of the fact that the universal mixture is not a proper measure and that the normalised universal mixture also fails to converge on all Martin-Löf random sequences.

AB - We study the convergence of Solomonoff's universal mixture on individual Martin-Löf random sequences. A new result is presented extending the work of Hutter and Muchnik [3] by showing that there does not exist a universal mixture that converges on all Martin-Löf random sequences. We show that this is not an artifact of the fact that the universal mixture is not a proper measure and that the normalised universal mixture also fails to converge on all Martin-Löf random sequences.

KW - Kolmogorov complexity

KW - Solomonoff induction

KW - Theory of computation

UR - http://www.scopus.com/inward/record.url?scp=84945288532&partnerID=8YFLogxK

U2 - 10.1016/j.tcs.2014.12.004

DO - 10.1016/j.tcs.2014.12.004

M3 - Article

SN - 0304-3975

VL - 588

SP - 2

EP - 15

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

On Martin-Löf (non-)convergence of Solomonoff's universal mixture

Abstract

Access to Document

Other files and links

Fingerprint

Cite this