Word problem and unsolvability

Abstract

The Word Problem, a cornerstone of mathematical logic and group theory, asks whether two words—finite sequences of generators and their inverses—represent the same element in a group under a given presentation. Originating from Max Dehn’s early 20th-century work and further developed through seminal results by Novikov and Boone, the problem captures the essence of algorithmic decision-making in abstract algebra. This report explores the nature of the Word Problem in both solvable and unsolvable contexts. It surveys foundational group-theoretic constructs such as free groups, group presentations, and Cayley graphs, while highlighting conditions under which the Word Problem is algorithmically decidable—for instance, in finite, free, abelian and linear groups. The discussion then transitions into formal undecidability through Turing Machines, Church-Turing Thesis, and the Halting Problem. Central to this exploration is the demonstration that for certain finitely presented groups and semigroups, no general algorithm exists to solve the Word Problem, formalized through Post-Markov's theorem. This work emphasizes not only the theoretical implications of undecidability but also its relevance in computational logic and the boundaries of algorithmic reasoning.