計算可能性理論特論2

更新日:2019-03-19

時間割コード

2501410

ナンバリングコード

GSI-11-6026-J

科目区分

主専攻科目

単位数

選択1単位

授業形態

特論

対象学年

修士1・2年

学期 曜日 時間 集中講義の有無

秋2期木曜2限目

講義室

情報学研究科棟1階第3講義室

開講専攻

数理情報学専攻

担当教員 所属

木原貴行,松原洋,吉信康夫

所属

数理情報学専攻

メールアドレス

kihara@i.nagoya-u.ac.jp


授業概要


◆講義目的

計算可能性理論とは,「計算」,「計算可能」,「アルゴリズム」などの概念を数学的に定式化するという目的で創られた理論である。
この講義では,現代的な観点から計算可能性の理論を展開し,計算可能性に関する基本的で重要な定理を学習する。
また,抽象的な理論だけでなく,具体的な問題の計算可能性と不可能性についての理解を深めることも目指す。

◆授業内容

「計算可能性理論特論2」では,計算可能性を空間的に理解できるようになることを目指す。
実現可能性を用いた表現空間の理論を導入し,具体的な数学的問題の計算可能性と不可能性について論じる。
そして,計算可能性の世界の広がりを認識し,計算に関する視野を広げることを目標とする。

(計画)
1. 表現空間と圏
2. ライスの定理と連結空間
3. 関数空間における計算可能性
4. 極限計算可能性
5. 算術的階層
6. 超限再帰の計算可能性
7. 数学における計算可能性
8. 講義のまとめと今後の展望

◆教科書・参考文献・履修条件等

必要に応じて参考資料を配布する。

◆授業期間中の課題・宿題等

講義において説明した内容を理解するために課題を与える。

成績評価方法・基準

中間のレポート50%,期末のレポート50%で評価し,合計100点満点で60点以上を合格とする。

Course Title

Theory of Computability 2

Class Timetable Code

2501410

Numbering Code

GSI-11-6026-J

Course Category

Main majors

Credits

Elective1

Class Format

Advanced Lecture

Grade

Master1-2

Semester, Day and Period

Autumn 2 semester Thursday 2

Instructor(s)

KIHARA Takayuki, MATSUBARA Yo, YOSHINOBU Yasuo

Affiliation

Department of Mathematical Informatics

Mailaddress

kihara@i.nagoya-u.ac.jp


Course Topics

In this course, we continue our study of the abstract framework of computability. We present how the notion of computability is connected to the notion of topology. We also study several basic concepts in computability theory such as limit computability, (hyper-)arithmetical hierarchy, effective transfinite recursion, and so on.

Course Purpose


Course Contents


Textbooks, Reference Materials and Requirements


Assignment


Grading Criteria