Алгоритмы на словах

2

Алгоритмы на словах

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

Знаментийный немецкий математик Давид Гильберт в начале века предложил план доказательства непротиворечивости математики при помощи построения исчисления (то есть правило преобразования) слов. В начале тридцатых годов было выясено, что «всю математку» (и даже «всю аррифметику») виснуть в одно исчисление невозможно (это знаменита теорема Гёделя). Хотя надежды Гильберта в полном объеме не оправдались, отдельные разделы математики «форматизованы» таким путем удается, и все современные исследования по основаниям математики начинаются с подобной формализции. Во многих разделах математики (например, в математической лингвистике и общей алгебре) и ее приложения (скажем, языки программирования) слова стали одним из важнейших объектов изучения.

Теория алгоритмов родилась только в тридцатых годах нашего века. С тех пор понятие алгоритма также стало одним из важнейших в математике.

Хотя слово «алгоритм» появляется только в последнем разделе предложаемой статьи, все она посвязывана словам и алгоритмам, работаюшим со словами.

Вводный пример

Фиксируем на плоскости равносторонний треугольник ABC (рис. 1). Обозначим через R поворот плоскости на 120° против часовой стрелки вокруг центра O треугольника (рис. 2); через S обозначим осевую симметрию плоскости с осью OB (рис. 3). Каждый из преобразований R, S отображает треугольник ABC на себя. Поэтому их называют также самосовмещения исходного треугольника. Самосовмещения R и S мы будем называть элементарными.

Рассмотрим всевозможные композиции элементарных самосовмещений («Геометрия 7», п. 77). Каждая такая композиция снова, очень удобна, будет неокоторым самосовмещением.

Подобно обычным операциям сложения и умножения чисел, операция композиции самосовмещений обладает сочетательным, или ассоциативным, свойством: если f, g, h — самосовмещения, то

$$f \circ g) \circ h = f \circ (g \circ h).$$

(Это верно не только для самосовмещений треугольника, но и для произвольных отображений любого множества M в себя!) Поэтому в «длин-

Рис. 1.

ных» композициях элементарных самосовмещений скобки можно ставить в любом порядке, а значит, можно их и вообще не ставить. Например,

$$(R \circ S) \circ (R \circ R) = R \circ ((S \circ R) \circ R) = R \circ S \circ R \circ R.$$

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

3

Рис. 2.
воря, переместительный, или коммутативный, свойством. Так, в данном случае $R \circ S \neq S \circ R$ (ср. рис. 4 и 5).

Напишем наудачу какую-нибудь «длинную» композицию элементарных самосовмещений:
$$X = S \circ S \circ R \circ S \circ R \circ S \circ R \circ S \circ R.$$ (1)
Что можно сказать о самосовмещении $X$?

Легко доказать, что все существует шесть самосовмещений исходного треугольника: тождественное отображение $E$, оставляющее каждую точку плоскости на месте; поворот на $120^\circ$ против часовой стрелки; поворот на $120^\circ$ по часовой стрелке; осевые симметрии с осями $OA, OB, OC$. Из рисунков 4 и 5 видно, что осевая симметрия с осью $OA$ совпадает с композицией $S \circ R$, а осевая симметрия с осью $OC$ есть композиция $R \circ S$.

Задача. Представьте в виде композиции элементарных самосовмещений поворот на $120^\circ$ по часовой стрелке.

Рис. 3.
Итак, наша наудачу написанная композиция (1) является одним из шести перечисленных самосовмещений. Каким же именно?

Разумеется, этот вопрос легко решить чисто геометрическим: продолжайте с исходным треугольником по очереди все указаные самосовмещения (не забудьте только, что запись $f \circ g$ означает: сначала совпадает $g$, потом $f!$) и посмотрит на конечное положение треугольника.

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

Легко проверить, что
$$\begin{cases} S \circ R = R \circ R \circ S, \\ R \circ R \circ R = E, \\ S \circ S = E. \end{cases}$$

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

Поскольку нам предстоит сравнить до линная выкладка, да-

Рис. 4.
Рис. 5.

4

вайте со знаком композиции $\circ$ обходиться как с точкой при умножении: не будем этот знак писать. Равенства (1), (2) примут тогда вид

$$X = SSRSRSSR,$$

$$\begin{cases} SR = RRS, \\ RRR = E, \\ SS = E. \end{cases}$$

Композицию $X$ можно преобразовать так:

$$X = SSRSRSSR =$$

$$= (SS)R(SR)(SR)(SS)R =$$

$$= ER(RRS)(RRS)ER =$$

$$= R(RRS)(RRS)R =$$

$$= (RRR)(SR)R(SR) =$$

$$= E(RRS)R(RRS) =$$

$$= (RRS)R(RRS) = RRS(RRR)S =$$

$$= RRSES = RRSS = RR(SS) =$$

$$= RRE = RR.$$

Ассоциативные исчисления

В только что проведенной выкладке мы фактически имели дело со словами (см. первый абзац статы).

В предыдущем разделе буквы $R$ и $S$ имели смысл: они обозначали в поле не конкретные объекты — неоторные самосовмещения. Сейчас мы заимемся изучением абстрактных х букв и слов — букв и построенных из них слов, которые ничего не обозначают. (Впрочем, ниже мы еще вернемся к примеру из предыдущего раздела.)

Исходный набор букв, из которого строятся слова, называется алфавитом. Число букв в слове называют его длиной.

Пусть наш исходный алфавит состоит всего из двух букв: $\{a, b\}$. Тогда существует 4 слова длины 2: $aa, ab, ba, bb$; 8 слов длины 3 и т. д. Разрешается говорить и об «однобуквенных» словах, словах длины 1; их всего два: $a$ и $b$. Удобно считать, что существует также слова, не содержащие букв — пустое слово. Пусть слова — это аналог пустого множества. Его обозначают греческий буквой $\Lambda$. Длиной его, конечно, считают число 0.

Наши «правила игры» будут иметь такой вид:

$$\alpha \leftrightarrow \beta,$$

(5)

Рис. 6.

Рис. 7.

где $\alpha$ и $\beta$ — некоторые слова. Правило (5) означает, что в любом слове можно вместе $\alpha$ подставить слово $\beta$ и вместе $\beta$ — слово $\alpha$. Правила вида (5) называются подстановками.

Рассмотрим для примера подстановку:

$$abab \leftrightarrow bb.$$

(6)

В слова $\gamma = abababbabb$ слова $abab$ входит в трех местах (рис. 6) или, как говорят в математике, имеет три входнения. Слово $bb$ имеет в слова $\gamma$ два входнения (рис. 6). Оdnкратны м применением подстановки (6) из слова $\gamma$ можно получить 5 слов (рис. 7). К слову $abaab$ подстановка (6) неприменима: в него не входят ни левая, ни правая часть этой подстановки.

Когда мы вычисляем $(10+2) \times (8-3)) : (15-3) = (12\cdot 5):12 = 60:12 = 5$, мы, по существу, применяем подстановки $(10+2) \leftrightarrow 12, (8-3) \leftrightarrow 5, (12\cdot 5) \leftrightarrow 60$ и т. п.

Подстановка вида

$$\alpha \leftrightarrow \Lambda$$

(7)

означает, во-первых, что в любом слове вместе $\alpha$ можно «подставить пустое слово», т. е. попросту выбросить входящие слова $\alpha$. Если, например, подстановку

$$bb \leftrightarrow \Lambda$$

(8)

применить таким образом ко второму в слову $\gamma$, получится слова $abababbaba$. Подстановка вида (7)означает, во-вторых, что в любом слове между любыми двумя буквами можно «вставить» слова $\alpha$: естественно считать, что пустое слово входит между любыми буквами. Кроме того, применяем подстановку (7)«справа налево», можно,

5

конечно, «приписать» слова $\alpha$ как впереди, так и позади любого слова. Таким применением подстановки (8) можно из того же слова $\gamma$ получить 6 слов (почему?).

Чтобы задать «игру», надо фиксировать некоторые конечный набор подстановок. Такой набор (вместе с алфавитом) в математической логике называется ассоциативным исчислением.

Два слова называются смejнными в данном ассоциативном исчислении, если одно из них можно получить из другого однократным применением какой-нибудь из подстановок этого исчисления. Два слова, $\delta$ и $\eta$, называются эквивалентными в данном исчислении, если их можно «соединить» цепочкой смejнных слов, т. е. если существует такие слова $\mu_1$, $\mu_2$, …, $\mu_n$, что в цепочке $\delta$, $\mu_1$, $\mu_2$ …, $\mu_n$, $\eta$ каждое слово можно своими соседями. Эквивалентность слов $\delta$, $\eta$ мы будем обозначать так: $\delta \sim \eta$.

Разумеется, смejные слова эквивалентны.

Пример 1

Рассмотрим в алфавите $\{a, b\}$ ассоциативное исчисление с подстановками

$$\begin{cases} ba \leftrightarrow aab, \\ aaa \leftrightarrow \Lambda, \\ bb \leftrightarrow \Lambda. \end{cases}$$

Какие слова в этом исчислении эквивалентны?

Например, $aababbaaaba \sim a$, поскольку в цепочке $aababbaaaba$, $aabaaaaaba$, $aabaaba$, $aaaaaba$, $ababa, aaabba, bba, a$ каждое слово смejнено со своим соседями.

А нельзя ли указыть способ, как для любых двух слов в нашем алфавите узнавать, эквивалентны они или нет?

Сравнение равенств (4) с подстановками (9) подсказывает такой способ. Расмотрим равносторонний треугольник $ABC$ и его самосовмещения $R, S$ (с. 2).

Для любого слова $\alpha$ обозначим через $T_\alpha$ композицию элементов самосовмещений $R$ и $S$, получающегося в результате замены в слова $\alpha$ буквы $a$ на $R$ и буквы $b$ — на $S$. Например, $T_{ba} = SR$, $T_{abaa} = RSR$.

Поскольку в композиции самосовмещений тоже действенное отображение $E$ можно не писать, положим по определению $T_\Lambda = E$.

Каждая композиция элементов самосовмещений может, очевидно, быть записана в виде $T_\alpha$, где $\alpha$ — некоторое слово.

Таким образом, мы получили неокторое соответствие между множеством всех слов в алфавите $\{a, b\}$ и множеством самосовмещений. Это соответствие не является обратным: различным словам может соответствовать одно и то же самосовмещение. Например, $T_{ba} = SR = RRS = T_{aab}$ (ср. рисунки 5 и 8).

Способ, который мы хотим предложить для установления эквивалентности произвольных слов, основывается на трех «критах»:

(A) Левой и правой части каждой из подстановок исчисления соответствует мою же самосовмещение:

$$\begin{cases} T_{ba} = T_{aab}, \\ T_{aaa} = T_\Lambda, \\ T_{bb} = T_\Lambda. \end{cases}$$

Рис. 8.

6

(B) Любое слово эквивалентно в нашей исчислении одному из цесми слов: Λ, а, b, аа, ab, ааб.
(B) Любым двум из слов Λ, а, b, аа, ab, ааб соответствует разные самосовмещения.
Прежде всего установим верность утверждений (A) — (B).
Утверждение (A) вытекает из равенств (4). Утверждение (B) проверяется геометрическим: подейстуем на исходный треугольник самосовмещениями $T_\Lambda, T_a, T_b, T_{aa}, T_{ab}, T_{aab}$ и увидим, что получаются разные результаты (см. рисунки 1—3, 9, 4 и 8).
(B) доказывает последнее. Пусть $\alpha$ — произвольное слово. Применив к нему нужное число раз первую из подстановок (9), мы «перегоним» все $a$ в начало. Таким образом, слово $\alpha$ эквивалентно слову вида
$$\beta = \underbrace{aa \dots abb \dots b}_{k}$$
$(k \geqslant 0, l \geqslant 0)$. Если $l$ четно, то, применив к $\beta$ нужное число раз третью из подстановок (9), мы можем «учичтожить» в $\beta$ все $b$. В этом случае $\beta$, а значит, и $\alpha$, эквивалентно слову вида
$$\gamma' = \underbrace{aa \dots a}_{k}$$
В зависимости от остатка деления числа $k$ на 3 (он равяется 0, 1 или 2)

