筑波大学数学談話会

ランダム性と計算可能性

アルゴリズム的ランダムネスの理論について概説を行う．
ランダムネスの理論は確率概念の数学的基礎づけを発端とし，
情報理論や予測理論，最近ではエルゴード理論などとの関係が調べられてきた．
前半では，ランダムな2進無限列を定義し，
大数の法則などの基本的な性質を見る．
ランダム性が数学的に定式化できることで，
様々な概念が見通しよく理解できるようになることを説明する．
後半では，一見対極にあって相容れないように思われる
ランダム性と計算可能性という2つの概念が深い関係を持つことを見る．
具体的には，ChaitinのΩ数のランダム性や停止問題を計算することなどを解説する．