- Последовательность Туэ
-
Последовательность Морса-Туэ — бесконечная последовательность нулей и единиц, впервые предложенная в 1906 году норвежским математиком Акселем Туэ в качестве примера апериодической рекурсивно вычислимой строки символов. Эта последовательность является простейшим примером фрактала. Применяется в алгоритмах сжатия изображений фрактальным способом.
10010110011010010110100110010110...
Содержание
Определения
Последовательность можно определить многими разными эквивалентными способами:
- Выполняя преобразование ; , взяв за первую итерацию 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 Свойства
Обобщение на произвольный алфавит
Имея произвольный алфавит из n символов, можно составить ровно n разных циклических перестановок этого алфавита. Затем, заменя каждую букву алфавита на соответсвующую перестановку, можно получить последовательность Морса-Туэ. Так например из трёх симоволов 1, 2, 3 можно составить три циклических перестановки: 123, 231, 312:
1 2 3 123 231 312 123231312 231312123 312123231 123231312231312123312123231 ...
Многомерное обобщение
Многомерная последовательность Морса-Туэ определяется подобным образом. Так например двумерная последовательность (матрица) является пределом последовательности, каждый следующий член которой получается из предыдущего при помощи преобразованием
- ;
Также двумерную последовательность Морса-Туэ можно представить как совокупность одномерных.
Симметрии
Как и любой фрактал, последовательность Морса-Туэ обладает рядом симметрий. Так последовательность остаётся сама собой
- При удалении всех элементов на чётных местах.
100101100110100 1 0 0 1 0 1 1 0
- При замене двух фрагментов, из которых можно составить всю последовательность другими символами. Последнее означает, что любой кусок последовательности нельзя заархивировать по алгоритму Хаффмана — архив будет совпадать с архивируемым файлом.
1001 0110 0110 1001... 1 0 0 1 ...
Другие свойства
- В последовательности никогда не встречаются три одинаковых подряд идущих куска, то есть невозможно встретить AAA, где под A можно подразумевать любую конечную последовательностей нулей и единиц.
- Фурье-преобразование последовательности имеет одинаковые максимумы на частотах 1/3 и 2/3.
- Число, двоичной записью которого является последовательность Морса-Туэ, называется числом Пруэ-Туэ-Морса.
, где ti — элементы последовательности Морса-Туэ. Это число трансцендентно (доказано K. Mahler в 1929).
История
Последовательность была открыта в 1851 году Пруэ (P. Prouhet), который нашёл ей применение в теории чисел, однако не описал исключительные свойства последовательности. И только в 1906 году Аксель Туэ при изучении комбинаторики открыл её заново.
Публикация работы Туэ в Германии прошла бесследно, и последовательность вновь открывает Марсон Морс (Marston Morse) в 1921 году, применив её в дифференциальной геометрии.
Последовательность открывалась независимо много раз: например гроссмейстер Макс Эйве открыл её применение в шахматах, показав, как играть бесконечно, не нарушая правил ничьи.
Применения
Ссылки
- Weisstein, Eric W. Последовательность на сайте Wolfram MathWorld.(англ.)
Wikimedia Foundation. 2010.