The Word Problem for Some Classes of Semigroups

The word problem for finite semigroups is the following decision problem: given some number n of word pairs (u₁,v₁), …, (u_n,v_n) and an additional word pair (u₀,v₀), decide whether the n equations u₁=v₁,…, u_n=v_n impliy the additional equation u₀=v₀ 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   =  (u₁=v₁ and … and u_n=v_n). 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 (u₀,v₀) such that E implies u₀=v₀ in every periodic semigroup.
K2 is the class of word pairs (u₀,v₀) such that E fails to imply u₀=v₀ in some finite semigroup.
The paper contains some additional undecidability results.