| 授業の目的 【日本語】 | | | 計算可能性理論は，20世紀前半にゲーデルが不完全性定理の証明に用いた（自然数上の）再帰的関数の定式化に始まり，続けてチャーチ，チューリング，ポストらがそれと同等な計算モデルを様々に考案した結果，計算可能性の普遍性が確立された。この講義ではそれらの計算モデルとその定式化の概要を学ぶことを第一の目的とする。数理情報学9においては特にチュリーングマシンと再帰的関数を中心に計算可能性理論の基礎を学習する。 |
|
|
| 授業の目的 【英語】 | | | The Computability Theory began with the formulation of the recursive function (natural number) which Godel used for the proof of the incompleteness theorems in the first half of the 20 century, and as a result of Church, Turing, and Post devising various calculation models equivalent to it, the universality of the computability was established. The primary purpose of this lecture is to study the outline of these computational models and their formulation. |
|
|
| 到達目標 【日本語】 | | | 計算可能性理論は，20世紀前半にゲーデルが不完全性定理の証明に用いた（自然数上の）再帰的関数の定式化に始まり，続けてチャーチ，チューリング，ポストらがそれと同等な計算モデルを様々に考案した結果，計算可能性の普遍性が確立された。この講義ではそれらの計算モデルとその定式化の概要を学ぶことを第一の目的とする。 |
|
|
| 到達目標 【英語】 | | |
|
| 授業の内容や構成 | | 数理情報学9においては計算可能性の定義を原始的なプログラム等（チューリングマシンやS-プログラム）を使って導入し，それと原始帰納的関数（再帰的関数）の関係を調べながら計算可能性理論の基礎を学習する。
1. プログラム
2. 計算可能関数
3. 原始帰納的関数
4. 帰納的関数
5. クリーネの正規形定理
6. 帰納定理・パラメータ定理
7. 相対化
8. 総括 | |
|
|
| 履修条件・関連する科目 | | |
|
| 成績評価の方法と基準 | | | 講義中に与える演習課題の評価30％，期末レポート70％，合計100点満点で60点以上を合格とする。 | |
|
|
| 教科書・参考書 | | 必要に応じて参考資料を配布する。
参考文献「帰納的関数と述語」篠田寿一著（河合文化教育研究所） | |
|
|
| 課外学習等（授業時間外学習の指示） | | | 講義において説明した理論を理解するために課題を与える。 | |
|
|
| 授業開講形態等 | | |
|
| 遠隔授業（オンデマンド型）で行う場合の追加措置 | | |
|