Skip to main content

Alfred Tarski’s great algorithm. Decidability of elementary algebra and geometry

Posted in
Yuri Matiyasevich
Steklov Insitute of Mathematics, St. Petersburg
Mon, 2017-10-23 12:00 - 14:00
MPIM Lecture Hall

On of the most important decidability results is Tarski Theorem. It allows us to determine whether a closed first-order
formula with real variables is true or not. As a corollary we get the decidability of elementary geometry. The original
proof given by Tarski was very involved. After that it was simplified by many researchers. In my talk I am to present
a version of this algorithm which is 

  • easy to understand;
  • easy to implement on a computer; 
  • very inefficient (compared to modern advanced algorithms).
© MPI f. Mathematik, Bonn Impressum & Datenschutz
-A A +A