Самоорганизация и неравновесные
процессы в физике, химии и биологии
 Мысли | Доклады | Самоорганизация 
  на первую страницу НОВОСТИ | ССЫЛКИ   

Апериодические слова
от 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.


  


СТАТИСТИКА