授業の目的 【日本語】
Goals of the Course(JPN) | | | 計算可能性理論は，20世紀前半にゲーデルが不完全性定理の証明に用いた（自然数上の）再帰的関数の定式化に始まり，続けてチャーチ，チューリング，ポストらがそれと同等な計算モデルを様々に考案した結果，計算可能性の普遍性が確立された。この講義ではそれらの計算モデルとその定式化の概要を学ぶことを第一の目的とする。数理情報学9においては特にラムダ計算と再帰的関数を中心に計算可能性理論の基礎を学習する。 |
|
|
授業の目的 【英語】
Goals of the Course | | | 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. |
|
|
到達目標 【日本語】
Objectives of the Course(JPN) | | | 計算可能性理論は，20世紀前半にゲーデルが不完全性定理の証明に用いた（自然数上の）再帰的関数の定式化に始まり，続けてチャーチ，チューリング，ポストらがそれと同等な計算モデルを様々に考案した結果，計算可能性の普遍性が確立された。この講義ではそれらの計算モデルとその定式化の概要を学ぶことを第一の目的とする。 |
|
|
到達目標 【英語】
Objectives of the Course | | |
|
授業の内容や構成
Course Content / Plan | | 数理情報学9においては計算可能性の定義を原始的なプログラム等（ラムダ計算やコンビネータ）を使って導入し，それと原始帰納的関数（再帰的関数）の関係を調べながら計算可能性理論の基礎を学習する。
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) | | |
|