Schnorr triviality is equivalent to being a basis for tt-Schnorr randomness

タイトル
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に関するいくつかの新しい結果を紹介する.

ダウンロード
アブストラクト
スライド

INI web seminar

Schnorr triviality is equivalent to being a basis for tt-Schnorr randomness

タイトル
Schnorr triviality is equivalent to being a basis for tt-Schnorr randomness

種類
口頭発表

発表場所
京都大学数理解析研究所計算機科学セミナー
2012年6月7日

アブストラクト
ランダムの概念として最も有名なMartin-L\”ofランダムネスは,
テスト,複雑性,マルチンゲールなどにより特徴付けられる.
一方,ランダムではない(遠い)という概念として,
low,trivial,basisなどの概念が存在し,
これらが同値になる事が知られている.(Nies 2005, Hirschfeldt et al. 2007)
このSchnorrランダムネス版について,適当な相対化を行えば,
lowとtrivialは同値になる.(Franklin-Stephan 2010)
一方,basisによる(自然な)同値な定義は知られていなかった.
本講演では,basisによる特徴付けなど,
Schnorr trivialityに関するいくつかの新しい結果を紹介する.

補足
前半30分は日本語で,Martin-L\”ofランダムネスに対する,
low,triviality,basisなどの概念を紹介する.
後半30分は英語で,Schnorrランダムネスに関する
講演者の結果を発表する.
後半はCCR2012で発表する予定である.

ダウンロード
前半用スライド

後半用スライドなどはCCR用のページからダウンロードできます