Speaker: Toghrul Karimov
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; <, {2ⁿ : n ≥ 0}, {3ⁿ : n ≥ 0}) is decidable. (2) The first-order theory of (N; <, +, {2ⁿ : n ≥ 0}, {3ⁿ : n ≥ 0}) is undecidable. (3) The first-order theory of (N; <, n ↦ |τ(n)|), where τ(n) is the Ramanujan tau function, is undecidable.