Послідовність Морзе - Туе

Анімація демонструє генерацію послідовності Морсе-Туе.

В математиці, послідовністю Морсе-Туе, називають двійкову послідовність яка починається так:

0 1 10 1001 10010110 1001011001101001....

Замість символів 1 та 0 можна використати будь-яку іншу пару, логічна структура послідовності Морсе-Туе не залежить від символів що використовуються для її представлення.

Задання

Існує кілька способів задати послідовність Морсе-Туе:

Пряме задання

Щоб обчислити n-тий елемент $t_n$, запишіть номер $n$ в двійковій формі. Якщо число одиниць в цьому двійковому записі непарне, тоді $t_n = 1$, якщо ж парне, то $t_n = 0$.

Рекурсивне задання

Послідовність $t_n$ можна задати так: $\begin{cases} t_0 = 0 \\ t_{2n} = t_n \\ t_{2n+1} = 1 - t_n \end{cases} \forall n \in \mathbb{N}$

L-система

Послідовність Морсе-Туе - це вивід наступної системи Лінденмаєра:

  Змінні  0  1
  Константи  немає
  Аксіома      0
  Правила      (0 → 01), (1 → 10)

Конкатенація з результатом побітового "не"

Послідовність Морсе-Туе, у формі що дається вище як послідовність бітів, може описуватись рекурсивно з використанням оператора побітового заперечення.

Перший елемент - 0. Якщо перших $2^n$ елементів визначені, і формують послідовність $s$, тоді наступні $2^n$ елементів є побітовим запереченням $s$. Таким чином ми описали перших $2^{n+1}$ елементів, і продовжимо рекурсію для них.

Якщо розписати кілька перших кроків:

1. Починаємо з нуля. Отримуємо 0
2. Побітовим запереченням нуля є 1. Отримуємо 01
3. Побітовим запереченням 01 є 10. Отримуємо 0110
4. Побітовим запереченням 0110 є 1001. Отримуємо 01101001
5. І так далі. Дивіться анімацію на початку статті.

Деякі властивості

Фрактали та черепашача графіка

Черепашача графіка - це крива, що генерується автоматом, який керується послідовністю команд.

Якщо елементи послідовності Морсе-Туе інтерпретувати так:

• Якщо t(n) = 0, переміститись вперед на одиницю,
• Якщо t(n) = 1, повернутись проти годинникової стрілки на кут π/3,

Крива яку отримуємо в результаті збігається до сніжинки Коха, фрактальної кривої нескінченної довжини, що міститься в скінченній площі. Це ілюструє фрактальну природу послідовності Морсе-Туе.

Посилання

• Використано матеріали зі статті в англійській Вікіпедії.
• The Ubiquitous Prouhet-Thue-Morse Sequence. Allouche, J.-P.; Shallit, J. O. Many applications and some history
• MathWorld: Thue-Morse Sequence. Some other applications
• When Thue-Morse meets Koch A paper showing an astonishing similarity between the Thue–Morse Sequence and the Koch snowflake
• Reducing the influence of DC offset drift in analog IPs using the Thue-Morse Sequence A technical application of the Thue–Morse Sequence
• MusiNum - The Music in the Numbers Freeware to generate self similar music based on the Thue–Morse Sequence and related number sequences.