アルゴリズム的確率
次のような問題を扱う。ある理解したいと思う現象のデータが与えられたとする。そのデータがどのようにして起こったのかについてのすべての可能な仮定の中で、どのようにして最もありそうな仮定を選んだら良いだろうか? どのように異なる仮定を評価したら良いだろうか? どのようにして未来を予測したら良いだろうか?
アルゴリズム的確率はオッカムの剃刀、エピクロスの複数説明の原理、現代の計算理論による符号手法など、いくつかのアイディアを組み合わせて、事前確率は予測に関するベイズの定理を使用した式から得られる。オッカムの剃刀とは、「観察された現象に合致する理論の中で、最も単純なものを選ぶべき」というものである。一方、エピクロスは複数説明の原理を唱えている。つまり、「複数の理論が観察に合致するなら、すべての理論を保持せよ」。そこで、特別な数学的道具である普遍機械を使って、すべての興味ある理論に量を割り当てる。
アルゴリズム的確率はオッカムの剃刀と複数説明の原理を組み合わせ、与えられた観察を説明するそれぞれの仮定(アルゴリズムやプログラム)に次のようにして確率値を割り当てる。単純な仮定(短いプログラム)には高い確率を、複雑な仮定(長いプログラム)には小さな確率を割り当てる。すると、これらの確率は観察に対して事前確率になっており、ソロモノフはそれが定数倍を除いて機械に依存しないことを示した(不変定理と呼ばれている)。