アルゴリズム的確率
Rathmanner, S and Hutter, M., "A Philosophical Treatise of Universal Induction" in Entropy 2011, 13, 1076-1136: A very clear philosophical and mathematical analysis of Solomonoff's Theory of Inductive Inference
さらに、ベイズの定理を用いて最もありそうな未来の予測に使える。
ソロモノフが不変定理の発見と共にアルゴリズム的確率の概念を発明したのは、1960年頃であり、それに関しての論文も出版している。これらの考えをはっきりと明らかにしたのは、1964年の2本の論文であろう 。
アルゴリズム的確率はソロモノフの帰納推論の理論(観察に基づく予測の理論)における鍵であり、機械学習への応用を目指して開発された。文字列が与えられたら、次に来る文字は何であろうか? ソロモノフの理論はこの問題に対し、ある意味で最善の解答を与えている。ただし、計算可能ではない。ただ、例えばポッパーの帰納推論の理論とは違い、ソロモノフの理論は数学的には厳格である。
アルゴリズム的確率はコルモゴロフ複雑性の概念と深い関係がある。コルモゴロフはこの概念を情報理論やランダムネスの問題から着想を得て導入したが、ソロモノフはそれより早く帰納推論という別の理由で導入していた。実際、普遍的な事前確率はコルモゴロフ複雑性を用いて書くことができる。
ソロモノフのc.e.測度は普遍性を持つ代わりに、計算時間が有限ではない。この問題に対して、Leonid Levinによるサーチアルゴリズムの変種を考え、計算時間を制限して、短い時間で出力するプログラムに高い確率を与える方法がある。