В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 12

Проблема Тождества слов в конечно определенныхполугруппах и другие примечательные алгоритмическинеразрешимые проблемы10 ) Пусть даны алфавит A = {a1,... an } и множество пар слов S = {( Pi ,Qi )}, i ∈ Iв алфавите А. Пусть A ∗ - множество конечных слов в алфавите А. На множествеA ∗ определим отношение эквивалентности так.Определим два типа элементарных преобразований (ЭП):а) Левое Э.П.: замена в P ∈ A ∗ любого вхождения слова Pi словом Qi( P = W 1PWi 2 → W 1QiW 2 = Q ) .б) Правое Э.П.: замена в P ∈ A ∗ любого вхождения слова Qi словомPi ( P = W 1QiW 2 → W 1PWi 2 = Q).Если слово Q получено из Р одним элементарным преобразованием, то пишемP →Q.Слова P ,Q ∈ A ∗ назовем эквивалентными, если существует (конечная)последовательность слов R 1,..., R k , такая, чтоP = R 0 → R 1 →...

→ R k = Q .Если Р,Q эквивалентны, то пишем P ~ Q . Ясно, что отношение ~ естьотношение эквивалеютности. Класс эквивалентности, содержащий Р обозначим[P].Определим операцию умножения на классах[P][Q]=[PQ]Легко доказать, что данное определение корректно. Операция умноженияклассов ассоциативна ,и множество классов образует полугруппу П = A, S .Она называетсяполугруппой ,заданной образующими A и определяющими соотношениямиS.Если А-конечный алфавит ,то П конечно определенной.Проблемаэквивалкнтности слов в конечно определенной полугруппе ставится так: Длялюбых двух слов P ,Q ∈ A ∗ требуется узнать ,эквивалентны они или нет.(т.е.выпелнено ли [P]=[Q],поэтому проблему эквивалентности слов называютпроблемой тождества).Если такой алгоритм есть, то говорят, что проблема тождества разрешима, еслинет, то - неразрешима.Можно указать ряд полугрупп П, в которых проблема эквивалентностислов разрешима.Примеры:1.

П = a1 ,..., an ; (ai a j = a j ai ) , ∀i , j ∈1, n , i ≠ j .Ясно, что П - абелева{}полугруппа. Слова Р ,Q эквивалентны ⇔ они имеют одинаковое числовхождений каждой буквы из A = {a1,... an } . Это дает очевидный алгоритмпроверки эквивалентности любых P ,Q ∈ A ∗ .702. П = {a1 , a2 , a3 ; (a1a1 , a1 ) , ( a1a2 , a2 a1 ) , (a1a3 , a3a1 ) , (a2 a3 , a3 )} . Легкоkmnпоказать, что каждое слово из П эквивалентно слову вида a1 , a2 , a3 , где k=0,1m , n ∈ N 0 , что также дает очевидный алгоритм проверки эквивалентности слов.{3) П = a1 ,..., an , b1 ,..., bn ; (ai bi , λ ) , (bi ai , λ ) ∀i ∈1, n}λ - пустое слово. Легко показать, что данная полугруппа будет группой,называемой свободной группой. Наличие алгоритма проверки эквивалентностислов следует из того, что для каждого слова Р имеется единственноеэквивалентное несократимое слово P$ (т.е.

не содержащее вхождений вида(ai bi ) или ( bi ai ) ).В 40-х годах было установлено, что существуют конечно определенныеполугруппы, в которых проблема эквивалентности слов алгоритмическинеразрешима.Первые примеры таких полугрупп указали Марков А.А. и Пост Э.(1947). Данные примеры были довольно громоздкими. Цейтин Г.С. (1958)получил следующий пример такой полугруппы:A={a,b,c,d,e},S={(ab,da),(ac,ca),(bc,cb),(bd,db),(eca,ce),(edb,de),(cca,ccae)}(т.е.

5 букв, 7 соотношений).Матиясевич Ю.В. (1967) нашел полугруппу с двумя образующими и тремяопределяющими соотношениями с нерезрешимой проблемой эквивалентностислов. В одном из этих соотношений слева стоит слово из 304 букв, справа словоиз 608 букв.2 0 ) Приведем доказательство существования полугруппы с неразрешимойпроблемой эквивалентности слов. Сначала укажем конструкцию полугруппы Пт ,соответствующей машине Тьюринга Т. Пусть машина Т - имеет алфавитыQ = {q0 ,...

qm } , A = {a0 ,... an } и система команд qi a j → qk al S S ∈{R , L , E } .Соответствующая полугруппа Пт будет иметь образующиеAT = {a0 ,... an , q0 ,... qm , h} ,где h - новая буква. Определяющие соотношенияполучаются так:Команде qi a j → qk al S соответствует оотношение( qi a j , qk al )Команде qi a j → qk al L соответствует система оотношений( aqi a j , qk aal ),a ∈ A , ( hqi a j , hqk a0al )Команде qi a j → qk al R соответствует система оотношений( qi a j a, al qk a ),a ∈ A , ( qi a j h , al qk a0 h ) .В качестве системы определяющих соотношений ST берем объединениевсех соотношений, соответствующих всем командам машины Т. Получимполугруппу ПT = AT , ST .Машина Тьюринга Т осуществляет переработку машинных слов видаP = W q jW , V ,W ∈ N 0 .

