アルゴリズム的ランダムな無限列
適切なランダムな列の定義を最初に与えたのはペール・マルティン=レーフであり、1966年のことであった。リヒャルト・フォン・ミーゼスなどの先行研究者もランダムネスのためにテストの概念を定式化して、ランダムネスのテストをすべて通過する列をランダムな列と定義しようとしたが、正確なランダムネスのテストの概念を与えることはできなかった。マルティンレーフによる重要な貢献は計算理論を使ってランダムネスのテストの概念を定式化したことにあった。この定義は、確率論のランダムネスの考え方とは対照的である。つまり、確率論では標本空間のどの特定の元もランダムとは言えないからである。
マルティンレーフランダムネスはその後、多くの同値な特徴付けが可能であることが示された。データ圧縮、ランダムネスのテスト、ギャンブルなどどれも元の定義には似ていないように思われるが、同時にどれもランダムな列が持つべき直感的な特徴を満たしている。ランダムな列は圧縮不可能であるだろうし、確率的なテストを通過するであろうし、賭をして儲けるのは難しいであろう。複数の定義が存在し異なる計算のモデルの異なる定義が一致することから、マルティンレーフランダムネスは数学において基本的な性質であって、マルティンレーフの特別なモデルではないと言える。 マルティンレーフランダムネスがランダムネスの直感的概念を「正しく」捕らえているというテーゼは、マルティンレーフ=チャイティンのテーゼと呼ばれている。これは「チャーチ=チューリングのテーゼ」と似たようなものである。