Logic Colloquium 2024

Special Session

Computable Structures

Chair: Alberto Marcone

  Tuesday, 14:00, J222 ! Live

Talks in this session


Meng-Che (Turbo) Ho, Decision problems for groups as equivalence relations

In 1911, Dehn proposed three decision problems for finitely presented groups: word problem, conjugacy problem, and isomorphism problem. These problems have been central to both group theory and logic, and were each proven to be undecidable in the 50s. There is much current research studying the decidability of these problems in classes of groups.

Although these problems are classically studied as decision problems, each of them is naturally an equivalence relation. In this talk, we study them as equivalence relations and compare them using computable reductions. This leads to a more refined measure of their complexity and brings new results and questions.

Parts of the talk are joint works with Uri Andrews, Matthew Harrison-Trainor, and Luca San Mauro.


Matthew Harrison-Trainor, Interpretations, back-and-forth games, and group von Neumann algebras

When defining the Ehrenfreucht-Fraisse back-and-forth games, it is common for model theorists to say that each player plays a single element at a time, while many computability theorists will often say that each player can play a tuple of arbitrary length. Both versions of these games appeared in Ehrenfreucht’s first treatment of back-and-forth games. However the two versions of the games can behave very differently, in particular by how they transfer through constructions like the construction from a ring \(R\) of the polynomial ring \(R[x]\). I will talk about some interesting aspects about the differences between the two versions of the back-and-forth games, and when one might use each one. One interesting example, from joint work with Isaac Goldbring, is the construction from a group of its group von Neumann algebra.


David Gonzalez, Generically computable linear orderings

W. Calvert, D, Cenzer and V. Harizanov introduced notions of generic computability for structures that are stratified by the computable ordinals. In a recent collaboration with these authors we examined these notions in the context of linear orderings. Our main results contrast one another. We show that every linear ordering has a 1-generically computable copy. On the other hand, we have that the set of linear orderings with a n-generically computable copy for \(n>1\) is as complicated as possible: \(\mathbf{\Sigma}_1^1\)-complete. This talk will put these results in context and describe the new, more structural approach we took to this problem. In particular, I will describe these results through the lens of a surprising connection with Ramsey-like properties.

 Overview  Program