情報科学特別研究II

授業テーマ	計算可能性の理論の専門的な知識を学ぶ．
授業のねらい・到達目標	計算可能性の理論について，その専門文献を読み解くことができるように，基本的な知識と全体的な枠組みを学習する．Turing machine，再帰関数，ラムダ計算といった各種計算モデルの等価性と理解すること，計算可能性に関する直観的判断力を養うこと，対角線論法と還元可能性を利用した計算不可能性の証明手法を理解し応用力を養うことを主な目標とする．
授業の方法	履修者の論理学に対する知識や数学的素養の度合いに応じて，参考文献に記載した教科書などから一つを選んで購読する．学習に使用する教科書は第1回目の授業のときに決定する．下記の授業計画はOdifreddiによる教科書を選択した場合の学習のモデルケースを示している．
履修条件	情報科学特別研究Iを履修していること．さらに，本科目の担当者が別途担当するコンピュータ科学特論Iを履修することが望ましい．
事前学修・事後学修，授業計画コメント	教科書を事前に学習し，その内容をまとめた資料を作成し，授業時間に資料に基づいて発表する．教科書に記載されている演習問題を時間の許す限り解くことが望ましい．

授業計画
1	ガイダンス：履修者と相談しながら学習用の教科書を選定する．
2	概論と準備
3	帰納法，原始再帰関数，再帰関数
4	原始再帰関数の具体例，原始再帰法の除去
5	等式系による関数定義，一般再帰関数と再帰関数の等価性
6	算術における再帰関数の表現可能性
7	チューリング機械
8	再帰関数とチューリング計算可能性
9	フローチャートプログラム
10	様々な計算モデル
11	ラムダ計算
12	再帰関数の算術化
13	クリーネの標準形定理
14	計算概念のまとめ
15	チャーチ・チューリングの提唱
16	部分関数の計算可能性
17	RE集合，再帰的集合
18	対角線論法の基礎
19	非RE集合および非再帰的集合の存在性
20	停止性判定問題，Riceの定理
21	不動点定理
22	形式的体系の限界
23	自己参照
24	相対化された計算，チューリング還元可能性と次数
25	再帰的汎関数
26	第一再帰定理
27	指標と列挙
28	ポストの問題
29	多対一還元可能性
30	単純集合

その他
教科書	P. G. Odifreddi, Classical Recursion Theory, Elsevier, 1999, 2 edition NIegel Cutland, Computability: An Introduction to Recursive Function Theory, Cambridge University Press, 1980, 1 edition Borut Robič 『The Foundations of Computability Theory』 Springer 2015年第1版
成績評価の方法及び基準	授業参画度(100%)
オフィスアワー	毎週水曜日１２：１０〜１３：００