アルゴリズム的ランダムな無限列
マルティンレーフランダムの列のそれぞれの定義はチューリングマシンでの計算可能性を元にしているので、神託機械での計算可能性でも考えることができる。ある固定した神託Aに対して、列Bが、ランダムであるだけでなくAから見た計算可能性による同じ定義を満たすならば(例えばAから見た構成可能なマルチンゲールでBが成功しないならば)、BはAに対してランダムであると言う。二つの列がそれぞれランダムでも似た情報を持っているために互いにランダムではないということは起こりうる。ある列からもう一方へのチューリング還元が存在すれば、後者の列は前者の列から見てランダムではない。それはちょうど計算可能な列がランダムではないようなものである。特にチャイティンの停止確率 Ω {\displaystyle \Omega } は停止性問題の集合から見てランダムではない。
相対的なランダムネスに関して重要な結果の一つが、van Lambalgenの定理である。これは列Cが列Aと列BからAの最初のビット、Bの最初のビット、Aの2番目のビットと交互に取って作られる列だとすると、Cがアルゴリズム的ランダムであるということとAがランダムでBがAから見てランダムであるということが同値であるという定理である。似た結論としてAとBがそれぞれランダムとすると、AがBから見てランダムであるということとBがAから見てランダムであることが同値になる。
なぜなら列SがRANDに入るかどうかは、万能で構成可能なヌル被覆に含まれるSを含まない開集合が存在するかどうかと同値であり、これは Σ 2 0 {\displaystyle \Sigma _{2}^{0}} の式で定義可能であるからである。
Δ 2 0 {\displaystyle \Delta _{2}^{0}} (停止問題をオラクルとして計算可能)なランダムな列が存在する。(シュノア1971)チャイティンの Ω {\displaystyle \Omega } はそのような列の例である。
ランダムな列は帰納的集合でも、帰納的可算集合でも、帰納的可算集合の補集合でもない。これらはそれぞれ算術的階層で Δ 1 0 {\displaystyle \Delta _{1}^{0}} 、 Σ 1 0 {\displaystyle \Sigma _{1}^{0}} 、 Π 1 0 {\displaystyle \Pi _{1}^{0}} に対応するから、 Δ 2 0 {\displaystyle \Delta _{2}^{0}} がランダムな列が存在する算術的階層で一番低い層ということになる。
すべての列はあるランダムな列にチューリング還元可能である。(クセラ1985/1989、ガックス1986)よって任意の高いチューリング次数にランダムな列は存在する。
アルゴリズム的ランダムな無限列(あるごりずむてきらんだむなむげんれつ、英: Algorithmically random sequence)、あるいは単にランダムな列は、直感的にはどんなアルゴリズムにとってもランダムに見える二進無限列のことを言う。この定義は有限文字の列にも上手く適用される。ランダムな列はアルゴリズム情報理論において中心となる対象である。実行時間に特定の上限のあるアルゴリズムや神託への伺いを許したアルゴリズムなど、いくつかの異なった種類のアルゴリズムが考えられ、それに応じて異なったランダムネスの概念が存在する。もっとも良く知られているのはマルティンレーフランダムネス(1ランダムネスとも言う)であるが、もっと強いランダムネスや弱いランダムネスも存在する。単に「ランダム」と言った場合には、マルティンレーフランダムであることを意味することが多い。二進無限列は単位区間の実数と同一視できるので、ランダムな2進無限列はランダムな実数と呼ばれることもある。さらに、二進無限列は自然数の集合の特性関数とも同一視されるので、自然数の集合と見ることもある。二進のマルティンレーフランダムの無限列のクラスはRANDやMLRで表される。