A08DPPMAT_UPS2006D00

Полутуэвские процессы. Пусть A a, b, c . . . — некоторый алфавит и X — множество всех слов в этом алфавите. Рассмотрим операцию умножения слов, которая определена следующим образом. Пусть u, v X, причем u a1 . . . am, v b1 . . . bn. Тогда

uv a1 . . . amb1 . . . bn.

Тем самым произведение u v получается выписыванием вначале букв слова u, а затем букв слова v. Ясно, что u v также слово в алфавите A . Поэтому произведение uv содержится X. Например, при A a, b, c, d , u abd, v aca получим u v abdaca X.

Итак, мы имеем бинарную алгебраическую операцию на множестве X. Напомним, что множество с некоторым набором алгебраических операций называется алгеброй. Поэтому мы имеем алгебру X, .

ТЕОРЕМА 12.3 . Алгебра X, является полугруппой с единичным элементом Λ.

Доказательство. Напомним, что полугруппа — это множество, на котором определена ассоциативная алгебраическая операция. Поэтому нужно проверить ассоциативность операции . Пусть u, v, w — элементы

из X, т.е. слова в алфавите A , u a1 . . . ak, v b1 . . . bl, w c1 . . . cm. При записи произведения u v будем обычно опускать знак операции. То-

гда

uv	a1 . . . ak b1 . . . bl, uv w	a1 . . . ak b1 . . . blc1 . . . cm.
vw	b1 . . . blc1 . . . cm, u vw	a1 . . . akb1 . . . blc1 . . . cm.

Получили uv w u vw , т.е. операция ассоциативна.

Полугруппа X, называется полугруппой с единицей, если в ней существует единичный элемент относительно операции . Проверим, что пустое слово Λ является единичным элементом. Имеем uΛ u, т.к. при приписывании справа к слову u пустого слова Λ получаем u. Аналогично, Λu u. Итак, Λ — единичный элемент.

Теорема доказана.

Слова в некотором алфавите представляют собой наиболее простые объекты, а замена в них подслов на другие слово — простейшие действия над объектами. Такие прозрачные конструкции уже приводят к алгоритмически неразрешимым проблемам.

121

ОПРЕДЕЛЕНИЕ 12.1. Полутуэвской продукцией над A (или просто продукцией) называется упорядоченная пара u, v , где u и v являются словами в алфавите A .

Такую продукцию будем записывать также в виде u v. Она предназначена для замены в произвольных словах подслова u на слово v и поэтому аналогична формуле подстановки в нормальном алгорифме.

ОПРЕДЕЛЕНИЕ 12.2 . Полутуэвским процессом Π над алфавитом A называется всякое конечное непустое множество полутуэвских продукций над A.

Поэтому

Πu, v , u , v , . . . .

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

Пусть u v — некоторая полутуэвская продукция из Π. Будем использовать ее для замены произвольного вхождения u в слове P на слово v. Если в результате такой замены из слова P получено слово Q, то записываем P Π Q. Если имеем несколько последовательно выполненных замен

P Π P1, P1 Π P2, . . . , Pn 1 Π Pn,

и в результате получаем Pn Q, то записываем этот факт в виде

P Q.

Π

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

Требуется найти алгоритм, с помощью которого для произволь-

ных слов P, Q X можно определить, верно ли, что P Q, или

Π

нет.

Как и в любой проблеме разрешимости, такой алгоритм должен быть представлен или доказано его несуществование.

ТЕОРЕМА 12.4 . Существует полутуэвская система, проблема слов для которой неразрешима.

Доказательство этого утверждения достаточно сложно и поэтому опускается. Наметим лишь основные идеи.

122

Алгоритмическая сводимость. Доказательство несуществования алгоритма A наиболее часто проводится одним из двух следующих методов.

1)Диагональный метод. Рассматривается какое-либо построение, связанное с диагональю в некоторой таблице. Такой метод использовался, например, в теореме (9.2) для доказательства несуществования универсальной функции для класса вычислимых, всюду определенных функций.

2)Метод сведения. Пусть нужно доказать неразрешимость некоторой проблемы B. Предположим, что мы уже знаем, что некоторая другая проблема A неразрешима. Мы можем попытаться доказать следующее утверждение.

Если проблема B разрешима, то и проблема A разрешима.

