人文科学研究科Graduate School of Humanities
PHL500B1（哲学 / Philosophy 500）論理学特殊講義２Lecture on Logic 2
安東 祐希
授業コードなどClass code etc
| 学部・研究科Faculty/Graduate school | 人文科学研究科Graduate School of Humanities |
| 添付ファイル名Attached documents | |
| 年度Year | 2022 |
| 授業コードClass code | X0064 |
| 旧授業コードPrevious Class code | |
| 旧科目名Previous Class title | |
| 開講時期Term | 秋学期授業/Fall |
| 曜日・時限Day/Period | 月2/Mon.2 |
| 科目種別Class Type | |
| キャンパスCampus | 市ヶ谷 |
| 教室名称Classroom name | 各学部・研究科等の時間割等で確認 |
| 配当年次Grade | |
| 単位数Credit(s) | 2 |
| 備考（履修条件等）Notes | |
| 実務経験のある教員による授業科目Class taught by instructors with practical experience | |
| カテゴリーCategory | 哲学専攻(博士後期課程) |
すべて開くShow all
すべて閉じるHide All
Outline (in English)
[Course outline]
This course deals with the relative computability.
[Learning Objectives]
By the end of the course, students should be able to do the followings with connectoins to related areas:
-To comprehend the notion of ``relative" on computability.
-To explain the hierarchy introduced by using the relative computability.
[Learning activities outside of classroom]
Students will be expected to do exercises by writing them on paper. Your study time will be more than four hours for a class.
[Grading Criteria/Policies]
Final grade will be calculated according to the following process:
Presentation as the person in charge for some parts of the text (50%) and contribution in question-and-answer sections (50%).
授業で使用する言語Default language used in class
日本語・英語併用 / Japanese & English
授業の概要と目的（何を学ぶか）Outline and objectives
春期科目の「論理学特殊講義１」に引き続き、帰納的関数論により、相対的な計算可能性とは何かを学ぶ。
到達目標Goal
関連分野への影響も踏まえながら、計算可能という概念の相対化について理解し、相対化に従って得られる階層構造について論ずることができる。
授業で使用する言語Default language used in class
日本語・英語併用 / Japanese & English
授業の進め方と方法Method(s)（学期の途中で変更になる場合には、別途提示します。 /If the Method(s) is changed, we will announce the details of any changes. ）
教科書に従い、省略されている詳細部分も含め、定義・定理・証明あるいは例を履修者が分担して発表し、それに対して教員および他の参加者により質疑応答を行う。（発表が「課題」であり、質疑応答において「フィードバック」する。）
アクティブラーニング（グループディスカッション、ディベート等）の実施Active learning in class (Group discussion, Debate.etc.)
あり / Yes
フィールドワーク（学外での実習等）の実施Fieldwork in class
なし / No
授業計画Schedule
授業形態/methods of teaching：対面/face to face
※各回の授業形態は予定です。教員の指示に従ってください。
第1回[対面/face to face]：relative recursion
教科書第12節
第2回[対面/face to face]：the arithmetical hierarchy (arithmetical relation etc.)
教科書第13節前半
第3回[対面/face to face]：the arithmetical hierarchy (arithmetical hierarchy theorem etc.)
教科書第13節後半
第4回[対面/face to face]：recursively enumerable relations (RE parameter theorem etc.)
教科書第14節前半
第5回[対面/face to face]：recursively enumerable relations (graph theorem etc.)
教科書第14節後半
第6回[対面/face to face]：degrees (definiton of degree etc.)
教科書第15節前半
第7回[対面/face to face]：degrees (Post's problem etc.)
教科書第15節後半
第8回[対面/face to face]：evaluation of degrees (Rice's proposition etc.)
教科書第16節前半
第9回[対面/face to face]：evaluation of degrees (Rogers' propositioin etc.)
教科書第16節後半
第10回[対面/face to face]：large RE sets (simple set etc.)
教科書第17節前半
第11回[対面/face to face]：large RE sets (Dekker's proposition etc.)
教科書第17節後半
第12回[対面/face to face]：functions of reals
教科書第18節
第13回[対面/face to face]：the analytical hierarchy
教科書第19節
第14回[対面/face to face]：the projective hierarchy
教科書第20節
授業時間外の学習（準備学習・復習・宿題等）Work to be done outside of class (preparation, etc.)
教科書の内容について、具体的な例を考え、紙に書きながら充分な演習を行うこと。なお、予復習時間の標準は4時間である。
テキスト（教科書）Textbooks
Joseph R. Shoenfield, Recursion Theory (Lecture Notes in Logic 1), A K Peters/CRC Press, 2001 (Springer-Verlag, 1993).
参考書References
Hartley Rogers, Jr., Theory of Recursive Functions and Effective Computability, The MIT Press, 1987 (McGraw-Hill, 1967).
成績評価の方法と基準Grading criteria
到達目標に関する問題の提示・解題能力を担当箇所の発表内容（50％）において、さらに、目標の問題全般にわたる理解度を他者担当時の質疑応答（50％）において評価する。
学生の意見等からの気づきChanges following student comments
担当者の発表と教員からの指摘について時間配分をより適切なものにしたい。
担当教員の専門分野等
〈専門領域〉
数理論理学（証明論）
〈研究テーマ〉
証明図の正規化手続きに関する諸性質
〈主要研究業績〉
・Church-Rosser property of a simple reduction for full first-order classical natural deduction, Annals of Pure and Applied Logic 119 (2003) pp225-237, Elsevier.
・A representation of essential reductions in sequent calculus (abstract), The Bulletin of Symbolic Logic 11 (2005) pp265-265, The Association for Symbolic Logic.
・Gentzen's unpublished normalization theorem and its successors, 数理解析研究所講究録 2083『証明論と証明活動』(2018) pp146-149, 京都大学数理解析研究所.