15:00
Fixed points of group homomorphisms and the Post Correspondence Problem
Abstract
The Post Correspondence Problem (PCP) is a classical problem in computer science that can be stated as: is it decidable whether given two morphisms g and h between two free semigroups $A$ and $B$, there is any nontrivial $x$ in $A$ such that $g(x)=h(x)$? This question can be phrased in terms of equalisers, asked in the context of free groups, and expanded: if the `equaliser' of $g$ and $h$ is defined to be the subgroup consisting of all $x$ where $g(x)=h(x)$, it is natural to wonder not only whether the equaliser is trivial, but what its rank or basis might be.
While the PCP for semigroups is famously insoluble and acts as a source of undecidability in many areas of computer science, the PCP for free groups is open, as are the related questions about rank, basis, or further generalisations. In this talk I will give an overview of what is known about the PCP in hyperbolic groups, nilpotent groups and beyond (joint work with Alex Levine and Alan Logan).