計算可能性理論特論2

更新日:2017-05-11

時間割コード

2501410

ナンバリングコード

GSI-11-6026-J

科目区分

主専攻科目

単位数

選択1単位

授業形態

特論

対象学年

修士1・2年

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

秋2期木曜2限目

講義室

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

開講専攻

数理情報学専攻

担当教員 所属

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

所属

数理情報学専攻

メールアドレス

yom@is.nagoya-u.ac.jp


授業概要


◆講義目的

計算可能性理論とは,「計算」,「計算可能」,「アルゴリズム」などの概念を数学的に定式化するという目的で創られた理論である。
この講義では,いかにしてそのような定式化が行われるかを学習することを目的とする。
またその定式化に基づいて,計算可能関数のクラスがもつ基本的で重要な性質を学ぶことを目指す。

◆授業内容

「計算可能性理論特論2」ではより詳しく原始帰納的関数のクラスと帰納的関数のクラスについて学習する。
帰納的関数論の基本的な定理であるKleeneの正規形定理やパラメータ定理とそれらの応用について学んで行く。
また計算可能性の概念を関数のみではなく述語/集合へと拡張した後,Riceの定理などを使って帰納的ではない述語/集合について学習する。
そして計算可能性の概念をオラクルを使って相対化していく。

〔計画〕
1. Kleeneの正規形定理
2. パラメータ定理
3. 帰納定理
4. Ackermann関数
5. Riceの定理
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)

MATSUBARA Yo,etc

Affiliation

Department of Mathematical Informatics

Mailaddress

yom@is.nagoya-u.ac.jp


Course Topics

In this course, we continue our study of recursive functions and primitive recursive functions. We present fundamental theorems such as Kleene’s normal form theorem and the parameter theorem. We also extend the concept of computability of functions to that of sets and predicates. By presenting theorems such as Rice’s theorem, we study non-recursive sets and predicates. The relativization of computability using the concept of oracles will also be presented.

Course Purpose


Course Contents


Textbooks, Reference Materials and Requirements


Assignment


Grading Criteria