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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Анімація демонструє генерацію послідовності Морсе-Туе.

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

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,

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

Посилання[ред.ред. код]