Последовательность Морса — Туэ

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

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

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

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

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

ОпределенияПравить

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

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

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

• Начинаем с 1. На каждом шаге дописываем к числу инверсию этого числа. Инверсия получается заменой всех нулей на единицы, а единиц на нули. К примеру, инверсией числа 1001 будет число 0110. (По-другому инверсию числа можно описать так: это число, дополняющее уже написанное до числа, состоящего только из единиц; например 1001+0110=1111 в двоичной системе счисления)

Шаг 1: 1
Шаг 2: 10
Шаг 3: 1001
Шаг 4: 10010110
Шаг 5: 1001011001101001
...

• Выпишем подряд числа 0,1,2,3... в двоичной системе, и посчитаем количество цифр 1 в каждом числе. (Получим последовательность A000120 в OEIS.) Затем возьмем остаток этого числа от деления на 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 году Пруэ (фр. E. Prouhet), который нашёл ей применение в теории чисел, однако не описал исключительные свойства последовательности. И только в 1906 году Аксель Туэ при изучении комбинаторики открыл её заново.

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

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

СвойстваПравить

СимметрииПравить

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

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

10 01  01 10  01 10  10 01  01 10  10 01  10 01  01 10...

1  0   0  1   0  1   1  0   0  1   1  0   1  0   0  1...

• При замене двух частей, из которых можно составить целое, другими двумя символами. Это означает, что последовательность нельзя заархивировать по алгоритму Хаффмана, так как последовательность, являющаяся «архивом» будет совпадать с самой последовательностью Морса — Туэ:

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

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

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

$\mathrm{\tau <!--\; \tau \; -->}=\underset{i=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\sum <!--\; \sum \; -->}}\frac{t_i}{2^{i+1}}=0.412454033640\dots <!--\; \dots \; -->$$\tau =\sum _{{i=0}}^{{\infty }}{\frac {t_{i}}{2^{{i+1}}}}=0.412454033640\ldots$  (последовательность A014571 в OEIS),

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

Вариации и обобщенияПравить

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

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

$1\to <!--\; \to \; -->123$$1\rightarrow 123$ 

$2\to <!--\; \to \; -->231$$2\rightarrow 231$ 

$3\to <!--\; \to \; -->312$$3\rightarrow 312$ 

                              1
         1                    2                    3
  1      2      3      2      3      1      3      1      2
1 2 3  2 3 1  3 1 2  2 3 1  3 1 2  1 2 3  3 1 2  1 2 3  2 3 1...

Многомерное обобщениеПравить

 

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

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

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

$10010110\cdots <!--\; \cdots \; -->$$10010110\cdots$

$01101001\cdots <!--\; \cdots \; -->$$01101001\cdots$

$01101001\cdots <!--\; \cdots \; -->$$01101001\cdots$

$10010110\cdots <!--\; \cdots \; -->$$10010110\cdots$

$⋮<!--\; ⋮\; -->⋮<!--\; ⋮\; -->⋮<!--\; ⋮\; -->\ddots <!--\; \ddots \; -->$$\vdots \quad \vdots \quad \vdots \quad \ddots$

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

СсылкиПравить

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