学部・大学院区分
Undergraduate / Graduate		情報・博前
時間割コード
Registration Code		2510025
科目区分
Course Category
主専攻科目
科目名　【日本語】
Course Title		計算可能性理論特論1
科目名　【英語】
Course Title		Theory of Computability 1
コースナンバリングコード
Course Numbering Code		GSI116025J
担当教員　【日本語】
Instructor		木原　貴行 ○ 吉信　康夫 松原　洋
担当教員　【英語】
Instructor		KIHARA Takayuki ○ YOSHINOBU Yasuo MATSUBARA Yo
単位数
Credits		1
開講期・開講時間帯
Term / Day / Period		秋１期 木曜日 ２時限
Fall1 Thu 2
対象学年
Year		１年
1
授業形態
Course style
開講系（学部）・開講専攻（大学院）
Subject
数理情報学専攻
必修・選択
Required / Selected
選択1単位


授業の目的　【日本語】
Goals of the Course(JPN)
計算可能性理論とは，「計算」，「計算可能」，「アルゴリズム」などの概念を数学的に定式化するという目的で創られた理論である。
この講義では，現代的な観点から計算可能性の理論を展開し，計算可能性に関する基本的で重要な定理を学習する。
また，抽象的な理論だけでなく，具体的な問題の計算可能性と不可能性についての理解を深めることも目指す。
授業の目的　【英語】
Goals of the Course
In this lecture we present several approaches to formalization of the concept of computability from the modern viewpoint. To understand the essence of the notion of computability, we also study fundamental theorems concerning recursive functions, partial combinatory algebras, realizability theory, and so on.
到達目標　【日本語】
Objectives of the Course(JPN)
この講義では具体的な決定問題を例にして，計算可能性や計算不可能性の証明法について学ぶ。
また，計算可能性の本質を理解するために，計算と論理の対応関係や，実現可能性に関する基本的な定理を学習する。
到達目標　【英語】
Objectives of the Course
授業の内容や構成
Course Content / Plan
1. イントロダクション
2. 型付きラムダ計算
3. カリー・ハワード対応
4. クリーネ実現可能性
5. 高階原始再帰
6. ゲーデルのシステムT
7. イプシロンノート再帰
8. 講義のまとめと展望
履修条件・関連する科目
Course Prerequisites and Related Courses
成績評価の方法と基準
Course Evaluation Method and Criteria
中間レポート５０％、期末のレポート５０％で評価し、合計１００点満点で６０点以上を合格とする。
教科書・参考書
Textbook/Reference book
必要に応じて参考資料を配布する。
課外学習等（授業時間外学習の指示）
Study Load(Self-directed Learning Outside Course Hours)
講義において説明した内容を理解するために課題を与える。
授業開講形態等
Lecture format, etc.
遠隔授業（オンデマンド型）で行う場合の追加措置
Additional measures for remote class (on-demand class)