Каждому машинному слову Р поставим в71соответствие элемент полугруппы ПТ вида P ′ = hW q jW h , который назовемобобщенным машинным словом.Лемма 1.Если машина Т переводит машинное слово Р в Q, то в полугруппе ПТ имеемP′ ~ Q′.Док-во.Утверждение ясно, поскольку командам машины Т соответствуют элементарныепреобразования в Пт .Лемма 2.Если P ′, Q ′ - обобщенные машинные слова из ПТ и слово Q ′ содержит q0 заключительное состояние, причем P ′ ~ Q ′ в полугруппе ПТ , то слово Q ′может быть получено из P ′ применением только левых элементарныхпреобразований.Док-во.По условию дано, что P ′ ~ Q ′ в ПТ .Значит, слово Q ′ получается из P ′ спомощью некоторой цепочки элементарных преобразованийP ′ = R 0 → R 1 →...

→ R k = Q ′ .Если в этой цепочке нет правых преобразований, то доказывать нечего. Пустьправые преобразования есть, тогда правое преобразование не может бытьпоследним, т.к. в Q ′ есть заключительное состояние q0 ,а в левых частяхопределяющих соотношений нет вхождений q0.Поэтому оно может появитьсятолько в результате левого преобразования.Возьмемпервое справа правоеэлементарное преобразование: R α → R α +1 → R α + 2Здесь переход R α → R α +1 осуществлен правым преобразованием , а переходR α +1 → R α +2 левым преобразованием.Пусть переход R α +1 → R α +2 осуществлен применением соотношения( qi a j , qk al ) . ЗначитR α +1 = R ′qi a j R ′′R α + 2 = R ′qk al R ′′Тогда переход R α → R α +1 (по правому преобразованию) долженосуществляться применением соотношения содержащеего в левой частивхождение qi a j , но такое соотношение единственно и совпадает с ( qi a j , qk al ) .Следовательно, R α = R α +2 и слово Q ′ можно получить из P ′ с помощьюцепочки из k-2 элементарных преобразований , в которой число правыхпреобразований уменьшено на единицу.Пусть теперь переход R α +1 → R α +2 осуществлен с помощьюсоотношения ( qi a j , qk aal ) .

