相対的なランダムネス

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

相対的なランダムネス

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

「アルゴリズム的ランダムな無限列」の記事における「相対的なランダムネス」の解説

マルティンレーフランダムの列のそれぞれの定義はチューリングマシンでの計算可能性を元にしているので、神託機械での計算可能性でも考えることができる。ある固定した神託Aに対して、列Bが、ランダムであるだけでなくAから見た計算可能性による同じ定義を満たすならば（例えばAから見た構成可能なマルチンゲールでBが成功しないならば）、BはAに対してランダムであると言う。二つの列がそれぞれランダムでも似た情報を持っているために互いにランダムではないということは起こりうる。ある列からもう一方へのチューリング還元が存在すれば、後者の列は前者の列から見てランダムではない。それはちょうど計算可能な列がランダムではないようなものである。特にチャイティンの停止確率は停止性問題の集合から見てランダムではない。 相対的なランダムネスに関して重要な結果の一つが、van Lambalgenの定理である。これは列Cが列Aと列BからAの最初のビット、Bの最初のビット、Aの２番目のビットと交互に取って作られる列だとすると、Cがアルゴリズム的ランダムであるということとAがランダムでBがAから見てランダムであるということが同値であるという定理である。似た結論としてAとBがそれぞれランダムとすると、AがBから見てランダムであるということとBがAから見てランダムであることが同値になる。