Апериодические слова от 12.07.06		Мысли
Придайте человеку такие размеры, чтобы то небо, на которое мы смотрим, помещалось бы на одном полушарии его кровяного шарика. Он будет велик. И все же его спутником будут все те же числа, которые знаем и мы, так как ряд чисел не меняется от выбора единицы Велимiр Хлъбников. Есть закон неизменности чисел Последовательнсть Морса-Туэ Не будет преувеличением сказать, что эта последовательность нулей и единиц столь же - всепроникающа и вездесуща -, как число пи. Еще в 1906г. норвежский математик Аксель Туэ привел эту последовательность в качестве примера апериодической рекурсивно вычислимой строки символов, а американский математик Марстон Морс обнаружил ту же последовательность при  изучении некоторых нелинейных систем методом символической динамики в 1921 г. Построение последовательнсти Морса-Туэ начинается с нуля. На каждом следующем шаге к набору нулей и единиц, уже имеющемуся на предыдущем шаге, справа приписывается его дополнение - набор знаков, в котором каждый нуль заменен единицей, а каждая единица заменена нулем - 1 шаг - 0 - 2 шаг - 01 - 3 шаг - 0110 - 4 шаг - 01101001 - 5 шаг - 0110100110010110 - 6 шаг - 01101001100101101001011001101001 - и т.д. - В пределе мы, следуя принципу - скопируйте предыдущий член последовательности и припишите справа его дополнение -, проистекающему из простого правила замены символов 0 --> 01, 1 --> 10, получаем последовательность Морса-Туэ. Последовательность Морса-Туэ обладает свойством самоподобия - содержит фрагменты, которые при надлежащем - растяжении - воспроизводят всю последовательность. В качестве примера рассмотрим шестой шаг построения. Начав с первого члена, выберем каждый второй член последовательности. Нетрудно заметить, что выбранные члены образуют последовательность Морса-Туэ 0110100110010110. Последовательность Морса-Туэ можно получить не только по правилу - скопируйте и припишите справа дополнение -, но и следующим образом. Рассмотрим все целые неотрицательные числа. Запишем эти числа в двоичной системе. Заменим каждое двоичное число остатком от деления суммы его двоичных цифр на 2 (так называемым - цифровым корнем по модулю 2) 0    1    2    3    4    5    6    7    - десятичные цифры 0   1   10   11 100 101 110 111 - двоичные цифры 0    1    1    2    1    2    2   3   - сумма двоичных чисел 0    1    1    0    1    0    0   1   - цифровой корень по модулю 2 Цифровые корни по модулю 2 образуют последовательность Морса-Туэ Ю.А. Данилов. Из лекций по нелинейной динамике http://sinsam.kirsoft.com.ru/KSNews_145.htm 3. Апериодические слова В дальнейшем нам понадобится бесконечная последовательность из двух символов 1 и 2 t1, t2, t3, ...ti, ti+1,... для которой при любом i в слово t1t2...ti не входит никакое непустое подслово вида Е3. 3.1. Рассмотрим всевозможные перестановки из трех цифр 1, 2 и 3 1 2 3,   3 2 1, 2 3 1,   1 3 2, 3 1 2,   2 1 3. Перестановки из левой колонки назовем нечетными, а перестановки из правой колонки - четными. Нечетные перестановки занумерованы своими первыми элементами, а четные - последними. Каждая четная перестановка есть зеркальное отражение нечетной перестановки с тем же номером. Индукцией по i построим слова Аi при любых натуральных i > 0. Положим А1 = 1. Если слово Аi уже пострено и Аi = h1h2...hr, то через Аi+1 обозначим результат замещения в Аi каждой цифры hj четной или нечетной перестановкой с номером hj в зависимости от четности числа j. Выпишем несколько первых слов Аi А2 = 123, А3 = 123 132 312, А3 = 123 132 312 321 312 132 312 321 231, и т.д. Здесь мы выделили тройки цифр для того, чтобы легче было обозревать все слово. Очевидно, каждое Аi есть начало слова Аi+1. 3.2. В слово Аi при i > 0 не входит никакое непустое слово вида ЕЕ. (Доказывается индукцией по i) 3.3. Пусть v(1) -->12, v(2) --> 121, v(3) --> 1221. Для любого слова Х в алфавите {1, 2, 3} через v(Х) обозначим результат замещения в Х каждой цифры i словом v(i). Эти слова v(i) будем называть компонентами слова v(Х). Очевидно, каждаяч компонента начинается словом 12. С другой стороны, слово 12 может входить в v(Х) только как начало некоторой компоненты... 3.4. В слово v(Аi) не входит никакое непустое подслово вида ЕЕЕ. ... 3.5. Так как при каждом i > 0 слово v(Аi) есть начало слова v(Аi+1) то, достраивая последовательность слова v(Аi) до v(Аi+1), мы получим искомую последовательность t1, t2, t3, ...ti, ti+1,... где при любом i в слово в слово t1t2...ti не входит никакое непустое подслово вида Е3 С.И. Адян. Проблема Бернсайда и тождество в группах Говорят, что слово X входит в слово А, если можно указать такие слова R и Q, что А = RXQ. Если при этом слово R (слово Q) пусто, то говорят, что X есть начало (конец) слова А. Слово А будем называть n-апериодическим, если в него не входит никакое непустое слово вида Хn, т.е. А не равно R(ХХ…Х)nQ. Таким образом, если слово А = R(ХХ…Х)nQ , то А сокращается на Хn и А --> A = RQ. Далее, если А включает в себя какое-либо непустое слово вида Хn, то опять сокращается на Хn. Этот процесс будет продолжаться до тех пор, пока в слове А не будет содержаться ни одного вхождения типа Хn.