Computability learning seminar

Tuesday, September 16, 2014 3:30 pm - 3:30 pm EDT (GMT -04:00)

Sam Eisenstat, Department of Pure Mathematics, University of Waterloo

“Background for Computable Abelian Group Theory”

The class of abelian groups is somewhat well-behaved from the perspective of computability theory, since the theory of abelian groups is decidable. This implies, for example, that the word problem for finitely generated abelian groups is decidable. In this seminar, we survey basic definitions and theorems in abelian group theory and computable model theory, in order to state the main problems in computable abelian group theory. We define what it means for an abelian group to have a computable or computably enumerable presentation, and raise questions about the structure of such groups. We also discuss questions about the algorithmic complexity of isomorphisms between computable abelian groups and the complexity of the problem of whether an isomorphism exists.