Проблема тождества для полугрупп

Лекция 10 Проблема тождества для полугрупп Пусть A – конечный алфавит, - множество всех слов в алфавите A. Обозначим через S множество тождеств . Будем говорить, что слова d и f эквивалентны, если от слова d к слову f можно перейти путём выполнения конечного числа замен из S. Проблема тождества для полугрупп (проблема Туэ) состоит в ответе на вопрос, являются ли слова d и f эквивалентными. Теорема 1. Проблема Туэ является алгоритмически неразрешимой. Доказательство. Покажем, что задача распознавания слова сводится к вопросу об эквивалентности слов для некоторой схемы S. Пусть Al – произвольный алгоритм, заданный машиной Тьюринга в алфавите A и множеством состояний Q. Машина Тьюринга пусть задана в виде отображениями и . Построим по этим отображениям схему S. При этом воспользуемся идеями, использованными при доказательстве алгоритмической сводимости машины Тьюринга к нормальному алгорифму Маркова (Error: Reference source not found). Текущее состояние программы закодируем словом . Положение универсального считывающего устройства будем кодировать положением самого слова в слове, к которому применяется схема. Будем считать, что универсальное считывающее устройство просматривает первый справа символ от слова состояния. Входное слово имеет вид , где разделитель играет роль ограничителя входного слова. Приведём правило замены отображений подстановками. При этом символы алфавита будем обозначать , а движение универсального считывающего устройства – символами r, l, s. Отображение Подстановки Комментарий , , при добавляется еще состояние не конечное , , при добавляется еще подстановка состояние конечное , , при добавляется еще подстановка состояние не конечное , , при добавляется еще подстановка состояние конечное , , при добавляется еще подстановка состояние не конечное , , при добавляется еще подстановка состояние конечное , для каждого добавляются , и состояние не конечное. , , при добавляется еще подстановка состояние конечное не определено , при добавляется еще подстановка Дополнительно и Если в указанных тождествах знак равенства заменить на , то получим схему нормального алгорифма Маркова, моделирующую работу машины Тьюринга (Error: Reference source not found). Следовательно, если слово X распознается алгоритмом Al, то слово эквивалентно слову . Допустим, что слова и - эквивалентны. Замену будем обозначать буквой R и называть правой, если заменяем правую часть равенства из схемы на левую, и L (левая)– в противном случае. Выполнение последовательности замен вида R, L не меняет слова. Следовательно, можно считать, что последовательность замен имеет вид . Поскольку, в левых частях равенств из схемы нет слова , то заменой правых частей на левые невозможно получить слово . Таким образом, слово может быть получено из слова только последовательным выполнением левых замен. Выполнение левых замен равносильно работе машины Тьюринга. Таким образом, если слово эквивалентно слову , то слово X распознается алгоритмом Al. Поскольку вопрос о распознаваемости слова X алгоритмом Al сводится к вопросу об эквивалентности слов и , а задача распознавания алгоритмически неразрешима (Error: Reference source not found), то тем самым показана алгоритмическая неразрешимость проблемы Туэ.