[logic-ml] セミナー案内

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

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

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

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

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

------ 問い合わせ先：鹿島 亮（東京工業大学） [email protected]