Słowo Thuego-Morse’a

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania
Tworzenie kolejnych słów 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 publikacja w otwartym dostępie – możesz ją przeczytać A010060 w OEIS).

Definicje[edytuj | edytuj kod]

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

Definicja formalna[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Kolejne litery ciągu można wyznaczać według wzoru[3]:

dla wszystkich nieujemnych

Definicja z pomocą morfizmu[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  • 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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

Pierwsze badania nad ciągiem, w ramach teorii liczb przeprowadził Eugène ProuhetInformacje powiązane z artykułem „Eugène Prouhet” w Wikidanych 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’aInformacje powiązane z artykułem „Marston Morse” w Wikidanych 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ż[edytuj | edytuj kod]

Uwagi[edytuj | edytuj kod]

  1. Słowa kwadratowe to dwukrotne sklejenie takie samej kombinacji symboli na przykład mama lub kankan[13].
  2. 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[edytuj | edytuj kod]

  1. a b c Williamson 2010 ↓, s. 3.
  2. a b c d e f szreder 2011 ↓.
  3. a b Williamson 2010 ↓, s. 2.
  4. Arndt 2011 ↓, s. 44.
  5. a b Fraenkel 2015 ↓, s. 2.
  6. a b Fraenkel 2015 ↓, s. 3.
  7. a b Allouche i Shallit 1999 ↓, 3.1 The pioneering work of Thue.
  8. Astudillo 2003 ↓, s. 1–2.
  9. a b c Allouche i Shallit 2000 ↓, s. 1.
  10. Williamson 2010 ↓, s. 13.
  11. a b c Allouche i Shallit 1999 ↓, Abstract.
  12. Allouche i Shallit 1999 ↓, 4. Differential geometry.
  13. Jakub Radoszewski, Kwadraty, „Delta”, marzec 2011 [dostęp 2018-06-27].
  14. Williamson 2010 ↓, s. 9.

Bibliografia[edytuj | edytuj kod]

Linki zewnętrzne[edytuj | edytuj kod]