слово $\gamma'$ при помощи второй из подстановок (9) преобразуется в одно из слов $\Lambda, a, aa$. Если же $l$ нечетно, то $\beta$ и $\alpha$ эквивалентны слову вида
$$\gamma'' = \underbrace{aa \dots ab}_{k}.$$
В зависимости от того же остатка слова $\gamma''$ переводится в одно из слов $b, ab, aab$.
Из (A), очевидно, следует, что смежным словам соответствует одно и то же самосовмещение. Значит, это верно и для эквивалентных слов:
$$\alpha \sim \beta \Rightarrow T_\alpha = T_\beta.$$ (10)
Из (B), (B) и (10) мы получим обратное утверждение:
$$T_\alpha = T_\beta \Rightarrow \alpha \sim \beta.$$ (11)
Пусть $T_\alpha = T_\beta$. В силу (B) каждое из слов $\alpha, \beta$ эквивалентно одному из слов $\Lambda, a, b, aa, ab, aab$. Положим $\alpha \sim \alpha', \beta \sim \beta'$, где $\alpha', \beta' \in \{\Lambda, a, b, aa, ab, aab\}$. Из (10) $T_\alpha' = T_\alpha$ и $T_\beta' = T_\beta$. Учитывая $T_\alpha = T_\beta$, получаем $T_\alpha' = T_\beta'$. Тогда из (B) $\alpha' = \beta'$. Следовательно, $\alpha \sim \beta$.
Из (10) и (11) вытекает
$$\alpha \sim \beta \Leftrightarrow T_\alpha = T_\beta.$$ (12)
Просмотрите еще раз доказательство утверждения (12) и вы убедитесь, что это доказательство опирается только на (A) — (B). После того, как (A) — (B) установлены, дальнейшее обращение к подстановкам исчисления не нужно.

7

Теперь, после установки (12), мы можем наконец предложить обещанный способ: путь надо испать на эквивалентность слова $\alpha$ и $\beta$; подействуйте на треугольник $ABC$ самосовмещениями $T_{\alpha}$ и $T_{\beta}$; если получите одинаковый результат, то $T_{\alpha} = T_{\beta}$ и, значит, в силу (12) $\alpha$ и $\beta$ эквивалентны; в противном случае, опять в силу (12) они не эквивалентны.

Пример 2

Рассмотрим теперь в том же алфавите $\{a, b\}$ ассоциативное ичисление с подстановками:

$$\begin{cases} ab \leftrightarrow ba, \\ aa \leftrightarrow \Lambda, \\ bb \leftrightarrow \Lambda. \end{cases}$$

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

Первый способ

Данный способ аналогичен способу из примера 1. Фиксируем на плоскости какой-нибудь прямогольник $ABCD$ (рис. 10). Обозначим через $S_1$ осевую симметрию плоскости с осью $OM$, проходящей через центр симметрини прямогольника $O$ параллельно стороне $AB$ (рис. 11); через $S_2$ обозначим осевую симметрию с осью $ON$ (рис. 12). Обе эти симметрия являются самосовмещениями исходного прямогольника. Самосовмещения $S_1$ и $S_2$ мы будем называть элементарными.

Как и в примере 1, рассмотрим всевозможные композиции элементарных самосовмещений.

На этот раз самосовмещение $T_{\alpha}$ мы будем получить из слова $\alpha$ заменой буквы $a$ на $S_1$, буквы $b$ — на $S_2$.

Опять выполняются три «кита»:

(A) Левой и правой части каждой из подстановок ичисления соответствует применению (13) подстановки (13), найдите этаонные слова, эквивалентные словам $\alpha$ и $\beta$ (как это делается, рассказано при доказательстве (B) из примера 1); если $\alpha$ и $\beta$ окажутся эквивалентными одному и тому же этаонному слову, то $\alpha \sim \beta$; в противном случае $\alpha$ и $\beta$ не эквивалентны.

На языке статьи А. Толыго «Инварианты» («Квант», 1976, № 12) второй способ может быть изложен так: для любого слова

$$\begin{cases} T_{ab} = T_{ba}, \\ T_{aa} = T_{\Lambda}, \\ T_{bb} = T_{\Lambda}. \end{cases}$$

(B) Любое слово эквивалентно в нашем исчислении одному из четырех слов: $\Lambda$, $a$, $b$, $ab$.

(B) Любим двум из слов $\Lambda$, $a$, $b$, $ab$ соответствует соответствующим разные самосовмещения.

Из (A) — (B), как и выше, выводится

$$\alpha \sim \beta \iff T_{\alpha} = T_{\beta}.$$

Значит, эквивалентность произвольных слов $\alpha$, $\beta$ устанавливается, как в примере 1: подействуйте на прямогольник $ABCD$ преобразованиями $T_{\alpha}$ и $T_{\beta}$; если получим одинаковый результат, то $\alpha \sim \beta$; иначе $\alpha$ и $\beta$ не эквивалентны.

Второй способ

Присмотревшись к подстановкам (13), можно подметить, что они сохраняют одному из эмалонных слов $\Lambda$, $a$, $b$, $ab$.

