清华主页 EN
导航菜单

Logic and Computation I

来源: 09-22

时间:10:40 - 12:15, Tue,Thu, 10/27/2022 - 12/27/2022

地点:Venue: 1110 Online: Zoom: 928 682 9093 PW: BIMSA

主讲人:Kazuyuki Tanaka (Research Fellow)

Record: Yes

Level: Graduate

Language: English


Prerequisite

Completion of undergraduate course on logic, set theory or automata theory is recommended. But all interested students are welcome.


Abstract

This is an advanced undergraduate and graduate-level course in mathematical logic and theory of computation. Topics to be presented in the first semester include: computable functions, undecidability, propositional logic, NP-completeness, first-order logic, Goedel's completeness theorem, Ehrenfeucht-Fraisse games, Presburger arithmetic.

In the second semester, we will move on to Goedel's incompleteness theorems, second-order logic, infinite automata, determinacy of infinite games, etc.



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.


Syllabus

"Logic and Computation I" consists of the following three parts.

Part 1. Introduction to Computational Theory

Fundamentals on theory of computation and computability theory (recursion theory) of mathematical logic, as well as the connection between them.

This part is the basis for the following lectures.

Part 2. Propositional Logic and Computational Complexity

The basics of propostional logic (Boolean algebra) and complexity theory including some classical results, such as the Cook-Levin theorem.

Part 3. First Order Logic and Decision Problems

The basics of first-order logic, Goedel's completeness theorem, and the decidability of Presburger arithmetic.

We will use Ehrenfeucht-Fraisse game as a basic tool of first-order logic, and apply it to prove Lindstrom's theorem.

In "Logic and Computation II", we will move on to Goedel's incompleteness theorem, second-order logic, infinite automata, determinacy of infinite games, Post's problem, the Kondo-Addison theorem, admissible sets, alpha-recursion theory, etc.


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/


Lecturer Email: tanaka.math@tohoku.ac.jp

TA: Dr. Wenjuan Li, liwj@bimsa.cn


返回顶部
相关文章
  • Logic and Computation I

    Record: YesLevel: GraduateLanguage: EnglishPrerequisiteCompletion of undergraduate course on logic, set theory or automata theory is recommended. But all interested students are welcome.AbstractThis is an advanced undergraduate and graduate-level course in mathematical logic and theory of computation. Topics to be presented in the first semester include: computable functions, undecidability, pr...

  • Introduction to Quantum Computation

    Record: YesLevel: GraduateLanguage: EnglishPrerequisiteQuantum Mechanics, Linear AlgebraAbstractIn this course, I present a self-consistent review of fault-tolerant quantum computation using the surface code. The course covers everything required to understand topological fault-tolerant quantum computation, ranging from the definition of the surface code to topological quantum error correction ...