Słowo 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.

Tworzenie kolejnych słów Thuego-Morse’a

Pierwsze 32 symbole ciągu to

01101001100101101001011001101001… (ciąg A010060 w 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{cases}0&{\text{dla }}n=0,\\T_{n-1}{\overline {T_{n-1}}}&{\text{dla }}n>0,\end{cases}}$

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

to $T_{\infty }:=\lim _{n\to \infty }T_{n}$ jest słowem Thuego-Morse’a .

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 razie .

Przykład:

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ągu.

Wzór rekurencyjny

Kolejne litery $t_{n}$ ciągu można wyznaczać według wzoru:

${\begin{aligned}t_{0}&=0,\\t_{2n}&=t_{n},\\t_{2n+1}&\neq t_{n},\end{aligned}}$

dla wszystkich nieujemnych $n.$

Definicja z pomocą morfizmu

Niech $\mu$ będzie następującym morfizmem

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

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

${\begin{aligned}\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{aligned}}$

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

Własności

• słowo zawiera kwadraty podsłów ,
• słowo jest beznakładkowe ,
• z beznakładkowości wynika, że słowo nie zawiera niepustego podsłowa będącego trzecią potęgą ,
• analiza definicji z pomocą morfizmu prowadzi do wniosku, że słowo jest fraktalem.

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\geq 2.$ Tak zdefiniowany ciąg $\{T_{k}(n)\}_{n=0}^{\infty }$ jest również binarny, a po podstawieniu $k=2$ daje $T_{2}(n)=T(n)$ ciąg słów Thuego-Morse’a.

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

Historia

Pierwsze badania nad ciągiem, w ramach teorii liczb przeprowadził Eugène Prouhet w 1851. Jednak nie wskazał go jawnie. Zrobił to dopiero Axel Thue w 1906, w swoich badaniach nad słowami w dziedzinie kombinatoryki. Nieskończony ciąg binarny zyskał światową uwagę dzięki pracy Marstona Morse’a z 1921 dotyczącej geometrii różniczkowej. W kolejnych latach ciąg był również wielokrotnie niezależnie odkrywany w różnych odległych od siebie dziedzinach.

Zobacz też

• słowa Fibonacciego

Bibliografia

• Jean-PaulJ.P. Allouche Jean-PaulJ.P., JeffreyJ. Shallit JeffreyJ., The ubiquitous Prouhet-Thue-Morse sequence [online], 1999 [dostęp 2018-06-24]  (ang.).
• Jean-PaulJ.P. Allouche Jean-PaulJ.P., JeffreyJ. Shallit JeffreyJ., Sums of Digits, Overlaps, and Palindromes, „Discrete Mathematics and Theoretical Computer Science”, 4 (1), 2000, s. 001–010, hal-00958941 [dostęp 2018-06-24] .
• 1.16.4 The Thue-Morse sequence, [w:] JörgJ. Arndt JörgJ., Matters Computational: Ideas, Algorithms, Source Code, Springer, 2011  (ang.).
• RicardoR. Astudillo RicardoR., On a class of Thue-Morse type sequences, „Journal of Integer Sequences”, 6, 2003, Article 03.4.2  (ang.).
• Aviezri S.A.S. Fraenkel Aviezri S.A.S., Games derived from a generalized Thue-Morse word [online], 31 grudnia 2015 [dostęp 2018-06-25]  (ang.).
• szreder, Rozdział 2: Przykłady ciekawych abstrakcyjnych tekstów | Informatyka MIMUW [online], 18 stycznia 2011 [dostęp 2018-06-24] .
• ChristopherCh. Williamson ChristopherCh., An Overview of the Thue-Morse Sequence [online], 4 czerwca 2010 [dostęp 2018-06-24]  (ang.).

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Thue-Morse Sequence, [w:] MathWorld, Wolfram Research  (ang.).
• KarolK. Gryszka KarolK., Od Prouheta-Tarry’ego-Escotta do Thuego-Morse’a, „Delta”, październik 2016 [dostęp 2018-06-24] .
• KarolK. Gryszka KarolK., Sprawiedliwie, sprawiedliwiej, najsprawiedliwiej, „Delta”, listopad 2016 [dostęp 2018-06-24] .
• KarolK. Gryszka KarolK., Fraktale z zer i jedynek, „Delta”, marzec 2017 [dostęp 2018-06-25] .