Если такое утверждение получено, то заведомо зная, что проблема A неразрешима, мы делаем вывод о неразрешимости и проблемы B.

Внашем случае можно установить, что для всякой машины Тьюринга M можно построить соответствующую полутуэвскую систему Π M , такую, что алгоритм для решения проблемы слов для Π M может быть также использован для решения проблемы остановки для M . Однако проблема остановки машины Тьюринга алгоритмически неразрешима. Из неразрешимости проблемы A (проблемы остановки) получаем неразрешимость проблемы B (проблемы слов для полутуэвской системы Π M ).

Всвязи с этим возникает вопрос: нельзя ли неразрешимость всякой неразрешимой проблемы установить сведением к «стандартной неразрешимой проблеме»? Проблема сводимости была решена независимо А.А.Мучником и Р.М.Фридбергом. Показано, что никакая неразрешимая проблема не может служить «стандартной неразрешимой проблемой». Тем самым нельзя доказательство неразрешимости любой неразрешимой проблемы свести к доказательству неразрешимости этой стандартной проблемы.

Алгоритмические проблемы в полугруппах. Рассмотрим теперь

частный случай полутуэвского процесса. Обратной к полутуэвской продукции u v является продукция v u.

ОПРЕДЕЛЕНИЕ 12.3 . Полутуэвский процесс Π называется туэвским процессом, если для каждой продукции u v обратная продукция v u также находится в Π.

123

Для туэвского процесса Π вместо P Q записываем P $ Q.

Π

ТЕОРЕМА 12.5 . Для любого туэвского процесса Π отношение P $ Q является отношением эквивалентности.

Доказательство. Для

любого

полутуэвского

процесса отношение

P

Q очевидно, рефлексивно и транзитивно. Осталось проверить, что

Π

Q влечет Q

P для туэвского процесса.

P

Π

Π

Из P Q имеем P

Π

P

, P

1

Π

P

, . . . , P

1

Π

P

, где P

n

Q.

Π

1

2

n

n

Тогда имеем P

n

Π

P

, . . . , P

1

Π

P , т.е. Q P , что и надо.

n

1

Π

Теорема доказана.

Так как отношение $ является отношением эквивалентности, то можно рассмотреть классы эквивалентных элементов.

Класс эквивалентности, содержащий u, будем обозначать через u¯. Напомним определение отношения конгруэнтности и его свойства.

ОПРЕДЕЛЕНИЕ 12.4. Пусть A, — алгебра с бинарной операцией . Отношение эквивалентности $ на алгебре A, называется отношением конгруэнтности, если

%a, b, c A a $ b ac $ bc и ca $ cb.

(12.2)

Другими словами, при умножении эквивалентных элементов a и b справа на произвольный элемент c должны получаться эквивалентные элементы. То же при умножении слева.

Правило умножения классов. Пусть отношение $ является отношением эквивалентности на алгебре A, и x, y, z, . . . — множество всех классов эквивалентных элементов. Определим операцию умножения классов следующим правилом. Выберем в классе x произвольный элемент a — представитель класса, в классе y выберем представитель b. Вычислим произведение ab элементов a и b в алгебре A. Класс z, содержащий элемент ab, считаем произведением классов x и y.

124

	Итак, правило умножения классов имеет вид.
				Если a x, b y, то произведение xy				(12.3)
				есть класс, содержащий элемент ab.
	Если x		, y		, то по (12.3) получаем
				b
		a
								(12.4)
					xy	ab.
	То же самое в другой записи
	¯ ¯							(12.5)
						ab.
					a b

ТЕОРЕМА 12.6. Если $ является отношением конгруэнтности на алгебре A, то произведение xy в (12.4) не зависит от выбора представителей a и b в классах x и y.

Доказательство в [12, с.33].

ТЕОРЕМА 12.7 . Отношение $ является отношением конгруэнтности на алгебре X.

Доказательство. Проверим условие конгруэнтности. Пусть

aa1 . . . ak, b b1 . . . bl, c c1 . . . cn.

Самостоятельно проверить, что ac $ bc и ca $ cb. Теорема доказана.

Обозначим через S алгебру классов для отношения конгруэнтности $.

ТЕОРЕМА 12.8 . Алгебра классов для отношения конгруэнтности $ является полугруппой.

