[[FrontPage]]

このページではランダムネスの理論でのOpen Questionsを紹介する.
取捨選択は全く個人的な判断による.

*Randomness and computability: Open questions[#kdf27eba]
-Nies and Miller, Bull. Symb. Logic. 12 no 3 (2006) 390-410

**K-trivialityはtraceabilityで特徴づけられるか? [#c81ac068]
-K-trivialityはstrong jump traceabilityとjump traceabilityの間にある
-traceのboundにより特徴づけようと盛んにされているが,果たして研究の方向として正しいかどうかは微妙
-boundにKが表れたりするのかも?

**Lowness notions for randomness notions weaker than MLR [#n6b7ce7a]
-多くの研究者は「解けた」と思っているみたいだが,実は不十分
-Schnorrの正しい定義をFranklin&Stephan2010が与えた
-それ以外の概念に関しては,宮部が現在,進めている

**KL-randomnessはMLRと同じか? [#u09c94a3]
-おそらく一番有名なlong open question
-生半可な気持ちで取り組むべきではない


*AIM/ARCC Workshop in Effective Randomness [#g2750660]
-Open Problem List – updated (live) version
--Last updated: December 17, 2007

**K-trivialityはmartingaleで特徴づけられるか?by Stephan, Slaman [#u1b30e6e]
-直観的にはできないと思う.traceabilityによる特徴付けと同じぐらい難しい気がする.
-ただし,Schnorr trivialityはできそうな気がする.
-おそらくそのうち取り組む.

**すべてのsetは1-random setにK-reducibleか? [#h93b2ef4]
-最初見た時は「こんな(簡単そうな)問題も分かっていないのか!」と思った.
-けれどすこし考えると,不自然な問題のような気がしてきた.
-そう言いながらwikiに取り上げるのは適切ではない.

**Problem 6.7. What are the bases for Schnorr randomness? Computable randomness? [#x038640f]
-最近宮部が解いた.
-次は"a basis for weak randomness"を問うべき.
-ヒント:basisはmartingaleとの相性が良い.

**無限列のmutual informationとは?by Levin [#l36d0259]
-昔考えたような気が・・・
-予想ではintegral testを使うと良いと思う.

*Algorithmic Randomness: Open Questions and New Directions [#ece8ef22]
-by Downey, at CCR 2010 in Notre Dame

**Other settings [#j5b1ade5]
-Cantor spaceからcomputable metric spaceへの拡張はすでになされ,それの応用に焦点が当たっている
-さらなる拡張は現在行っている最中だが,最近ストップしている.

**Demuth's Programme [#ef7bda3c]
-微分可能性の問題に関してはずいぶん研究が進んだ.
-たぶんもう少しやることはあると思うけれど,いまいち重要性を見いだせない.
-面白い結果が出るのを待つ
-Ergodic theoryに関してはやることが多い.
-直近の重要な問題としては,Schnorr randomnessのBirkhoffのErgodic Theoremによる特徴付けが,L^1-computabilityで説明が出来ないかというもの
-最近,Logic Blog 2012にpartial answerが上がった


トップ   編集 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS