Słowo Thuego-Morse’a

Tworzenie kolejnych słów Thuego-Morse’a

Słowo Thuego-Morse’a – nieskończony ciąg binarny; słowo nad alfabetem $\{0,1\},$ które pojawia się w wyniku analizy różnych zagadnień, często w odległych dziedzinach. Jedna z metod jego konstrukcji polega na podaniu jego pierwszego elementu (litery) $0,$ a następnie dopisywaniu w każdym kolejnym kroku do już wypisanych elementów ich negacji. Każda kolejna iteracja wydłuża dwukrotnie uzyskany ciąg.

Pierwsze 32 symbole ciągu to

01101001100101101001011001101001… Szablon:OEIS.

Definicje

Istnieje kilka równoważnych sposobów na zdefiniowanie ciągu Thuego-Morse’a.

Definicja formalna

Jeśli skończone wyrazy ciągu są zdefiniowana jako

$T_n:=\{\begin{array}{cc}0& \text{dla }n=0,\\ T_{n-1}\overline{T_{n-1}}& \text{dla }n>0,\end{array}$

gdzie $\bar{T}$ oznacza słowo, w którym wszystkie litery zostały zanegowane,

to $T_{\mathrm{\infty }}:=\underset{n\to \mathrm{\infty }}{\lim }{T}_n$ jest słowem Thuego-Morse’aSzablon:OdnSzablon:Odn.

Wzór ogólny ciągu

Jeśli kolejne litery $t_n$ słowa ponumerujemy od zera, to na pozycji $n$ będzie $1,$ gdy liczba jedynek w zapisie binarnym liczby $n$ będzie nieparzysta i $0$ w przeciwnym razieSzablon:Odn.

PrzykładSzablon:Odn:

Niech $n=11.$

Ponieważ $(11{)}_{10}=(1011{)}_2$ i liczba jedynek liczby 11 w zapisie dwójkowym jest równa 3, czyli jest nieparzysta, więc

$t_{11}=1.$

Ta metoda pozwala na utworzenie efektywnego algorytmu na obliczanie kolejnych wyrazów ciąguSzablon:Odn.

Wzór rekurencyjny

Kolejne litery $t_n$ ciągu można wyznaczać według wzoruSzablon:Odn:

$\begin{array}{cc}{t}_0& =0,\\ t_{2n}& =t_n,\\ t_{2n+1}& \ne t_n,\end{array}$

dla wszystkich nieujemnych $n.$

Definicja z pomocą morfizmu

Niech $\mu$ będzie następującym morfizmemSzablon:Odn

$\begin{array}{cc}\mu (0)& =01,\\ \mu (1)& =10,\\ \mu (uv)& =\mu (u)\mu (v).\end{array}$

Tworząc ciąg iterat począwszy od litery $0,$ otrzymujemySzablon:Odn:

$\begin{array}{cc}\mu (0)& =01,\\ {\mu }^2(0)& =\mu (\mu (0))=\mu (01)=\mu (0)\mu (1)=0110,\\ {\mu }^3(0)& =\mu ({\mu }^2(0))=\mu (0)\mu (1)\mu (1)\mu (0)=01101001.\end{array}$

Wyrażenie ${\mu }^{\mathrm{\infty }}(0):=\underset{n\to \mathrm{\infty }}{\lim }{\mu }^n(0)$ jest słowem Thuego-Morse’aSzablon:OdnSzablon:OdnSzablon:Odn. Natomiast $\mu$ nazywa się morfizmem Thuego-Morse’aSzablon:Odn.

Własności

• słowo zawiera kwadraty podsłówSzablon:Odn,
• słowo jest beznakładkoweSzablon:OdnSzablon:Odn,
• z beznakładkowości wynika, że słowo nie zawiera niepustego podsłowa będącego trzecią potęgąSzablon:Odn,
• analiza definicji z pomocą morfizmu prowadzi do wniosku, że słowo jest fraktalemSzablon:Odn.

Uogólnienie

Korzystając z definicji bezpośredniej bazującej na obliczaniu sumy jedynek $\text{mod}2,$ można zdefiniować uogólnienie, w którym dla litery $t_n$ obliczana jest suma cyfr o postawie $k\ge 2.$ Tak zdefiniowany ciąg $\{T_k(n){\}}_{n=0}^{\mathrm{\infty }}$ jest również binarny, a po podstawieniu $k=2$ daje $T_2(n)=T(n)$ ciąg słów Thuego-Morse’aSzablon:Odn.

Dalszym uogólnieniem jest zwiększenie rozmiaru alfabetu generującego słowa, zastępując operację $\text{mod}2$ przez $\text{mod}m$Szablon:Odn. Tak uzyskany ciąg tworzy słowo beznakładkowe wtedy i tylko wtedy gdy $m\ge k$Szablon:Odn dla $k\ge 2$ i $m\ge 1$Szablon:Odn.

Historia

Pierwsze badania nad ciągiem, w ramach teorii liczb przeprowadził Szablon:Link-interwiki w 1851Szablon:Odn. Jednak nie wskazał go jawnie. Zrobił to dopiero Axel Thue w 1906Szablon:Odn, w swoich badaniach nad słowami w dziedzinie kombinatorykiSzablon:Odn. Nieskończony ciąg binarny zyskał światową uwagę dzięki pracy Szablon:Link-interwiki z 1921 dotyczącej geometrii różniczkowejSzablon:Odn. W kolejnych latach ciąg był również wielokrotnie niezależnie odkrywany w różnych odległych od siebie dziedzinachSzablon:Odn.

Zobacz też

• słowa Fibonacciego

Bibliografia

• Szablon:Cytuj
• Szablon:Cytuj
• Szablon:Cytuj
• Szablon:Cytuj
• Szablon:Cytuj
• Szablon:Cytuj
• Szablon:Cytuj

Linki zewnętrzne

• Szablon:MathWorld
• Szablon:Cytuj
• Szablon:Cytuj
• Szablon:Cytuj