Algebra Seminar talk
2025-12-19
Mohandes Grilj
The Word Problem for Groups
Abstract:
In this seminar paper we consider the following problem: Let $G$ be a group defined by a set of generators $S = \{s_{1}, \ldots s_n\}$ and equations $t_1=1, \ldots, t_m=1$. Is there an algorithm that determines whether a word in $S$ is trivial in $G$ or not? We can formalize the problem using group presentations and Turing machines. To then answer the posed question, we introduce a different kind of computational device - modular machines - and give Aanderaa and Cohen's proof of the Novikov-Boone Theorem.