The Word Problem for Some Classes of Semigroups - Gurevich, Yuri (Algebra and Logic (Russian), 1966)
The word problem for finite semigroups is the following decision problem: given some number n of word pairs (u1,v1), ..., (un,vn) and an additional word pair (u0,v0), decide whether the n equations u1=v1,..., un=vn impliy the additional equation u0=v0 in all finte semigroups. We prove that the word problem for finite semigroups is undecidable. In fact, the undecidability result holds for a particular premise E = (u1=v1 and ... and un=vn). Furthermore, this particular E can be chosen so that the following classes K1 and K2 of word pairs are recursively inseparable: K1 is the class of word pairs (u0,v0) such that E implies u0=v0 in every periodic semigroup. K2 is the class of word pairs (u0,v0) such that E fails to imply u0=v0 in some finite semigroup. The paper contains some additional undecidability results.