Logic and Computation II
In the last semester, we studied basics of computable functions, first-order logic and complexity theory. In this semester, we move on to Goedel's incompleteness theorems, second-order logic, infinite automata, desciriptive set theory, etc.
讲师
日期
2023年03月07日 至 06月06日
位置
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| 周二,周四 | 10:40 - 12:15 | A3-1-101 | ZOOM 05 | 293 812 9202 | BIMSA |
修课要求
"Logic and Computation I". Those who did not take our course last semester had better consult with the lecturer or TA before enrolling this course. Please find more information on "Logic and Computation I" at https://www.bimsa.cn/newsinfo/749634.html
课程大纲
"Logic and Computation I" included
Part 1. Introduction to Computational Theory
Part 2. Propositional Logic and Computational Complexity
Part 3. First Order Logic and Decision Problems
"Logic and Computation II" consists of the following four parts.
Part 4. Formal arithmetic and Goedel's incompletess theorems
First-order logic, arithmetical formulas,
Godel's first and second incompletess theorems,
Second-order logic, analytical formulas
Part 5. Automata on infite objects
Buechi automata and S1S, tree automata and S2S, finite model theory, parity games.
Part 6. Recursion-theoretic hierarchies
Oracle computation, m-degrees and T-degrees, arithmetical and analytical hierarchies,
descriptive set theory.
Part 7. Admissible ordinals and second order arithmetic
The KP set theory, admissible ordinals, recursively large ordinals, models of second-order arithmetics.
Part 1. Introduction to Computational Theory
Part 2. Propositional Logic and Computational Complexity
Part 3. First Order Logic and Decision Problems
"Logic and Computation II" consists of the following four parts.
Part 4. Formal arithmetic and Goedel's incompletess theorems
First-order logic, arithmetical formulas,
Godel's first and second incompletess theorems,
Second-order logic, analytical formulas
Part 5. Automata on infite objects
Buechi automata and S1S, tree automata and S2S, finite model theory, parity games.
Part 6. Recursion-theoretic hierarchies
Oracle computation, m-degrees and T-degrees, arithmetical and analytical hierarchies,
descriptive set theory.
Part 7. Admissible ordinals and second order arithmetic
The KP set theory, admissible ordinals, recursively large ordinals, models of second-order arithmetics.
参考资料
[1] H.D. Ebbinghaus, H. Flum and W. Thomas, Mathematical Logic, 3rd ed., Springer 2021.
[2] D.C. Kozen, Theory of Computation, Springer 2006.
[3] K. Tanaka, 計算理論と数理論理学 (Mathematics of Logic and Computation, in Japanese), Kyoritsu 2022.
[2] D.C. Kozen, Theory of Computation, Springer 2006.
[3] K. Tanaka, 計算理論と数理論理学 (Mathematics of Logic and Computation, in Japanese), Kyoritsu 2022.
听众
Undergraduate
, Graduate
视频公开
不公开
笔记公开
公开
语言
英文
讲师介绍
田中一之教授博士毕业于美国加州大学伯克利分校，曾就职于东京工业大学和东北大学，并指导15位博士生和50名硕士生，2022年正式入职BIMSA。他是数理逻辑和计算理论领域的国际知名学者，在反推数学和二阶算术领域开创了新的研究方法，如WKLo的田中嵌入定理和守恒结果的田中公式，取得了一系列奠基性的成果，并将这一研究方向引入日本，将日本的数理逻辑研究推向了世界水平。田中一之教授还致力于模态mu演算，认知逻辑，随机博弈树等交叉领域的研究。