Упражнения

1. Каково число подслов слова до длины я, не содержащего более одного вхождения каждой буквы? Как можно точнее укажите верхнюю границу для числа подслов в общем случае, когда не все буквы слова до различны.
2. Рассмотрим DOL-систему G = ({a, b), h, a), где h(a) = b и h(b) = ab. Покажите, что длины слов в последовательности S(G) образуют последовательность Фибоначчи.
3. Изменив данное в тексте определение, назовем слово или ω-слово сильно бескубным, если оно не содержит подслов вида bx², где b - последняя буква слова x. Покажите, что при этом теорема 1.9 остается в силе. (Чтобы установить этот результат, нет необходимости просматривать все доказательство теоремы 1.9.)
4. Назовем примитивным корнем ρ(w) слова w из ∑* кратчайшее слово и, такое, что w = uⁿ для некоторого n≥1. Убедитесь в единственности слова ρ(w). Докажите, что "до = дои тогда и только тогда, когда ρ(u) = ρ(w). Сравните этот результат с леммой 1.10.
5. Докажите, что из равенства u^mvⁿ = w^p, где m, n, p≥2, следует, что ρ(u) = ρ(v) = ρ(w). (Этот результат содержится в [LyS].) Конструкция Туэ применима во многих ситуациях, возникающих в самых разных областях математики; типичный пример - ее использование для доказательства существования непериодических рекуррентных траекторий в динамике (см. [MoH1]). Общим моментом в таких ситуациях, по-видимому, оказывается необходимость создать нечто нерегулярное из нескольких заданных элементов. Дальнейшие примеры будут приведены в упр. 6-8.
6. Среди обычных правил игры в шахматы есть правила о ничьей, утверждающие, в частности, что каждая игра должна содержать лишь конечное число ходов. Предлагались различные модификации этих правил о ничьей, и одна из них состояла в следующем. Множество пешек и фигур на доске перед ходом образует конфигурацию, причем возможно лишь конечное число различных конфигураций. (Ясно, что конфигурация содержит также информацию о том, чей сейчас ход.) Ничья объявляется в том случае, когда некоторая последовательность конфигураций повторилась два раза подряд. (При этом опускается обычное правило о том, что после некоторого числа ходов должна быть сдвинута пешка или взята фигура.) Покажите, что при таких правилах о ничьей возможна бесконечная игра. Ограничьтесь рассмотрением лишь таких конфигураций, в которых у каждого игрока остался только король.
7. Элемент z называется нулем полугруппы S, если для каждого элемента а полугруппы S имеет место za = az = z. Полугруппа S называется нильпотентной, если существует такое натуральное k, что S^k = {z}. Постройте порожденную тремя элементами полугруппу S, не являющуюся нильпотентной и такую, что квадрат каждого элемента S равен нулю.
8. Покажите, что существуют конечно-порожденные бесконечные группы, в которых каждый элемент имеет конечный порядок, являющийся делителем некоторого фиксированного числа n (см. [H]). (Фактически последовательность Туэ используется лишь в одной части доказательства.)¹.
9. Рассмотрим идемпотентную полугруппу (т. е. такую, в которой для каждого элемента а имеет место a² = a). Докажите, что каждая конечно-порожденная идемпотеитная полугруппа является полугруппой конечного порядка (см. |[Mc]). Сопоставьте этот результат с упр. 7 и 8.
10. Рассмотрите ω-слово a₀a₁a₂ ... над алфавитом {a, b}, определенное следующим образом: a_n = a (соответственно a_n = b), если в двоичной записи числа n имеется четное (соответственно нечетное) число единиц. Докажите, что это ω-слово равно ω-слову из теоремы 1.5.
11. Рассмотрим "дважды бесконечные" слова
    ...c_-2c_-1c₀c₁c₂... .
    Приведите пример бесквадратного дважды бесконечного слова над алфавитом {a, b, c) и сильно бескубного дважды бесконечного слова над алфавитом {a, b).
12. Порождается ли ω-слово у из теоремы 1.8 какой-либо DOL-системой? (Напомним, что у получено применением сохраняющего длину гомоморфизма к ω-слову β, порожденному некоторой DOL-системой. Будем говорить, что ω-слово, построенное таким способом, порождается CDOL-системой.)
13. Рассмотрим алфавит ∑ = {0, 1, 2} и отображения f₁ и f₂ алфавита ∑ в ∑³, заданные равенствами
    f₁(0) = 012, f₁ (1) = 120, f₁(2) = 201, f₂(0) = 210, f₂ (1) = 021, f₂(2) = 102.
    Расширим область определения f₁ и f₂ на ∑*, полагая для всех a из ∑ и w из ∑*
    f₁ (λ) = f₂(λ) = λ.
    f₁ (aw) = f₁(a) f₂(w), f₂ (aw) = f₂ (a)f₁ (w).
    Покажите, что последовательность {fⁱ₁ (0), i = 0, 1, 2, ...} определяет бесквадратное ω-слово. Покажите также, что это ω-слово не порождается никакой CDOL-системой (см. [Be2]).
14. ω-язык, порождаемый DOL-системой (∑, h, w), состоит из всех ω-слов δ, таких, что δ порождается некоторой DOL-системой
    (∑, hⁱ, h^j(w)), i≥1, j≥0.
    Рассмотрим DOL-систему G из упр. 2. Покажите, что, хотя сама G не порождает никакого ω-слова, ω-язык системы G состоит из двух ω-слов, ни одно из которых не является бескубным. Содержат ли эти ω-слова подслова вида x*, где x - непустое слово?
15. Предположим, что проблема равенства ω-слов, порождаемых двумя заданными DOL-системами, удовлетворяющими дополнительному условию о порождении ω-слов, разрешима. (В действительности эта проблема остается пока открытой².) Покажите, что при этом предположении проблема равенства ω-языков, порождаемых двумя DOL-системами, также разрешима. (Здесь очень полезен результат, установленный в |Li3], в соответствии с которым проблема пустоты ω-языка, порожденного DOL-системой, разрешима.)
16. DOL-система G называется локально-катенативной, если ее последовательность
    S(G): w₀, w₁, w₂, ...
    удовлетворяет следующему условию. Существуют положительные целые числа t, i₁, ..., i_t, такие, что равенство
    w_n = w_n-i1 ... w_n-it
    выполняется для всех достаточно больших n. (Например, DOL-система из упр. 2 локально-катенативна, если
    w_n = w_n-2w_n-1.)
    Докажите, что w-язык, порождаемый локально-катенативной DOL-системой, всегда непуст и что проблема равенства со-языков, порождаемых двумя локально-катенативными DOL-системами, разрешима.

¹ (Эта задача является знаменитой ("большой") проблемой Бернсайда, решенной П. С. Новиковым и С. И. Адяном (см. послесловие).- Прим. перев.)

² (Разрешимость этой проблемы и решение задачи 15 указываются в недавно опубликованной статье [CuH*]. (Здесь и далее звездочкой отмечены работы, включенные в составленный при переводе список дополнительной литературы.) В статье [CuS3*] доказывается, что из разрешимости этих проблем следует разрешимость обычной проблемы последовательностной эквивалентности для DOL-систем, а также решается ряд других задач для DOL-систем (см. гл. 5 книги) и для их обобщений DTOL-. систем. - Прим. перев.)