Finitely presented algebraic systems, such as finitely presented groups,
are fundamental in algebra and computation. They have computably
enumerable word equality problems and are finitely generated. We refer
to finitely generated algebraic systems with computably enumerable word
equality problems as computably enumerable. Not all computably
enumerable, finitely generated algebraic systems are finitely presented.
This talk explores the quest for finitely presented expansions of
computably enumerable and finitely generated algebraic systems.
The expansion of algebraic systems, such as transforming groups into
rings or introducing automorphisms, is a key technique in algebra, model
theory and theoretical computer science. Bergstra and Tucker proved that
all computably enumerable algebraic systems with decidable word problems
have finitely presented expansions. They, along with Goncharov,
independently asked if every finitely generated computably enumerable
algebraic system has a finitely presented expansion.
In this talk we provide examples of finitely generated computably
enumerable semigroups, groups and algebras that lack finitely presented
expansions, thus answering the question of Bergstra–Tucker and
Goncharov. Additionally, we build examples of residually finite,
infinite and algorithmically finite groups, answering Miasnikov and
Osin's question. These constructions rely on the interplay between key
concepts from computability, such as simple and immune sets, and
algebra, such as residual finiteness and the
Golod–Shafarevich theorem.
About the speaker. Bakhadyr Khoussainov directs the
Algorithms and Logic Lab at the University of Electronic Science and
Technology of China and is Honorary Professor at the University of
Auckland. He began his undergraduate studies at Tashkent University
before transferring to Novosibirsk University, where he took his PhD in
algebra and logic, and has held professorships at Cornell and Auckland
with visiting appointments at Chicago, Kyoto, Heidelberg,
Wisconsin–Madison and the National University of Singapore. He
works on automatic structures, algorithmic game theory and computable
model theory, and has published more than 180 papers.
He is a Foreign Academician of Academia Europaea (2023) and a Fellow of
the Royal Society of New Zealand (2005). His awards include the EATCS
Nerode Prize (2021), the Humboldt Prize (2020), a Best Paper Award at
STOC (2017), the Chang Jiang Distinguished Professorship (2022) and the
Aitken Lectureship (2019). He has supervised 20 PhD students and served
as an editor of the Journal of Symbolic Logic. Outside mathematics he is
a champion-level coach in taekwondo and football.