計算可能性理論特論1

更新日:2019-03-19

時間割コード

2501409

ナンバリングコード

GSI-11-6025-J

科目区分

主専攻科目

単位数

選択1単位

授業形態

特論

対象学年

修士1・2年

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

秋1期木曜2限目

講義室

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

開講専攻

数理情報学専攻

担当教員 所属

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

所属

数理情報学専攻

メールアドレス

kihara@i.nagoya-u.ac.jp


授業概要


◆講義目的

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

◆授業内容

この講義では具体的な決定問題を例にして,計算可能性や計算不可能性の証明法について学ぶ。
また,計算可能性の本質を理解するために,部分コンビネータ代数や実現可能性に関する基本的な定理を学習する。

(計画)
1. イントロダクション
2. 計算可能性と不可能性
3. 様々な決定問題
4. 語の問題とトポロジーにおける決定問題
5. 行列のモータリティ問題
6. ラムダ計算とコンビネータ
7. 再帰定理
8. 講義のまとめと展望

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

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

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

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

成績評価方法・基準

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

Course Title

Theory of Computability 1

Class Timetable Code

2501409

Numbering Code

GSI-11-6025-J

Course Category

Main majors

Credits

Elective1

Class Format

Advanced Lecture

Grade

Master1-2

Semester, Day and Period

Autumn 1 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 lecture we present several approaches to formalization of the concept of computability from the modern viewpoint. To understand the essence of the notion of computability, we also study fundamental theorems concerning recursive functions, partial combinatory algebras, realizability theory, and so on.

Course Purpose


Course Contents


Textbooks, Reference Materials and Requirements


Assignment


Grading Criteria