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

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

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

Определения


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

  • Выполняя преобразование 001 ; 110, взяв за первую итерацию 1:

 \texttt        1\\\texttt    1       0\\\texttt  1   0   0   1\\\texttt 1 0 0 1 0 1 1 0 

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

 \texttt1 0\\\texttt 10 01\\\texttt  1001 0110\\\texttt   10010110 01101001\\\texttt    1001011001101001...

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

10010110
01101001
01101001
10010110

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