Nierozstrzygalność problemu słowa dla półgrup Problemem jest rozstrzygnięcie, czy dla dowolnej struktury spełniającej skończony zbiór równoważności Yuri Gurevich, Harry L. Lewis, The Word Problem for Cancellation Semigroups with Zero, s. 184.. Naturalną reprezentacją półgrup są ciągi elementów nad skończonym alfabetem z działaniem konkatenacji, stąd nazwa problemu.
Nierozstrzygalność problemu pokrycia płaszczyzny thumb|Można pokazać, że powyższy zbiór 11 płytek pozwala na pokrycie płaszczyzny, jednak tylko w sposób nieokresowy.
Przypuśćmy, że dysponujemy skończonym zbiorem jednostkowych kwadratów ze zdefiniowanymi kolorami krawędzi poziomych i pionowych. Przedmiotem problemu jest pytanie, czy możliwe jest pokrycie płaszczyzny euklidesowej elementami tego zbioru, stosując jedynie translacje (bez obrotów) przy założeniu, że sąsiadujące krawędzie dowolnej pary kwadratów muszą mieć ten sam kolor. Nie istnieje ogólny algorytm odpowiadający na tak postawione pytanie w skończonej liczbie kroków.