京都大学大学院理学研究科数学・数理解析専攻数理解析系 数理解析特別講義１計算機科学（集中講義）
ランダムネスの理論では2進無限列などのある対象がランダムであるとはどういうことかを明らかにする．確率概念の数学的基礎付けとしてはKolmogorovの公理的確率論がよく知られているが，各元がランダムかどうかには言及しない．そこに計算可能性の概念を導入することにより，各元がランダムかどうかを議論できるようになる．
本講義では，2進無限列のランダム性と計算可能性との関係性に焦点を当てて概説する．すなわち，ある列が「ランダムである」ことと，その列の計算という側面での「有用性」との関係を見る．証明には計算論の技術が主に使われる．前提知識としてTuring機械などの何らかの計算モデルの知識と，測度論の基本的知識は仮定する．話題は以下のものを考えている．
以下の講義ノート(アップロード予定)の中から，上記の話題の部分を取り出して，黒板に板書する形で進める．IDとパスワードは講義中に伝える．
以下の演習問題を解いて下さい．