Speaker
Florian Richter
Abstract
Suppose that we are given a finitely generated group G. The word problem for G can be stated as follows:
Is there an algorithm that determines whether two expressions in the given generators of G are equal?
Other decision problems in group theory are closely related to the word problem. For instance, is it possible to (algorithmically) decide whether a given finitely generated group G is abelian? Or finite? Or even trivial? Is there an algorithm that decides whether two given finitely generated groups G and H are isomorphic?
There is a strong dichotomy between the word problem and the notion of recursively enumerable sets on N, and those have close connections with the Halting problem (Alan Turing, 1936). The peak of this theory is the Boone-Higman Theorem, providing a wonderful tie-up between logic and algebra.