学部・大学院区分
Undergraduate / Graduate		情報学部
時間割コード
Registration Code		1001140
科目区分
Course Category
専門科目(自然情報)
関連専門科目(人社，CS)
科目名　【日本語】
Course Title		数理情報学１０
科目名　【英語】
Course Title		Mathematical Informatics 10
コースナンバリングコード
Course Numbering Code		SIS-11-3016-J
担当教員　【日本語】
Instructor		木原　貴行 ○ 吉信　康夫 松原　洋
担当教員　【英語】
Instructor		KIHARA Takayuki ○ YOSHINOBU Yasuo MATSUBARA Yo
単位数
Credits		1
開講期・開講時間帯
Term / Day / Period		秋２期 月曜日 ３時限
Fall2 Mon 3
対象学年
Year		３年
3
授業形態
Course style		講義
Lecture
開講系（学部）・開講専攻（大学院）
Subject
自然・数理情報
必修・選択
Required / Selected
選択


授業の目的　【日本語】
Goals of the Course(JPN)
この講義では数理情報学9で学習した計算可能性理論をより深く学習する。ラムダ関数や帰納的関数（再帰的関数）以外の計算可能性の定式化を紹介する。また停止問題やRiceの定理などを通して，計算不可能な関数に関する発展的話題について学ぶ。特に算術的階層について学ぶ。この講義では計算可能性の概念を関数だけではなく集合/述語にも拡張する。
授業の目的　【英語】
Goals of the Course
In this course, students learn more about the computability theory learned in Mathematical Informatics 9. We introduce the formulation of computability other than recursive functions and learn the existence proof of non-computable functions during class. And, here students also learn on uncomputability through halting problem, Rice's theorem, and so on. This lecture extends the concept of computability not only to functions but also to sets and predicates.
到達目標　【日本語】
Objectives of the Course(JPN)
数理情報学9で学習したことをもとにAckermann関数が帰納的だが原始帰納的ではないことを学習する。そしてRiceの定理や停止問題を使って計算不可能性について検証して行く。また帰納的可算な関数や述語の性質も調べて行く。ペアノの公理系を使って表現可能性と弱表現可能性という概念を導入し，それによる計算可能性の定式化を紹介する，そしてその応用として不完全性定理にも言及する。
到達目標　【英語】
Objectives of the Course
授業の内容や構成
Course Content / Plan
1. アッカーマン関数
2. 停止問題とビジービーバー関数
3. 計算不可能な問題の具体例
4. 再帰的枚挙可能性
5. 算術的階層
6. ペアノの公理系
7. ゲーデルの不完全性定理
8. 総括
履修条件・関連する科目
Course Prerequisites and Related Courses
成績評価の方法と基準
Course Evaluation Method and Criteria
講義中に与える演習課題の評価30％，期末レポート70％，合計100点満点で60点以上を合格とする。
教科書・参考書
Textbook/Reference book
必要に応じて参考資料を配布する。
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours)
講義において説明した理論を理解するために課題を与える。
授業開講形態等
Lecture format, etc.
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class)