マルティンレーフランダムの性質の例
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2016/04/21 00:17 UTC 版)
「アルゴリズム的ランダムな無限列」の記事における「マルティンレーフランダムの性質の例」の解説
チャイティンの停止確率はランダムな列の族である。 RANDc（RANDの補集合）はすべての無限列の集合の中の測度0の部分集合である。これは構成可能なヌル被覆は測度0の集合しか覆えず、構成可能なヌル被覆は可算個しか存在せず、測度0の集合の可算和は測度0であることから導かれる。よってRANDは測度1の集合である。 すべてのランダムな列は正規数である。 RANDcを決める構成可能なヌル被覆が存在する。すなわちすべての構成可能なランダムネスのテスト（すなわち構成可能なヌル被覆）は、ある意味この万能なランダムネスのテストに含まれる、なぜならこの一つのランダムネスのテストを通過するどんな列はどんなランダムネスのテストをも通過するであろうから。（マルティンレーフ1966年） 万能な構成可能なマルチンゲールdが存在する。すなわちどんな構成可能なマルチンゲールdに対しても、dがある列で成功すればdもその列で成功するという意味で万能なマルチンゲールである。よってdはRANDcのどの列でも成功する（が、dは構成可能なので、RANDのどの列でも成功しない）。（シュノア1971） RANDはカントール空間の集合である。ここでとは算術的階層の２番目である。なぜなら列SがRANDに入るかどうかは、万能で構成可能なヌル被覆に含まれるSを含まない開集合が存在するかどうかと同値であり、これはの式で定義可能であるからである。 （停止問題をオラクルとして計算可能）なランダムな列が存在する。（シュノア1971）チャイティンのはそのような列の例である。 ランダムな列は帰納的集合でも、帰納的可算集合でも、帰納的可算集合の補集合でもない。これらはそれぞれ算術的階層で、、に対応するから、がランダムな列が存在する算術的階層で一番低い層ということになる。 すべての列はあるランダムな列にチューリング還元可能である。（クセラ1985/1989、ガックス1986）よって任意の高いチューリング次数にランダムな列は存在する。
※この「マルティンレーフランダムの性質の例」の解説は、「アルゴリズム的ランダムな無限列」の解説の一部です。
「マルティンレーフランダムの性質の例」を含む「アルゴリズム的ランダムな無限列」の記事については、「アルゴリズム的ランダムな無限列」の概要を参照ください。
- マルティンレーフランダムの性質の例のページへのリンク