Доказательство в упражнениях к лекции.

Если полугруппа S определена таким путем, то туэвский процесс Π называется представлением полугруппы S. Пары u, v для продукций

uv называются соотношениями, а символы из A называются образующими представления. Вместо двух пар u v и v u записываем

u# v.

125

Как и в случае полутуэвского процесса, имеем следующую проблему разрешимости. Требуется найти алгоритм, с помощью которого для произвольных элементов x и y полугруппы S можно определить, верно ли, что x y или нет.

ТЕОРЕМА 12.9. (Э.Пост, А.А. Марков).Существует представление полугруппы с неразрешимой проблемой слов.

Первоначальные конструкции Поста и Маркова являются достаточно громоздкими, с сотнями подстановок. Приведем более простой пример полугруппы с неразрешимой проблемой слов, полученный Г.С.Цейтиным и содержащий всего 7 подстановок.

В этом примере задан алфавит A a, b, c, d, e и подстановки

ac # ca

ad # da

bc # cb

bd # db

eca # ce

edb # de

cca # ccae

Рассмотренные проблемы слов были впервые предложены А. Туэ задолго до появления точного определения понятия алгоритма. Это исторически первый пример проблемы разрешимости, формулировка которой не относилась к логике.

Мы рассмотрели алгоритмические проблемы в полугруппах. Аналогичные вопросы, относящиеся к группам, будут рассмотрены в упражнениях.

126

Упражнения к лекции 12

ЗАДАЧА 1. Пусть A a — алфавит, состоящий из одной буквы. Зададим полугруппу S туэвским процессом в алфавите A a и соотношением

aa # Λ.

Показать, что в этом случае существует алгоритм для определения равенство слов в полугруппе S.

ЗАДАЧА 2. Зададим полугруппу S туэвским процессом в двубуквенном алфавите A a, b и соотношениями

ab # ba

aa# Λ

bb# Λ

Показать, что в этом случае существует алгоритм для определения равенства слов в полугруппе S.

Пусть отношение $ является отношением конгруэнтности на алгебреA, и K x, y, z, . . . — множество всех классов эквивалентных элементов. Рассмотрим операцию умножения классов

¯ ¯		(12.6)
a b	ab.

ЗАДАЧА 3. а) Пусть A — алгебра с коммутативной ассоциативной алгебраической операцией и $ является отношением конгруэнтности на алгебре A. Тогда произведение классов коммутативно ассоциативно .

б) Пусть алгебра A имеет единичный элемент e. Тогда e¯ — единичный элемент при умножении классов.

Пусть	A — алфавит,	состоящий из			букв	x1, x2, . . . , xn и	букв
x 1, x 1, . . . , x 1. Символы x			i	и x 1 в дальнейшем будут перемножаться
1 2	n			i
особым образом, а пока это просто буквы. Итак,
	A x1	, x2, . . . , xn, x 1, x 1, . . . , x 1 .					(12.7)
				1	2	n
Любой символ из A будем записывать в виде xiε, где 1 i n и ε							&1.

127

Пусть X — множество всех слов в алфавите A . Рассмотрим обычное произведение слов. Если u, v X, то uv — слово, полученное из сло-

ва u справа слова v. Например, для u

x

x 1 и u

x

x

x

1

имеем

x 1x

1

2

2

3

u

x

x

x

. Имеем алгебру X, с операцией (умножением слов).

1

2

2

3

1

Введем отношение $ на множестве X. Сотрем или добавим в любом из

слов u и v два рядом стоящих символа вида x

i

и x 1 или x 1 и x

. Если из

i

i

i

слова u несколькими такими действиями получим v, то записываем u $ v.

ЗАДАЧА 4. Доказать, что отношение $ на множестве X является отношением эквивалентности.

Класс эквивалентных элементов, содержащий слово u X будем обозначать через u . Множество всех классов для отношения $ обозначим через G. Поэтому

G u u X .

(12.8)

ЗАДАЧА 5. Доказать, что отношение $ на множестве X является отношением конгруэнтности на алгебре X, .

Поскольку отношение $ на множестве X является отношением конгруэнтности на алгебре X, , то можно задать обычным способом произведение классов для данного отношения конгруэнтности: u v uv .

