The Word Problem for Cancellation Semigroups with Zero

In 1947, Post showed the word problem for semigroups to be undecidable. In 1950, Turing strengthened this result to cancellation semigroups, i.e. semigroups satisfying the cancellation property
(1)         if xy = xz or yx = zx then y = z.
No semigroups with zero satisfies (1). The cancellation property for semigroups with zero and identity is
(2)         if xy = xz \neq 0 or yx = zx \neq 0 then y = z.
The cancellation property for semigroups with zero bur without identity is the conjunction of (2) and
(3)         if xy = x or yx = x then x = 0.
Whether or not a semigroup with zero has an identity, we refer to it as a cancellation semigroup with zero if it satisfies the appropriate cancellation property. It is shown in 8 (opens in new tab), that the word problem for finite semigroups is undecidable. Here we show that the word problem is undecidable for finite cancellation semigroups with zero; this holds for semigroups with identity and also for semigroups wihtout identity. (In fact, we prove a stronger effective inseparabilit result.) This provides the necessary mathematical foundation for 41 (opens in new tab)).