ソロモノフ帰納は、「1, 1, 2, 3, 5, 8という数列の次には何が来そうか」「このWebカメラによる過去3年分の視覚データが与えられたとき、このロボットは次に何を見そうか」「太陽は明日昇るか」といった問いへの理想的な答えである。ソロモノフ帰納には無限の計算能力が必要である。その定義では、過去のデータから未来のデータに確率分布を与える、計算可能なあらゆるアルゴリズムを取り上げ、それぞれをその アルゴリズム的単純性によって重みづけし、実際のデータと比較して それらの重みを更新する。
たとえば、理想的なソロモノフ分布のどこかには、1と0の列を見つめて次に何が来るか予測しようとしている、 今この瞬間のあなたの完全な複製がある。ただし、このあなたの複製は複雑なので、混合分布の中で当初与えられる重みは非常に低い。計算可能な予測器のこの混合分布にあなたの複製が含まれるため、ソロモノフ帰納があなたの完全な複製と比べてどれだけよく機能するかについて定理を証明できる。すなわち、ソロモノフ帰納が犯す誤りは、あなた、あるいは計算可能なほかの任意の予測方法に対して、有界な量にとどまる。したがってソロモノフ帰納は、数列を確率的に予測するための一種の完全な、または合理的な理想である。ただし無限の計算能力を必要とするため、現実には実装できない。それでもソロモノフ帰納を考察することにより、非理想的な推論が現実世界でどう機能すべきかについて、重要な洞察を得られる。
参考文献：