Słowo Thuego-Morse’a
Słowo Thuego-Morse’a – nieskończony ciąg binarny; słowo nad alfabetem 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) 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).
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
gdzie oznacza słowo, w którym wszystkie litery zostały zanegowane,
to jest słowem Thuego-Morse’a[1][2] .
Wzór ogólny ciągu
Jeśli kolejne litery słowa ponumerujemy od zera, to na pozycji będzie gdy liczba jedynek w zapisie binarnym liczby będzie nieparzysta i w przeciwnym razie[2] .
Przykład[3]:
Niech
Ponieważ i liczba jedynek liczby 11 w zapisie dwójkowym jest równa 3, czyli jest nieparzysta, więc
Ta metoda pozwala na utworzenie efektywnego algorytmu na obliczanie kolejnych wyrazów ciągu[4].
Wzór rekurencyjny
Kolejne litery ciągu można wyznaczać według wzoru[3]:
dla wszystkich nieujemnych
Definicja z pomocą morfizmu
Niech będzie następującym morfizmem[5]
Tworząc ciąg iterat począwszy od litery otrzymujemy[6]:
Wyrażenie jest słowem Thuego-Morse’a[1][2][6]. Natomiast nazywa się morfizmem Thuego-Morse’a[5].
Własności
- 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].
Uogólnienie
Korzystając z definicji bezpośredniej bazującej na obliczaniu sumy jedynek można zdefiniować uogólnienie, w którym dla litery obliczana jest suma cyfr o postawie Tak zdefiniowany ciąg jest również binarny, a po podstawieniu daje ciąg słów Thuego-Morse’a[8].
Dalszym uogólnieniem jest zwiększenie rozmiaru alfabetu generującego słowa, zastępując operację przez [9]. Tak uzyskany ciąg tworzy słowo beznakładkowe[b] wtedy i tylko wtedy gdy [9] dla i [10].
Historia
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].
Zobacz też
Uwagi
- ↑ Słowa kwadratowe to dwukrotne sklejenie takie samej kombinacji symboli na przykład mama lub kankan[13].
- ↑ a b Definicja: Słowo jest beznakładkowe jeśli nie zawiera wzoru o postaci gdzie jest literą z alfabetu tworzącego słowa, a dowolnym układem liter (także pustym)[14]. W słowach nakładkowych można znaleźć powtórzone podsłowa jak na przykład we francuskim wyrazie entente[9].
Przypisy
- ↑ a b c Williamson 2010 ↓, s. 3.
- ↑ a b c d e f szreder 2011 ↓.
- ↑ a b Williamson 2010 ↓, s. 2.
- ↑ Arndt 2011 ↓, s. 44.
- ↑ a b Fraenkel 2015 ↓, s. 2.
- ↑ a b Fraenkel 2015 ↓, s. 3.
- ↑ a b Allouche i Shallit 1999 ↓, 3.1 The pioneering work of Thue.
- ↑ Astudillo 2003 ↓, s. 1–2.
- ↑ a b c Allouche i Shallit 2000 ↓, s. 1.
- ↑ Williamson 2010 ↓, s. 13.
- ↑ a b c Allouche i Shallit 1999 ↓, Abstract.
- ↑ Allouche i Shallit 1999 ↓, 4. Differential geometry.
- ↑ JakubJ. Radoszewski JakubJ., Kwadraty, „Delta”, marzec 2011 [dostęp 2018-06-27] .
- ↑ Williamson 2010 ↓, s. 9.
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] .