アルゴリズム的ランダムな無限列
相対的なランダムネスはマルティンレーフランダムよりも強い最初のランダムネスの概念を与えてくれる、つまりある固定した神託Aからみたランダムネスである。どんな神託でも少なくとも同じくらい強いランダムであるし、多くの神託にとっては真に強いランダムネスである、なぜならAから見てランダムではないマルティンレーフランダムがあるだろうから。重要な神託でよく考察されるのが停止問題、 ∅ ′ {\displaystyle \emptyset '} 、n回ジャンプの神託、 ∅ ( n ) {\displaystyle \emptyset ^{(n)}} である。というのも、これらの神託が自然に起きる特定の問題に答えることができるからである。 ∅ ( n − 1 ) {\displaystyle \emptyset ^{(n-1)}} から見てランダムな列はnランダムと呼ばれる。よって1ランダムとマルティンレーフランダムは同じである。すべてのnに対してnランダムである列は算術的ランダムと呼ばれる。nランダムな列はもっと複雑な性質を考えるときによく出てくる。例えば Δ 2 0 {\displaystyle \Delta _{2}^{0}} 集合は可算個しかないので、ランダムとすべきではないと考えるかもしれない。しかしチャイティンの停止確率 Ω {\displaystyle \Omega } は Δ 2 0 {\displaystyle \Delta _{2}^{0}} であり1ランダムである。2ランダムネス以上ならばランダムな集合が Δ 2 0 {\displaystyle \Delta _{2}^{0}} とはなり得ない。