Выдержка из книги
Лаллеман Ж.N.
Полугруппы и комбинаторные приложения
Обратное ( что гораздо труднее) тоже верно. Из ( с) теперь следует, что ограниченная проблема соответствия над алфавитом A Q а, р при 90 неразрешима. Кодируя A J а, р двухбуквенным алфавитом ( см. следствие 6.1.2), мы получаем неразрешимость ограниченной проблемы соответствия ( а значит, и общей проблемы соответствия) над любым алфавитом, содержащим более одной буквы.
