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.
Lecturer
Date
7th March ~ 6th June, 2023
Location
| Weekday | Time | Venue | Online | ID | Password |
|---|---|---|---|---|---|
| Tuesday,Thursday | 10:40 - 12:15 | A3-1-101 | ZOOM 05 | 293 812 9202 | BIMSA |
Prerequisite
"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
Syllabus
"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.
Reference
[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.
Audience
Undergraduate
, Graduate
Video Public
No
Notes Public
Yes
Language
English
Lecturer Intro
Kazuyuki Tanaka received his Ph.D. from U.C. Berkeley. Before joining BIMSA in 2022, he taught at Tokyo Inst. Tech and Tohoku University, and supervised fifteen Ph.D. students. He is most known for his works on second-order arithmetic and reverse mathematics, e.g., Tanaka's embedding theorem for WKLo and the Tanaka formulas for conservation results. For more details: https://sendailogic.com/tanaka.html