計算論から見たランダムネス

摘要

計算論から見たランダムネスの研究として，無限列のランダムネスを定義したマーチンレフ・ランダムネス，そして有限列のランダムネスを定義したコルモゴロフ・ランダムネスとその関係について解説する．また，コルモゴロフ記述量の研究の応用として，最近提案された情報距離とその簡易版を紹介する．