Русская Википедия:Последовательность Морса — Туэ
Последовательность Морса — Туэ — бесконечная последовательность нулей и единиц (битов), впервые предложенная в 1906 году норвежским математиком Акселем Туэ в качестве примера апериодической рекурсивно вычислимой строки символовШаблон:Уточнить. Существует два варианта последовательности, получающиеся друг из друга инверсией битов:
- 10010110011010010110100110010110… (Шаблон:OEIS) — дополнительная
- 01101001100101101001011001101001… (Шаблон:OEIS) — основная
Последовательность Морса — Туэ является простейшим примером фрактала и находит своё применение в алгоритмах фрактального сжатия изображений.
Определения
Последовательность можно определить многими разными эквивалентными способами:
- Выполняя преобразование <math>0 \rightarrow 01 </math> ; <math> 1 \rightarrow 10 </math>, взяв за первую итерацию <math>1</math>:
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 в каждом числе. (Получим Шаблон: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 году Пруэ (Шаблон:Lang-fr), который нашёл ей применение в теории чисел, однако не описал исключительные свойства последовательности. И только в 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» — последовательностей нулей и единиц);
- Дискретное преобразование Фурье последовательности имеет одинаковые максимумы на частотах ⅓ и ⅔;
- Число, двоичной записью которого является последовательность Морса — Туэ, называется числом Пруэ-Туэ-Морса:
- <math> \tau = \sum_{i=0}^{\infty} \frac{t_i}{2^{i+1}} = 0.412454033640 \ldots</math> (Шаблон:OEIS),
где <math> t_i </math> — элементы последовательности Морса-Туэ. Это число трансцендентно (доказано K. Mahler в 1929 году).
Вариации и обобщения
Обобщение на произвольный алфавит
Имея произвольный алфавит из n символов, можно составить ровно n разных циклических перестановок этого алфавита. Затем, заменяя каждую «букву» алфавита на соответствующую перестановку, можно получить последовательность Морса — Туэ. Так например из трёх символов «1», «2», «3» можно составить три циклических перестановки: «123», «231», «312»:
- <math>1 \rightarrow 123</math>
- <math>2 \rightarrow 231</math>
- <math>3 \rightarrow 312</math>
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...
Многомерное обобщение
Многомерная последовательность Морса — Туэ определяется подобным образом. Так например двумерная последовательность (матрица) является пределом последовательности, каждый следующий член которой получается из предыдущего при помощи преобразования
- <math>1 \rightarrow \begin{matrix} 1 & 0 \\ 0 & 1 \end{matrix} </math> ; <math>0 \rightarrow \begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix} </math>
| <math>10010110\cdots</math> |
| <math>01101001\cdots</math> |
| <math>01101001\cdots</math> |
| <math>10010110\cdots</math> |
| <math>\vdots \quad \vdots \quad \vdots \quad \ddots</math> |
Также двумерную последовательность Морса-Туэ можно представить как совокупность одномерных.
Ссылки
