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

Щоб обчислити 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,

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