数学基礎論サマースクール 2012　発展コース　講演概要

	
        ● アルゴリズム的ランダムネス入門�T,�U  (只木 孝太郎)      発表資料

	本講義では、アルゴリズム的ランダムネスの基本事項について
	説明する。そしてその応用として、アルゴリズム的情報理論の
	統計力学的解釈について解説する。
	    アルゴリズム的ランダムネスでは、“ランダム性”の概念が
	中心的役割を演じる。ランダムと言ってもこれは確率変数では
	なく、個々の無限二進列（0と1からなる片側無限列）それぞれ
	毎にランダムか否かが定義されるのである。講義では、最も
	基本的な2つのランダム性概念について解説する。1つはChaitin
	ランダム性の概念である。これはKolmogorov complexityの概念に
	基づいて定義され、万能チューリングマシンでも圧縮できない
	無限列を、ランダムであるとして定義する。もう1つはMartin-Löf
	ランダム性の概念である。これは構成的零集合の概念に基づいて
	定義され、どんな構成的零集合にも属しない無限列をランダム
	であるとして定義する。実は、これら2つのランダム性の定義は
	同値であり、この同値性はアルゴリズム的ランダムネスの中核を
	なすものである。講義ではこれを証明する。また、ランダムな
	無限列の具体例であるChaitinのΩを導入し、そのランダム性を
	証明する。最後に、ChaitinのΩの一般化概念として、
	アルゴリズム的情報理論の統計力学的解釈について解説する。


	
	● 代表的ランダム性�T,�U  (樋口 幸治郎)      講義ノート

	アルゴリズム的情報理論において、これまで様々な無限二進列に
	関するランダム性の概念が提出され、研究されてきた。それらのうち、
	比較的自然な発想に基づいて定義されるランダム性の概念として、
	Martin-Löfランダム性、Schnorrランダム性、computableランダム性が
	ある。本講義では、これらのランダム性の定義の発想を説明し、これら
	を定義する。これらの発想は、測度論によるもの、複雑性によるもの、
	マルティンゲールによるものに分類できるが、他のアプローチによる
	特徴付けを紹介する。また、これらのランダム性の相互関係を探求する。
	ランダム性の概念は、無限二進列以外の対象、例えば実数、にも拡張
	されるが、時間が許せば、これについても説明する。
	    尚、本講義の内容は、後の木原氏、宮部氏の講義における基礎
	知識として使われる。

	
	● ランダムの概念はどう使えるか  (宮部 賢志)      発表資料

	ランダムには「使えない」というイメージがある反面，
	乱択アルゴリズムに代表されるように「使える」ものでもある．
	本講義では「ランダム＝うまく振る舞う＝収束」という見方が
	数学的に正当化できることを説明する．例として挙げるのは，
	ランダムの概念の微分可能性による特徴付けと，エルゴード定理
	による特徴付けである．この2つは，ランダムネスの解析への
	応用として，最近特に活発に研究されている．また，上記の
	見方の応用として，正規数の構成問題についても触れる．

	
	● 歪んだコインとフラクタル�T,�U  (木原 貴行)      講義ノート

	ランダムな列を生成する一つの手段として，コインを投げ続ける
	という方法が考えられる．しかし，不幸なことに，手持ちのコインが
	全て歪んでいたらどうしよう．「歪んだコインから得られるランダム性
	とはどのようなものであろうか？」「歪み具合の異なる２つのコインが
	与えられたとき，そこから得られるランダム性の差異はどれくらい
	あるだろうか？」「歪んだコインを投げた結果から，正しいランダム列
	を構成し直すことができるだろうか？」
	    歪んだコインから得られるランダム性に関する素朴な疑問を基点に，
	コルモゴロフ複雑性，フラクタル幾何学，実数の集合論，力学系および
	位相エントロピーとの関連性を交えた，ランダムネス研究の解説を行う．

	
	● ランダムの概念はどう発展してきたか  (宮部 賢志)      発表資料

	ランダム，確率，予測などの概念は互いに密接に関係している．
	また，分類，推定，相関などの概念も関係が深い．実際，
	ランダムネスの理論が現れたことにより，それに関連する概念の
	見方に影響を与えている．本講義では，まず確率およびランダム
	に対する見方の歴史を紹介し，ランダムネスの理論の影響を受けて
	それらの見方がどう変わり，それが数学的にどう定式化されようと
	したか，またそれらが抱えている問題点などについて説明する．