Последовательность Морса

Последовательность Морса — Туэ — бесконечная последовательность нулей и единиц (битов), впервые предложенная в 1906 году норвежским математиком Акселем Туэ в качестве примера апериодической рекурсивно вычислимой строки символов. Существует два варианта последовательности, получающиеся друг из друга инверсией битов:

10010110011010010110100110010110… (последовательность A010059 в OEIS)

01101001100101101001011001101001… (последовательность A010060 в OEIS)

Последовательность Морса — Туэ является простейшим примером фрактала и находит свое применение в алгоритмах фрактального сжатия изображений.

Определения

Последовательность можно определить многими разными эквивалентными способами:

• Выполняя преобразование $0 \rightarrow 01$ ; $1 \rightarrow 10$, взяв за первую итерацию $1$:

        1
    1       0
  1   0   0   1
 1 0 0 1 0 1 1 0 

• Каждым шагом (начиная с 1) дописывая число, дополняющее уже написанное до числа, состоящего только из единиц:

1 0
 10 01
  1001 0110
   10010110 01101001
    1001011001101001...

• Выпишем подряд числа 0,1,2,3.. В двоичной системе, и посчитаем количество цифр 1 в каждом числе. Затем возьмем остаток этого числа от деления на 2.

в десятичной записи	в двоичной	кол-во единиц	кол-во единиц mod 2
0	0	0	0
1	01	1	1
2	10	1	1
3	11	2	0
4	100	1	1
5	101	2	0
6	110	2	0
7	111	3	1

История

Последовательность была открыта в 1851 году Пруэ (P. Prouhet), который нашёл ей применение в теории чисел, однако не описал исключительные свойства последовательности. И только в 1906 году Аксель Туэ при изучении комбинаторики открыл её заново.

Публикация работы Туэ в Германии прошла бесследно, и последовательность вновь открывает Марсон Морс (Marston Morse) в 1921 году, применив её в дифференциальной геометрии.

Последовательность открывалась независимо много раз: например гроссмейстер Макс Эйве открыл её применение в шахматах, показав, как играть бесконечно, не нарушая правил ничьи.

Свойства

Симметрии

Как и любой фрактал, последовательность Морса — Туэ обладает рядом симметрий. Так последовательность остаётся сама собой

• При удалении всех элементов на чётных местах.

100101100110100

1 0 0 1 0 1 1 0

• При замене двух фрагментов, из которых можно составить всю последовательность другими символами. Последнее означает, что любой кусок последовательности нельзя заархивировать по алгоритму Хаффмана — архив будет совпадать с архивируемым файлом.

1001 0110 0110 1001...
 1    0    0    1  ...

Другие свойства

• В последовательности никогда не встречаются три одинаковых подряд идущих куска, то есть невозможно встретить AAA, где A — любая конечная последовательностей нулей и единиц.
• Дискретное преобразование Фурье последовательности имеет одинаковые максимумы на частотах ⅓ и ⅔.
• Число, двоичной записью которого является последовательность Морса — Туэ, называется числом Пруэ-Туэ-Морса:

$\tau = \sum_{i=0}^{\infty} \frac{t_i}{2^{i+1}} = 0.412454033640 \ldots$ (последовательность A014571 в OEIS),

где $t_i$ — элементы последовательности Морса-Туэ. Это число трансцендентно (доказано K. Mahler в 1929 году).

Вариации и обобщения

Обобщение на произвольный алфавит

Имея произвольный алфавит из n символов, можно составить ровно n разных циклических перестановок этого алфавита. Затем, заменя каждую букву алфавита на соответствующую перестановку, можно получить последовательность Морса — Туэ. Так например из трёх симоволов 1, 2, 3 можно составить три циклических перестановки: 123, 231, 312:

$1 \rightarrow 123$

$2 \rightarrow 231$

$3 \rightarrow 312$

    1         2         3
   123       231       312
123231312 231312123 312123231
123231312231312123312123231 ...

Многомерное обобщение

Двумерная последовательность Морса — Туэ. Чёрным цветом обозначена единица, белым — ноль.

Многомерная последовательность Морса — Туэ определяется подобным образом. Так например двумерная последовательность (матрица) является пределом последовательности, каждый следующий член которой получается из предыдущего при помощи преобразования

$1 \rightarrow \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix}$ ; $0 \rightarrow \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}$

$~10010110\cdots$

$~01101001\cdots$

$~01101001\cdots$

$~10010110\cdots$

$~\vdots \quad \vdots \quad \vdots \quad \ddots$

Также двумерную последовательность Морса-Туэ можно представить как совокупность одномерных.

Ссылки

• Weisstein, Eric W. Последовательность Морса — Туэ (англ.) на сайте Wolfram MathWorld.