タイトル
Schnorr triviality is equivalent to being a basis for tt-Schnorr randomness
種類
口頭発表
発表場所
Seventh International Conference on Computability, Complexity and Randomness (CCR 2012)
2-6 July 2012, Cambridge, Great Britain
Isaac Newton Institute
アブストラクト
ランダムの概念として最も有名なMartin-L\”ofランダムネスは，
テスト，複雑性，マルチンゲールなどにより特徴付けられる．
一方，ランダムではない（遠い）という概念として，
low,trivial,basisなどの概念が存在し，
これらが同値になる事が知られている．(Nies 2005, Hirschfeldt et al. 2007)
このSchnorrランダムネス版について，適当な相対化を行えば，
lowとtrivialは同値になる．(Franklin-Stephan 2010)
一方，basisによる(自然な)同値な定義は知られていなかった．
本講演では，basisによる特徴付けなど，
Schnorr trivialityに関するいくつかの新しい結果を紹介する．