Słowo Thuego-Morse’a

Słowo Thuego-Morse’a – nieskończony ciąg binarny; słowo nad alfabetem ${\displaystyle \{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) ${\displaystyle 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… (ciąg A010060 w OEIS).

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

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

${\displaystyle T_{n}:={\begin{cases}0&{\text{dla }}n=0,\\T_{n-1}{\overline {T_{n-1}}}&{\text{dla }}n>0,\end{cases}}}$

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

to ${\displaystyle T_{\infty }:=\lim _{n\to \infty }T_{n}}$ jest słowem Thuego-Morse’a^[1][2] .

Jeśli kolejne litery ${\displaystyle t_{n}}$ słowa ponumerujemy od zera, to na pozycji ${\displaystyle n}$ będzie ${\displaystyle 1,}$ gdy liczba jedynek w zapisie binarnym liczby ${\displaystyle n}$ będzie nieparzysta i ${\displaystyle 0}$ w przeciwnym razie^[2] .

Przykład^[3]:

Niech ${\displaystyle n=11.}$

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

${\displaystyle t_{11}=1.}$

Ta metoda pozwala na utworzenie efektywnego algorytmu na obliczanie kolejnych wyrazów ciągu^[4].

Kolejne litery ${\displaystyle t_{n}}$ ciągu można wyznaczać według wzoru^[3]:

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

dla wszystkich nieujemnych ${\displaystyle n.}$

Niech ${\displaystyle \mu }$ będzie następującym morfizmem^[5]

${\displaystyle {\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 ${\displaystyle 0,}$ otrzymujemy^[6]:

${\displaystyle {\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 ${\displaystyle \mu ^{\infty }(0):=\lim _{n\to \infty }\mu ^{n}(0)}$ jest słowem Thuego-Morse’a^[1][2] [6]. Natomiast ${\displaystyle \mu }$ nazywa się morfizmem Thuego-Morse’a^[5].

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

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

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

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

• słowa Fibonacciego

• 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.).

• 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] .