Значит, R α +1 = R ′qi a j R ′′ , R α + 2 = R ′qk aal R ′′ .Тогда при переходе R α → R α +1(по правому преобразованию) должноиспользоваться соотношение с вхождением в левую часть qi a j . Но такоесоотношение единственно и имеет вид ( qi a j , qk aal ) т.е. снова получили72R α = R α +2 и опять слово Q ′ можно получить из P ′ с помощью цепочки из k-2элементарных преобразований , в которой число правых преобразованийуменьшено на единицу.Остальные случая разбираются аналогично.ч.т.д.Следствие.Если P,Q машинные слова и Q содержит q0 , то для соответствующихмашинных слов Q ′ , P ′ выполнено P ′ ~ Q ′ ⇔ машина Т переводит слово Р вслово Q.Теорема.Существует конечно определенная полугруппа с неразрешимой проблемойэквивалентности слов.Док-во.1 , если U ( x, x) оп ределеноне оп ределен а , else.Рассмотрим функцию f ( x) = Здесь U ( n, x ) - универсальная функция для одноместных частичнорекурсивных функций.

Поскольку U ( n, x ) - частично рекурсивна, то функцияf ( x ) - частично рекурсивна. Тогда существует машина Тьюринга Т0 , которая... переводит ввычисляет функцию f ( x ) т.е. начальные конфигурации q1{x+ 1заключительные q0 в том и только в том случае, когда f ( x ) =1.По машине Тьюринга Т0 строим конечно определенную полугруппу П0 .Это и есть полугруппа с неразрешимой проблемой эквивалентности слов. Пустьэто не так, т.е.

существует алгоритм проверки эквивалентности слов из П0 .Применим его к парам слов вида Px = hq1{... h и Q = hq0 h . По доказанномуx+ 1...Px ~ Q тогда и только тогда, когда машина Т0 переводит конфигурацию q1{x+ 1в q0 .

Теперь определим алгоритм вычисления функции1 , если U ( x, x) оп ределеноg ( x) = 0, else.следующим образом.Для всякого x ∈ N 0 полагаем g ( x ) = 1,если Px ~ Q и g ( x ) = 0,если Px ~/ Q .Получили противоречие, т.к. согласно теореме 3 предыдущего раздела, функцияg ( x ) невычислима.ч.т.д.Заметим, что для полугрупп с одним определяющим соотношениемпроблема эквивалентности слов разрешима в широком классе случаев и,вероятно, разрешима всегда, но пока доказательство этого факта неполучено.(1991)73Для конечно определенных полугрупп можно сформулировать алгоритмическуюпроблему распознавания свойств. Свойство полугруппы Q назовем марковским,если1) существует конечно определенная полугруппа, обладающая свойством Q;2) существует конечно определенная полугруппа, не вложимая ни в какуюконечно определенную полугруппу, обладавшую свойством Q.Для марковских свойств алгоритмическая проблема распознавания дляконечно определенных полугрупп неразрешима.

(Марков А.А. 1952).Конечно определенная полугруппа П=(A,S) называется конечноопределенной группой, если A = {a1,..., an , b1,..., bn } и среди соотношений Sесть соотношения вида {( ai bi , λ ) , ( bi ai , λ ) } λ -пустое слово.Неразрешимость проблемы эквивалентности слов для конечноопределенных групп была установлена Новиковым П.С. (1955). (Даннаяпроблема была сформулирована М.Деном в 1912 г.)Заметим, что для конечно определенных групп с одним определяющимсоотношением проблема эквивалентности слов разрешима.Неразрешимость алгоритмической проблемы проверки марковскихсвойств для конечно определенных групп была доказана Адяном С.И.1958).30 ) Выявлению разрешимых и неразрешимых задач в различных разделахматематики посвящено много исследований.

Приведем без доказательстванекоторые из примечательных таких проблем из алгебры, логики, теоретическойкибернетики, которые отличаются простотой формулировки ифундаментальностью.1. Проблема распознавания истинности формул элементарной арифметики.Формулы строятся с помощью арифмитических действий (сложения иумножения), логических операций (логических связок и кванторов) и знакаравенства, а также константы О и натуральнозначных переменных.