FrontPage

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

Randomness and computability: Open questions

  • Nies and Miller, Bull. Symb. Logic. 12 no 3 (2006) 390-410

K-trivialityはtraceabilityで特徴づけられるか?

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

Lowness notions for randomness notions weaker than MLR

  • 多くの研究者は「解けた」と思っているみたいだが,実は不十分
  • Schnorrの正しい定義をFranklin&Stephan2010が与えた
  • それ以外の概念に関しては,宮部が現在,進めている

KL-randomnessはMLRと同じか?

  • おそらく一番有名なlong open question
  • 生半可な気持ちで取り組むべきではない

AIM/ARCC Workshop in Effective Randomness

  • Open Problem List – updated (live) version
    • Last updated: December 17, 2007

K-trivialityはmartingaleで特徴づけられるか?by Stephan, Slaman

  • 直観的にはできないと思う.traceabilityによる特徴付けと同じぐらい難しい気がする.
  • ただし,Schnorr trivialityはできそうな気がする.
  • おそらくそのうち取り組む.

すべてのsetは1-random setにK-reducibleか?

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

Problem 6.7. What are the bases for Schnorr randomness? Computable randomness?

  • 最近宮部が解いた.
  • 次は"a basis for weak randomness"を問うべき.
  • ヒント:basisはmartingaleとの相性が良い.

無限列のmutual informationとは?by Levin

  • 昔考えたような気が・・・
  • 予想ではintegral testを使うと良いと思う.

Algorithmic Randomness: Open Questions and New Directions

  • by Downey, at CCR 2010 in Notre Dame

Other settings

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

Demuth's Programme

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

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2015-03-04 (水) 00:47:11 (871d)