チャーハニスト鈴木と tri_iro さんによるランダムネス対話の記録¶

本文¶

Schnorr ランダムとか Martin-L Ö F ランダムの話というかランダムネスの話, なんべんも聴いてるのに, 未だにぜんぜんわからない…

@mszk_p コーエン強制法とランダム強制法を recursive な世界に落とし込んだ位相と測度の対比からランダムネスを理解すると, 次数絡みのランダムネス研究が何をやりたいのかは分かりやすいと思います (超遠回りルート)

@tri_iro いやなんというか, もっと低いレベルの話でわかってないんですよね… たぶん一番の原因はちゃんと勉強していないからということなのだと思いますが…

@mszk_p 定義とかの話なら, 漠然と「ランダム=ある種の確率 1 の事象全て満たす点」くらいに思っておけばお k ですよ. Martin-L Ö F とか Schnorr とか weak-2 とかはこの「ある種」の部分, つまり「確率 1 事象の部分クラス」を規定する形容詞であって, 枝葉の部分なので.

@tri_iro あぁ, そういうことだったんですか. ランダムの概念をいろんなアプローチで定義することを試みているのだと勘違いしていました…

@mszk_p ある意味では, 「ランダムの概念」をいろんなアプローチで定義しようと試みているという一面もある, というのは正しいのですが, 結局は, 数学的には, それは「確率 1 事象の部分クラス」を色んなアプローチで定義するということに落ち着くという感じです.

@mszk_p たとえば, 「チューリング機械では圧縮不可能である」確率は 1 なので, 圧縮不可能性はある種の確率 1 の事象を表しますし, 「マルチンゲールで予測不可能である」確率は 1 なので, 予測不可能性はある種の確率 1 の事象を表しますし, などなど.

@tri_iro あぁ, そういうところでコルモゴロフ複雑性とかが出てくるのですね.

@mszk_p はい, 「構成的に確率 1 」「コルモゴロフ複雑性の意味で圧縮不可能」「構成的なマルチンゲールでは予測不可能」が全て同値条件であるというのが, いわばランダムネスの基本定理なわけです. 興味あれば去年の僕の講義ノートとかもどうぞ http://researchmap.jp/mu1ce3br9-12518/#_12518

@tri_iro ありがとうございます. 去年は勉強する余裕がなかったので今年の夏休みで再チャレンジしてみます.

基本的に何を言っているのか全く把握していないが, 興味を持つ向きもいるだろうし, 何かあったときにメモを残しておくと私にとって有用になる可能性があるので, こういったことは積極的にメモっておく所存.

ラベル¶

数学, ランダムネス