Coursera Flash Sale
40% Off Coursera Plus for 3 Months!
Grab it
Explore a mathematical lecture that presents a significant strengthening of Cobham's famous theorem in automata theory and logic. Delve into the relationship between k-recognizable sets and their computational complexity when dealing with multiplicatively independent integers. Learn how subsets of natural numbers that are recognizable in different bases relate to Presburger-definable sets, and discover the groundbreaking result that combining two non-Presburger definable sets recognizable in multiplicatively independent bases leads to undecidable first-order theories. Understand the contrast with Büchi's theorem about the decidability of first-order theories with single recognizable sets, and examine how this work builds upon and extends previous research by Villemaire and Bès. Gain insights into why recognizability is fundamentally dependent on the choice of base and how this dependency creates computational intractability when multiple bases are involved. The presentation demonstrates that sets recognizable in multiplicatively independent bases are not merely distinct but create together a computationally intractable framework over Presburger arithmetic, representing collaborative research with Chris Schulz that advances our understanding of the intersection between automata theory, logic, and computational complexity.
