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

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

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

0 1 10 1001 10010110 1001011001101001....

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

Задання

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

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

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

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

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

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

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

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

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

Перший елемент - 0. Якщо перших ${\displaystyle 2^{n}}$ елементів визначені, і формують послідовність ${\displaystyle s}$, тоді наступні ${\displaystyle 2^{n}}$ елементів є побітовим запереченням ${\displaystyle s}$. Таким чином ми описали перших ${\displaystyle 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. [ 25 лютого 2021 у Wayback Machine.] Allouche, J.-P.; Shallit, J. O. Many applications and some history
• MathWorld: Thue-Morse Sequence [ 26 липня 2010 у Wayback Machine.]. Some other applications
• When Thue-Morse meets Koch [ 21 лютого 2007 у Wayback Machine.] 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 [ 26 вересня 2010 у Wayback Machine.] Freeware to generate self similar music based on the Thue–Morse Sequence and related number sequences.