Event Detail

Classically, the word problem of a group is the set of words equal to the identity of the group, and we analyze them using Turing reductions. In this talk, we consider the word problem of a group as a computably enumerable equivalence relation (ceer), namely, two words are equivalent if and only if they are equal in the group. We compare ceers using the computable reduction: E is reducible to F if there is a computable function f so that iEj if and only if f(i)Ff(j).

We will discuss some recent results and see that the landscape of word problems as ceers is very different from the classical theory. For instance, in the classical setting, any Turing degree can be realized as a word problem by first constructing a countable group and then embedding it into a finitely presented group via the Higman embedding theorem. However, we prove that in the ceer setting, there is a group G whose word problem is not universal, but for any nontrivial H, the free product G*H has a universal word problem.

This is a joint work with Uri Andrews and Luca San Mauro.