ペール・マルティン＝レーフ
マルティン=レーフは、ストックホルム大学におけるUlf Grenanderによって率いられる研究プログラムの対象である代数的構造、特に半群の中の確率論に関するライセンス論文を書いた。
マルティン=レーフ・ランダム性に複数の定義が存在することと、異なる計算モデルの下でのこれら定義の安定性は、マルティン=レーフ・ランダムネスが数学の基本的な性質であり、マルティン=レーフの特定のモデルによってもたらされた偶然ではないことの証拠となっている。マルティン=レーフ・ランダムネスの定義が「正確に」ランダムネスの直観的概念を捉えているという提唱は、「マルティン=レーフ・チャイティン提唱」と呼ばれている。これはチャーチ=チューリングのテーゼに幾分か類似している提言である。
マルティン=レーフの研究の後、アルゴリズム情報理論は、ランダム文字列を、その文字列よりも短いプログラムからは生成できないものとして定義した(チャイティン=コルモゴロフ複雑性)。すなわち、ある文字列のコルモゴロフ複雑性はその文字列の長さよりは小さいということである。これは統計学における用語の用法とは異なる意味である。統計学的ランダムネスは文字列を生成するプロセスを指す(たとえば、コインを投げて各ビットを生成するとランダム文字列が生成される)が、アルゴリズム的ランダムネスは文字列自体を指す。アルゴリズム情報理論は、用いられている計算モデルに対して比較的不変な方法で、ランダムでない文字列からランダムな文字列を分離する。
アルゴリズム的ランダムな無限列は文字の「無限」列であり、その全ての接頭部(おそらく有限の数を除いて)は、アルゴリズム的ランダムに極めて近い文字列である(その長さはコルモゴロフ複雑性の定数以下となる)。