§ 11. Проблема Тождества слов в конечно определенных полугруппах и другие примечательные алгоритмически неразрешимые проблемы

10 ) Пусть даны алфавит A ={a1,...an } и множество пар слов S ={(Pi ,Qi )},i I в алфавите А. Пусть A - множество конечных слов в алфавите А. На множестве A определим отношение эквивалентности так.

Определим два типа элементарных преобразований (ЭП):
а) Левое Э.П.: замена в P A любого вхождения слова P словом Q						i
					i
(P =W PW		→W Q W		= Q) .
1	i 2		1 i 2
б) Правое Э.П.: замена в P A любого вхождения слова Qi словом
P (P =W Q W			→W PW		= Q) .
i	1 i 2		1 i 2

Если слово Q получено из Р одним элементарным преобразованием, то пишем

P →Q .

Слова P,Q A назовем эквивалентными, если существует (конечная) последовательность слов R1,...,R k , такая, что

P = R0 → R1 →...→ R k = Q .

Если Р,Q эквивалентны, то пишем P ~ Q . Ясно, что отношение ~ есть отношение эквивалеютности. Класс эквивалентности, содержащий Р обозначим [P].Определим операцию умножения на классах

[P][Q]=[PQ]

Легко доказать, что данное определение корректно. Операция умножения классов ассоциативна ,и множество классов образует полугруппу П = A, S .

Она называется

полугруппой ,заданной образующими A и определяющими соотношениями S.Если А-конечный алфавит ,то П конечно определенной.Проблема эквивалкнтности слов в конечно определенной полугруппе ставится так: Для

любых двух слов P,Q A требуется узнать ,эквивалентны они или нет.(т.е. выпелнено ли [P]=[Q],поэтому проблему эквивалентности слов называют проблемой тождества).

Если такой алгоритм есть, то говорят, что проблема тождества разрешима, если нет, то - неразрешима.

Можно указать ряд полугрупп П, в которых проблема эквивалентности слов разрешима.

Примеры:

1. П = {a1,...,an ; (aia j = a jai ) , i, j 1,n ,i ≠ j}.Ясно, что П - абелева полугруппа. Слова Р ,Q эквивалентны они имеют одинаковое число вхождений каждой буквы из A ={a1,...an }. Это дает очевидный алгоритм

проверки эквивалентности любых P,Q A .

70

2. П = {a1,a2 ,a3 ; (a1a1,a1) , (a1a2 ,a2a1) , (a1a3 , a3a1) , (a2a3 ,a3 )}. Легко показать, что каждое слово из П эквивалентно слову вида a1k ,a2m ,a3n , где k=0,1 m,n N 0 , что также дает очевидный алгоритм проверки эквивалентности слов.

3)П = {a1,...,an , b1,...,bn ; (aibi ,λ ) , (biai ,λ ) i 1,n }

λ- пустое слово. Легко показать, что данная полугруппа будет группой, называемой свободной группой. Наличие алгоритма проверки эквивалентности слов следует из того, что для каждого слова Р имеется единственное

эквивалентное несократимое слово P$ (т.е. не содержащее вхождений вида

(aibi ) или (biai ) ).

В 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 букв.

20 ) Приведем доказательство существования полугруппы с неразрешимой проблемой эквивалентности слов. Сначала укажем конструкцию полугруппы Пт , соответствующей машине Тьюринга Т. Пусть машина Т - имеет алфавиты

Q ={q0,...qm }, A ={a0,...an} и система команд qiaj → qk alS S {R ,L,E}.

Соответствующая полугруппа Пт будет иметь образующие

AT ={a0,...an ,q0,...qm , h},где h - новая буква. Определяющие соотношения получаются так:

Команде qiaj → qk alS соответствует оотношение

(qiaj ,qk al )

Команде qiaj → qk al L соответствует система оотношений

(aqiaj ,qk aal ),a A , (hqiaj ,hqk a0al )

Команде qiaj → qk al R соответствует система оотношений

(qiaja,alqk a),a A , (qiaj h ,alqk a0h).

В качестве системы определяющих соотношений ST берем объединение всех соотношений, соответствующих всем командам машины Т. Получим полугруппу ПT = AT , ST .

Машина Тьюринга Т осуществляет переработку машинных слов вида P =W qjW , V ,W N 0 . Каждому машинному слову Р поставим в

71

соответствие элемент полугруппы ПТ вида P ′ = hW qjW h , который назовем

обобщенным машинным словом. Лемма 1.

Если машина Т переводит машинное слово Р в Q, то в полугруппе ПТ имеем

P ′ ~ Q ′ .

Док-во.

Утверждение ясно, поскольку командам машины Т соответствуют элементарные преобразования в Пт .

Лемма 2.

Если P ′,Q ′ - обобщенные машинные слова из ПТ и слово Q ′ содержит q0 - заключительное состояние, причем P ′ ~ Q ′ в полугруппе ПТ , то слово Q ′ может быть получено из P ′ применением только левых элементарных преобразований.

