Decidability of logical theories via rigidity and randomness in dynamical systems

30^th April 2026, 11:00 Ashton 208
Toghrul Karimov
MPI-SWS and IRIF

Abstract

Take an algebraic object M. We want to find algorithms that decide whether a given statement (in a suitable language) about M is true. I will discuss how dynamical systems have recently been used to produce such decidability and undecidability results, including the following. (1) The monadic second-order theory of (N;