In 1947, Markov and Post published independent papers showing that the word problem for semigroups cannot be effectively decided.
1947, Марков и Пост објавили су независно радове показујући да проблем речи у семигрупама не може бити ефективно одлучив.