Док-во.

По условию дано, что P ′ ~ Q ′ в ПТ .Значит, слово Q ′ получается из P ′ с помощью некоторой цепочки элементарных преобразований

P ′ = R0 → R1 →...→ R k = Q′.

Если в этой цепочке нет правых преобразований, то доказывать нечего. Пусть правые преобразования есть, тогда правое преобразование не может быть последним, т.к. в Q ′есть заключительное состояние q0 ,а в левых частях определяющих соотношений нет вхождений q0.Поэтому оно может появиться только в результате левого преобразования.Возьмемпервое справа правое элементарное преобразование: Rα → Rα +1 → Rα +2

Здесь переход Rα → Rα +1 осуществлен правым преобразованием , а переход Rα+1 → Rα+2 левым преобразованием.

Пусть переход Rα+1 → Rα+2 осуществлен применением соотношения

(qiaj ,qk al ). Значит

Rα+1 = R ′qiaj R ′′ Rα+2 = R ′qk al R ′′

Тогда переход Rα → Rα +1 (по правому преобразованию) должен осуществляться применением соотношения содержащеего в левой части вхождение qiaj , но такое соотношение единственно и совпадает с (qiaj ,qk al ).

Следовательно, Rα = Rα +2 и слово Q ′ можно получить из P ′с помощью

цепочки из k-2 элементарных преобразований , в которой число правых преобразований уменьшено на единицу.

Пусть теперь переход Rα+1 → Rα+2 осуществлен с помощью соотношения (qiaj ,qk aal ). Значит, Rα+1 = R ′qiaj R ′′ , Rα+2 = R ′qk aal R ′′. Тогда при переходе Rα → Rα +1(по правому преобразованию) должно использоваться соотношение с вхождением в левую часть qiaj . Но такое

соотношение единственно и имеет вид (qiaj ,qk aal ) т.е. снова получили

72

Rα = Rα +2 и опять слово Q ′ можно получить из P ′с помощью цепочки из k-2

элементарных преобразований , в которой число правых преобразований уменьшено на единицу.

Остальные случая разбираются аналогично.

ч.т.д.

Следствие.

Если P,Q машинные слова и Q содержит q0 , то для соответствующих машинных слов Q ′, P ′выполнено P ′ ~ Q ′ машина Т переводит слово Р в слово Q.

Теорема.

Существует конечно определенная полугруппа с неразрешимой проблемой эквивалентности слов.

Док-во.

1 , если U(x, x) определено

Рассмотрим функцию f (x) =

не определена , else.

Здесь U (n,x ) - универсальная функция для одноместных частично рекурсивных функций. Поскольку U (n,x ) - частично рекурсивна, то функция f (x ) - частично рекурсивна. Тогда существует машина Тьюринга Т0 , которая

вычисляет функцию f (x ) т.е. начальные конфигурации q ... переводит в

1 { x+1

заключительные q0 в том и только в том случае, когда f (x )=1.

По машине Тьюринга Т0 строим конечно определенную полугруппу П0 . Это и есть полугруппа с неразрешимой проблемой эквивалентности слов. Пусть это не так, т.е. существует алгоритм проверки эквивалентности слов из П0 .

Применим его к парам слов вида P = hq ... h и							Q = hq h . По доказанному
					x	1 {	0
						x+1
P	x	~ Q тогда и только тогда, когда машина Т0 переводит конфигурацию q ...
							1	{
								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

есть соотношения вида {(aibi ,λ ) , (biai ,λ ) } λ -пустое слово.

Неразрешимость проблемы эквивалентности слов для конечно определенных групп была установлена Новиковым П.С. (1955). (Данная проблема была сформулирована М.Деном в 1912 г.)

Заметим, что для конечно определенных групп с одним определяющим соотношением проблема эквивалентности слов разрешима.

Неразрешимость алгоритмической проблемы проверки марковских свойств для конечно определенных групп была доказана Адяном С.И.1958).

30 ) Выявлению разрешимых и неразрешимых задач в различных разделах математики посвящено много исследований. Приведем без доказательства некоторые из примечательных таких проблем из алгебры, логики, теоретической кибернетики, которые отличаются простотой формулировки и фундаментальностью.

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

2.Проблема разрешения для логики предикатов первого порядка. Нужно найти алгоритм, который бы проверял общезначимость формулы алгебры предикатов. Норазрешимость этой проблемы установил Черч А. (1936).

З. Проблема сочетаемости Поста. Конечное множество пар слов в некотором алфавите называется сочетаемым, если для некоторых пар

(A1,B1),…,(As,Bs) из V выполнено равенство A1…As=B1…Bs . Нужно найти алгоритм, который по всякому множеству V пар слов узнает сочетаемо оно или нет. Неразрешимость данной проблемы установил Пост Э. (1946).

4.Проблема представимости матриц. Рассматриваются ( n × n )-матрицы над кольцом целых чисел Z.Пусть даны произвольные матрицы U1,...,Uq и U .

Нужно иметь алгоритм, который бы решал, верно ли U =U i1 ...U ip для

74

задаваемый формулой

некоторых i1,...,ip .Неразрешимость данной проблемы, начиная с n=4 , установлена Марковым А.А.(1958).

5. Проблема тождества элементарных функций вещественного переменного. Определим класс термов τ индуктивно: x - переменная, π -число-

термы. Если u,v - термы, то (u + v),(uv),(u v),sinu, u - термы. Нужно иметь

алгоритм, который по любым двум термам из τ узнает, задают ли одну и туже функцию одного вещественного переменного x. Неразрешимость данной проблемы установил Матиясевич Ю.В. (1973).

6.Проблема полноты автоматных базисов. Дан набор конечных автоматов (базис) в одним множеством входов и выходами, входящими в множество входов. Строятся схемы с помощью присоединения базисного автомата и введения обратной связи. Каждая схема реализует автомат. Если схемами в данном базисе

может быть реализован любой автомат, в данном алфавите, то базис называется полным, в противном случае - неполным. Проблема полноты заключается в том, чтобы узнавать по заданному базису - является он полным или нет.

Неразрешимость данной проблемы установил Кратко М.И. (1966).

7.Десятая проблема Гильберта из 23 поставленных им в 1900 году формулируется тая: "Пусть задано диофантово уравнение (т.е. уравнение вида

p(x1,...,xn ) = 0, p - многочлен) с произвольными неизвестными и целыми

