Potential Divisibility in Finite Semigroups is Undecidable
Stanislav Kublanovsky, Mark Valentinovich Sapir · International Journal of Algebra and Computation · 1998
We prove that there is no algorithm to decide, given a finite semigroup S and two elements a, b∈S, whether there exists a bigger finite semigroup T>S where a divides b and b divides a. This solves a thirty years old problem by John Rhodes.