Поскольку у любых двух этаонных слов либо четности числа буква $a$, либо четности числа буква $b$ различны (см. рис. 13), эмалонные слова попарно не эквивалентны.

Следовательно, эквивалентность произвольных слов $\alpha$, $\beta$ расположется просто: применения подстановки (13), найдите этаонные слова, эквивалентные словам $\alpha$ и $\beta$ (как это делается, рассказано при доказательстве (B) из примера 1); если $\alpha$ и $\beta$ окажутся эквивалентными одному и тому же этаонному слову, то $\alpha \sim \beta$; в противном случае $\alpha$ и $\beta$ не эквивалентны.

На языке статьи А. Толыго «Инварианты» («Квант», 1976, № 12) второй способ может быть изложен так: для любого слова

8

α положим

$$f_1(\alpha) = \begin{cases} 0, если число букв a в слова α четно, 1 в противном случае; \end{cases}$$

$$f_2(\alpha) = \begin{cases} 0, если число букв b в слова α четно, 1 в противном случае. \end{cases}$$

Функции $f_1, f_2$ образуют полную систему инвариантов. Поэтому эквивалентность произвольных слов α, β распознается так: посчитайте значения функций $f_1$ и $f_2$ на α и β; если равенства

$$\begin{cases} f_1(\alpha) = f_1(\beta), f_2(\alpha) = f_2(\beta) \end{cases}$$

будут выполнены, α~β; в противном случае α и β не эквивалентны.

Попробуйте решить задачу из примера 1 вторым способом, т. е. при помощи инвариантов. Это намного труднее, чем в примере 2.

Алгоритм существует не всегда

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

В 1946 и 1947 годах советский математик Андрей Андреевич Марков и американский математик Эмиль Пост независимо построили ассоциативные ичисления, для которых также способа не существует.

До сих пор в нашей стране мы избегали слова «алгоритм». В математике алгоритм называют точное представление для решения неокоторого класса задач. Эту фразу ни в коем случае нельзя рассматривать как определенное понятие алгоритма — ведь слова «точное представление» не являются каким-то математическим термином, не имеют однозначного смысла.

До тех пор, пока математики занимались построением конкретных алгоритмов, они обходились тем рассыпчатым описанием этого понятия, которое дано выше. Но в первые десятилетия XX века накопилось много классов задач, для которых алгоритма найти не удалось. Математики начали подозревать, что дело не в недостатке у них смекалки. Им пришла в голову мысль: а вдруг для того или иного класса задач просто не во змю же на ней алгоритм? А если его просто не существует?

Для того чтобы доказать, что алгоритма не существует, уже недостаточно распливчатого понятия, надо это понятие уточнить. Такое уточнение и было проделано в середине тридцатьх годов нашего века *).

Лишь после этого уточнения стало в принципие возможного доказывать несуществование алгоритма. Первое доказательство такого рода дал американский логик Алонзо Черч.

Исчисления, построенные А. А. Марковым и Э. Постом, были весом громоздки: они содержали сотни подстановок. Математики стали искать более простые примеры ассоциативных ичислений с неразрешимой проблемой эквивалентности. В этом направленииrekord поставил Григорий Самуилович Цейтин: он построил такое ичисление всего с 7 подстановками **).

Цейтин доказал, что для ичисления в алфавите {a, b, c, d, e} с подстановками

$$\begin{cases} ac \leftrightarrow ca, ad \leftrightarrow da, bc \leftrightarrow cb, bd \leftrightarrow db, eca \leftrightarrow ae, edb \leftrightarrow be, abac \leftrightarrow abace \end{cases}$$

alгоритма распознавания эквивалентности слов не существует.

Интересно, что ичисления с разрешимой и ичислением с неразрешимой проблемой эквивалентности «лежат рядом». В брошюре Б. А. Трахтенброта «Алгоритмы и машинное решение задач» (Москва, Физматгиз, 1960) и ичисление Цейтина было приведено *)

*) Об этом можно прочесть в §§ 7, 13 брошюры Б. А. Трахтенброта «Алгоритмы и вычислительные автоматы» (Москва, «Советское радио», 1974) и на с. 9—13 книги «Машины Тыbiorинга и рекурсивные функции» (Москва, «Мир», 1972).

**) Егоrekord воспользовали перекрыл Юрий Владимирович Матиясевич, построивший такое ичисление с трея подстановками. К сожалению, они слишком длины, чтобы их здесь привести.