In 1947, Markov and Post published independent papers showing that the word problem for semigroups cannot be effectively decided.
Το 1947, ο Markov και ο Post δημοσίευσαν ανεξάρτητες μελέτες που δείχνουν ότι η λέξη πρόβλημα για υποσύνολα δεν μπορεί να λυθεί αποτελεσματικά.