マルティンレーフランダムより強いランダムネス

ウィキペディア小見出し辞書

マルティンレーフランダムより強いランダムネス

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/04/21 00:17 UTC 版)

「アルゴリズム的ランダムな無限列」の記事における「マルティンレーフランダムより強いランダムネス」の解説

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