Algorithmic problems for amalgams of finite semigroups (Q1579152)

It is proved that there is an amalgam of two finite semigroups such that the corresponding amalgamated product has an undecidable word problem. Further, both the problems of embeddability of finite semigroup amalgams in arbitrary semigroups and into finite semigroups are undecidable. Moreover, the finite semigroups involved can be taken to have the property that all products of length four equal zero. The proofs use several versions of Minsky algorithms (one type of which consists of a numbered sequence of instructions for passing coins between two glasses) and a result of Slobodskoj's about undecidability of the universal theory of finite groups. The reader should note that the article was reprinted because of a typesetting error in the original which caused referencing to be omitted: the complete version is in ibid. 232, 767-785 (2000).