0
$\begingroup$

I found in the book "Universal Algebra for Computer Scientists", by W. Wechler, the following statement : "In general, even for finite presentations, the word problem is unsolvable". In my belief, this statement is false since solving this problem can be done by building a finite set of ground rewrite rules, using a form of congruence closure. But it may be possible that it was still an open problem in 1992, when the book was published ? What do you think ? Thank you.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ You mean the word problem for finitely presented groups? Or algebras? What sort of algebraic structure? $\endgroup$
    – Ben McKay
    Commented Apr 9, 2021 at 15:13
  • $\begingroup$ The word algebra here is used more generally for an arbitrary signature. A finitely presented algebra is defined by a pair <G, R> where G is a finite set of "generators" et R is a finite set of pairs of terms built from the generators and the function symbols of the algebra. $\endgroup$
    – Baudouin Le Charlier
    Commented Apr 9, 2021 at 15:25
  • 4
    $\begingroup$ The argument you have in mind shows it's semidecidable. That is, you have an algorithm which takes two words, and if they represent the same element, eventually says "yes" while if they represent distinct elements, never stops. As already mentioned, it's not always decidable. There are semigroup examples, and much more complicated group examples. $\endgroup$
    – YCor
    Commented Apr 9, 2021 at 16:25

1 Answer 1

Reset to default
3
$\begingroup$

Novikov, P. S. (1955), On the algorithmic unsolvability of the word problem in group theory, Proceedings of the Steklov Institute of Mathematics (in Russian), 44: 1–143, Zbl 0068.01301; for more see Wikipedia. The associated group algebra over the rationals will still have unsolvable word problem.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ The word problem for semigroups was shown to be undecidable much earlier around 1947 independently by Markov and Post. This proof is much easier and can be understood as soon as you know the definition of a Turing machine. $\endgroup$
    – Benjamin Steinberg
    Commented Apr 9, 2021 at 18:05

Not the answer you're looking for? Browse other questions tagged .