[logic-ml] セミナー案内

[KASHIMA Ryo]

数理論理学セミナーのご案内

日時：1月25日(金)15:00から
場所：東京工業大学 大岡山西８号館W棟11階 W1101セミナー室

話者：宮部賢志（京大数解研）
題目：一様Kurtzランダムネスに対する独立性定理
概要：
アルゴリズム的ランダムネスでは，ある2進無限列がランダムかどうかについて，様々な定式化を与える．
Martin-L\"ofランダムネスはそのうちの一つで，次のような結果が知られている．
「ある列がMLランダムであることと，その列の奇数番目の文字の列AがMLランダムかつ，偶数番目の文字の列が，Aから見てMLランダムであること，が同値となる」
この定理はvan Lambalgen's Theoremと呼ばれているが，日本語では独立性定理と呼んでいる．

ランダムネスの理論では様々なランダムの概念を考察する．
他のランダムの概念に付いては，独立性定理が成り立たないことが知られていたが，筆者は一様相対化の場合は，Schnorrや計算可能ランダムについて，独立性定理が成り立つことを主張した．
その後，Demuthランダムネスについても同様の結果が知られている．

本発表では，Kurtzランダムネスの一様相対化の場合の独立性定理について報告する．

------
問い合わせ先：鹿島 亮（東京工業大学）
kashima at is.titech.ac.jp