рациональными коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли уравнение в целых рациональных числах".

Неразрешимость 10-й проблемы Гильберта установлена Матиясевичем Ю.В.(1970). Учитывая важность данного результата, приведем его точнее. Пусть p(x1,...,xn , y1,..., ym ) - многочлен над кольцом целых чисел Z. Тогда

предикат M (x1,...,xn )

M (x1,..., xn ) = y1... ym ( p(x1,..., xn , y1,..., ym ) = 0)

называется диофантовым предикатом. (Область определения кванторов - множество N0 ).

Легко убедиться, что диофантовы предикаты являются полувычислимыми. Матиясевич Ю.В.в 1970 году установил:

Теорема.

Каждый полувычислимый предикат диофантов.

Покажем теперь, как из этой теоремы следует неразрешимость десятой проблемы Гильберта. Заметим, что если 10-я проблема Гильберта разрешима, то разрешима и такая проблема: "установить, имеет ли произвольное полиномиальное уравнение p(x1,...,xn ) = 0 с целыми коэффициентами решение

75

в множестве натуральных чисел”. Действительно, любое натуральное число может быть представлено как сумма четырех квадратов (по теореме Лагранжа), поэтому, чтобы решать эту проблему достаточно найти целые решения уравнения p(s12 ,t12 ,u12 ,v12 ,...,s2n ,t2n ,u2n ,v2n) = 0

Возьмем теперь многочлен p(x, y1,..., ym ) , такой,

что x W x y1,..., ym ( p(x, y1,..., ym ) = 0) ,что можно сделать по теореме Матиясевича. Тогда если бы существовала разрешающая процедура для десятой проблемы Гильберта, то существовала бы и разрешающая процедура для проблемы “ x W x ” : чтобы проверить, верно ли a W a , нужно проверить,

имеет ли решение в N0 уравнение q( y1,..., ym ) = p(a, y1,..., ym ). Значит, неразрешимая проблема “ x W x ” сводится к проблеме Гильберта, что означает

ее неразрешимость.

Укажем еще одно следствие теоремы Матиясевича. Теорема.

Всякое рекурсивно перечислимое множество является множеством неотрицательных эначенй, принимаемых некоторым многочленом p(x1,...,xn )

над кольцом целых чисел Z (причем x1,...,xn N 0 ).

Док-во.

Пусть А - рекурсивно перечислимое множество. По теореме Матиясевича существует многочлен q(x, y1,..., ym ),такой что

x A y1,..., ym (q(x, y1,..., ym ) = 0).

Рассмотрим теперь многочлен p(x, y1,..., ym ) определяемый формулой

p(x, y1,..., ym ) = x − (x +1)(q(x, y1,..., ym ))2

Ясно, что p(x, y1,..., ym ) ≥ 0 q(x, y1,..., ym ) = 0 причем в этом случае p(x, y1,..., ym )=x. Таким образом,

А есть множество неотрицательных значений, принимаемых p(x, y1,..., ym ) когда x, y1,..., ym пробегает множество N0 .

ч.т.д.

Одно на приложений этого результата - множество простых чисел. Ясно, что множество простых чисел - рекурсивно перечислимо. На основании доказанного множество простых чисел есть множество положительных значений, принимаемых некоторым многочленом с целыми коэффициентами. Данный факт считался ранее маловероятным и даже невозможным.

76