Skip to main content

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

Posted in
Speaker: 
Yuri Matiyasevich
Zugehörigkeit: 
Steklov Insitute of Mathematics, St. Petersburg
Datum: 
Mon, 23/10/2017 - 12:00 - 14:00
Location: 
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