| 授業の目的 【日本語】 | | | この講義では数理情報学9で学習した計算可能性理論をより深く学習する。チューリング計算可能性や再帰的関数以外の計算可能性の定式化を紹介する，そしてRadoによるチューリングマシンの概念を使った計算不可能な関数の存在証明を学ぶ。その応用として停止問題を紹介する。また原始帰納的関数（原始再帰的関数）と再帰的関数の関係も考察する。この講義では計算可能性の概念を関数だけではなく集合/述語にも拡張する。 |
|
|
| 授業の目的 【英語】 | | | 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 stop problem, Rice's theorem, and so on. This lecture extends the concept of computability not only to functions but also to sets and predicates. |
|
|
| 到達目標 【日本語】 | | | この講義では数理情報学9で学習した計算可能性理論をより深く学習する。帰納的関数（再帰的関数）以外の計算可能性の定式化を紹介する，そして計算不可能な関数の存在証明を学ぶ。また停止問題やRiceの定理などを通して，計算不可能性について学習する。この講義では計算可能性の概念を関数だけではなく集合/述語にも拡張する。 |
|
|
| 到達目標 【英語】 | | |
|
| 授業の内容や構成 | | 数理情報学9で学習したことをもとにAckermann関数が帰納的だが原始帰納的ではないことを学習する。そしてRiceの定理や停止問題を使って計算不可能性について検証して行く。また帰納的可算な関数や述語の性質も調べて行く。ペアノの公理系を使って表現可能性と弱表現可能性という概念を導入し，それによる計算可能性の定式化を紹介する，そしてその応用として不完全性定理にも言及する。
1. Ackermann関数
2. Riceの定理
3. 停止問題
4. 帰納的可算な関数と述語
5. ペアノの公理系
6. 表現可能と弱表現可能述語
7. 不完全性定理
8. 総括 | |
|
|
| 履修条件・関連する科目 | | |
|
| 成績評価の方法と基準 | | | 講義中に与える演習課題の評価30％，期末レポート70％，合計100点満点で60点以上を合格とする。 | |
|
|
| 教科書・参考書 | | 必要に応じて参考資料を配布する。
参考文献「帰納的関数と述語」篠田寿一著（河合文化教育研究所） | |
|
|
| 課外学習等（授業時間外学習の指示） | | | 講義において説明した理論を理解するために課題を与える。 | |
|
|
| 授業開講形態等 | | |
|
| 遠隔授業（オンデマンド型）で行う場合の追加措置 | | |
|