ЗАДАЧА 6. Множество G является группой относительно данной операции произведения классов.

Группа G называется свободной группой с n образующими.

ЗАДАЧА 7. Является ли свободная группа G абелевой, конечной? Описать единичный элемент из G, обратный элемент для элемента u .

Теперь получим аналогичным приемом новую группу G1. В случае свободной группы мы считали равными слова, которые отличаются на со-

множители вида x	x 1	или x 1x		.
i	i	i	i

Теперь вместо данных слов рассмотрим множество R, состоящее из произвольного набора слов в алфавите A . Это множество R назовем системой определяющих соотношений. В группе G рассмотрим наименьший

128

нормальный делитель H, содержащий множество R. Он получится при перемножении соотношений из R, замене r R на обратный элемент и добавлении сопряженных элементов x 1rx, x G.

Введем отношение на множестве X. Сотрем или добавим в любом из слов подслово w H. Если из слова u несколькими такими действиями получим v, то записываем u ' v.

ЗАДАЧА 8. Доказать, что отношение ' на множестве X является отношением эквивалентности.

Класс эквивалентных элементов, содержащий слово u X, будем снова обозначать через u . Множество всех классов для отношения ' обозначим через G1.

ЗАДАЧА 9. Доказать, что отношение ' на множестве X является отношением конгруэнтности на алгебре X, .

Поскольку отношение ' на множестве X является отношением конгруэнтности на алгебре X, , то можно задать обычным способом произведение классов для данного отношения конгруэнтности: u v uv .

ЗАДАЧА 10. Множество G1 является группой относительно данной операции произведения классов.

Группа G1 называется группой с n образующими и системой определяющих соотношений R.

Нам хотелось бы иметь алгоритм, который по системе определяющих соотношений R выявляет, равны или нет два элемента группы G1.

Академиком П.С.Новиковым в 1952 г. показано, что данная проблема алгоритмически неразрешима.

П.С.Новиков доказал также алгоритмическую неразрешимость проблемы изоморфизма групп. Эта проблема состоит в указании алгоритма для распознавания, изоморфны или нет две группы.

129

Лекция 13. Разрешимые множества и предикаты

В данной лекции будет подробно рассмотрено понятие разрешимого множества, введенное в лекции 11.

Напомним, что подмножество A множества E называется разрешимым в E, если существует алгоритм A, определяющий для элементов x E, принадлежит элемент x множеству A или нет.

Поэтому, чтобы установить разрешимость множества A в E, нужно найти алгоритм A, на входе которого предъявляются элементы x E. При этом выполнены следующие два условия:

1)если на входе алгоритма предъявлен элемент x A, то на выходе должен быть ответ «да»;

2)если на входе алгоритма имеется элемент x E A, то на выходе должен быть ответ «нет». Разумеется, нужна договоренность, что подразумевать под ответами «да» и «нет». Например, выработка выходного объекта 1 означает «да», а выработка 0 означает «нет».

Если такой алгоритм существует, то он называется разрешающим методом для A в E. Если E — множество натуральных чисел, то вместо слов «множество A разрешимо в E» говорим «множество A разрешимо».

Задача нахождения алгоритма A или доказательства его несуществования названа в лекции 11 проблемой разрешимости для A. При этом нужно получить конструктивный ответ на проблему разрешимости, т.е. или

1)построить искомый алгоритм, т.е. указать его инструкции; или

2)доказать, что такого алгоритма не существует.

Следующее «доказательство разрешимости» множества A неконструктивно и не дает ответа вида 1) или 2). Пусть A — множество тех чисел n N, для которых в десятичной дроби числа π есть не менее n девяток подряд. Тогда A разрешимо. В самом деле, выполнено одно из утверждений: а) в числе π для любого n N найдется не менее n девяток подряд, т.е. A N ; либо б) есть не менее n девяток подряд до некоторого значения n, например n 5, но нет n девяток подряд для n 1, n 2, . . . .

В случае а) A N и A— разрешимо. В случае б) множество A конечно

ипредложению 13.1 этой лекции также разрешимо.

Итак, в обоих случаях A разрешимо. Тем не менее, мы так и не предъявили инструкций алгоритма, который по n определял бы, есть ли в десятичной дроби числа π не менее n девяток подряд.

130