情報科学特別研究Ⅱ

科目名	情報科学特別研究Ⅱ
教員名	戸田誠之助
単位数	4	課程	前期課程	開講区分	文理学部
科目群	地球情報数理科学専攻
学期	通年	履修区分	必修

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

授業計画
1	ガイダンス：履修者と相談しながら学習用の教科書を選定する．【事前学習】シラバスを事前に確認する【事後学習】選定した教科書を用意する．
2	概論と準備【事前学習】発表用資料を準備する．【事後学習】数学的な基礎概念を理解する．
3	帰納法，原始再帰関数，再帰関数【事前学習】発表用資料を準備する．【事後学習】原始再帰法と最小化作用素を理解する．
4	原始再帰関数の具体例，原始再帰法の除去【事前学習】発表用資料を準備する．【事後学習】原始再帰関数と再帰関数について理解を深める．
5	等式系による関数定義，一般再帰関数と再帰関数の等価性【事前学習】発表用資料を準備する．【事後学習】再帰関数について理解を深める．
6	算術における再帰関数の表現可能性【事前学習】発表用資料を準備する．【事後学習】再帰関数の表現可能性を理解する．
7	チューリング機械【事前学習】発表用資料を準備する．【事後学習】チューリング機械を理解する．
8	再帰関数とチューリング計算可能性【事前学習】発表用資料を準備する．【事後学習】チューリング機械による計算可能性を理解する．
9	フローチャートプログラム【事前学習】発表用資料を準備する．【事後学習】フローチャートプログラムを理解する．
10	様々な計算モデル【事前学習】発表用資料を準備する．【事後学習】様々な計算モデルを理解する．
11	ラムダ計算【事前学習】発表用資料を準備する．【事後学習】ラムダ計算を理解する．
12	再帰関数の算術化【事前学習】発表用資料を準備する．【事後学習】再帰関数の算術化を理解する．
13	クリーネの標準形定理【事前学習】発表用資料を準備する．【事後学習】クリーネの標準形定理を理解する．
14	計算概念のまとめ【事前学習】発表用資料を準備する．【事後学習】様々な計算概念の等価性について理解を深める．
15	チャーチ・チューリングの提唱【事前学習】発表用資料を準備する．【事後学習】チャーチ・チューリングの提唱について理解を深める．
16	部分関数の計算可能性【事前学習】発表用資料を準備する．【事後学習】部分関数の計算可能性について理解を深める．
17	RE集合，再帰的集合【事前学習】発表用資料を準備する．【事後学習】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%) 授業参画度は，毎回の発表用資料（レジメ，プレゼン資料等）をもとに評価します．
オフィスアワー	毎週水曜日１２：１０〜１３：００

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