| Abstract | アルゴリズム的ランダムネスとはランダムな二進無限列を計算の側面から
定義し、その性質を調べる分野である。ランダムな列の定義には、
典型性、記述不可能性、予測不可能性の３つのアプローチがあり、
適切な定式化のもとで同値になる。最初に定義された
Martin-L\"ofランダムネスでは、多くのランダムな列として自然な性質が
示された。また許す計算可能性を変化させることで、様々なランダムネスが
定義され、それらの計算可能性との関連が深く調べられている。
本講演では前半ではこのようなアルゴリズム的ランダムネスの基本概念を紹介する。
後半ではSchnorrランダムネスに関して得られた結果を紹介する。
Schnorrランダムネスは自然な概念と考えられていたが、
独立性定理の不成立やLownessの不自然な結果が最近得られていた。
これは相対化が不適切なことが原因であるとして、
真理値表Schnorrランダムを提案し、独立性定理が成立することや、
自然なLownessの概念が得られることを示した。
これによりランダムネスは計算可能性による制限よりも、
チューリングマシンの制限により定まるとの理解が自然であることが分かる。
|