計算可能性理論特論1

更新日:2017-05-11

時間割コード

2501409

ナンバリングコード

GSI-11-6025-J

科目区分

主専攻科目

単位数

選択1単位

授業形態

特論

対象学年

修士1・2年

学期 曜日 時間 集中講義の有無

秋1期木曜2限目

講義室

情報科学研究科棟1階第3講義室

開講専攻

数理情報学専攻

担当教員 所属

木原貴行,松原洋,吉信康夫

所属

数理情報学専攻

メールアドレス

yom@is.nagoya-u.ac.jp


授業概要


◆講義目的

計算可能性理論とは,「計算」,「計算可能」,「アルゴリズム」などの概念を数学的に定式化するという目的で創られた理論である。
この講義では,いかにしてそのような定式化が行われるかを学習することを目的とする。
またその定式化に基づいて,計算可能関数のクラスがもつ基本的で重要な性質を学ぶことを目指す。

◆授業内容

この講義では主に2つのアプローチによる計算可能性概念の定式化を紹介し,それらが同値であることの証明を通して,
計算可能性の概念の普遍性(Churchの提唱)を理解するとともに,計算可能関数のクラス(帰納的関数のクラス)に
関する基本的な定理を学習する。

〔計画〕
1. イントロダクション
2. S-プログラム
3. 計算可能性
4. 原始帰納的関数
5. 帰納的関数
6. チューリングマシン
7. Churchの提唱
8. 講義のまとめと今後の展望

◆教科書・参考文献・履修条件等

「帰納的関数と述語」篠田寿一著また必要に応じて参考資料を配布する。

◆授業期間中の課題・宿題等

講義において説明した内容を理解するために課題を与える。

成績評価方法・基準

講義中に与える課題の評価50%,期末のレポート50%で評価し,合計100点満点で60点以上を合格とする。

Course Title

Theory of Computability 1

Class Timetable Code

2501409

Numbering Code

GSI-11-6025-J

Course Category

Main majors

Credits

Elective1

Class Format

Advanced Lecture

Grade

Master1-2

Semester, Day and Period

Autumn 1 semester Thursday 2

Instructor(s)

MATSUBARA Yo,etc

Affiliation

Department of Mathematical Informatics

Mailaddress

yom@is.nagoya-u.ac.jp


Course Topics

In this lecture we present two distinct approaches to formalization of the concept of computability. By studying the proof showing that these formalizations define the same class of “computable” functions, we learn the universality of the concept of “computable”, which is the claim of Church-Turing’s Thesis. We also study fundamental theorems concerning the class of computable functions.

Course Purpose


Course Contents


Textbooks, Reference Materials and Requirements


Assignment


Grading Criteria