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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Определения[править | править вики-текст]

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

  • Выполняя преобразование  ; , взяв за первую итерацию :
        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 году Аксель Туэ при изучении комбинаторики открыл её заново.

Публикация работы Туэ в Германии прошла бесследно, и последовательность вновь открывает Марсон Морс в 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», где « — последовательностей нулей и единиц);
  • Дискретное преобразование Фурье последовательности имеет одинаковые максимумы на частотах ⅓ и ⅔;
  • Число, двоичной записью которого является последовательность Морса — Туэ, называется числом Пруэ-Туэ-Морса:
(последовательность A014571 в OEIS),

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

Вариации и обобщения[править | править вики-текст]

Обобщение на произвольный алфавит[править | править вики-текст]

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

Многомерное обобщение[править | править вики-текст]

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

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

 ;

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

Ссылки[править | править вики-текст]