frame|right|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… .

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.

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.

Przykład:

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.

Wzór rekurencyjny Kolejne litery ciągu można wyznaczać według wzoru:

dla wszystkich nieujemnych

Definicja z pomocą morfizmu Niech będzie następującym morfizmem

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

Wyrażenie jest słowem Thuego-Morse’a. Natomiast 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 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.

Dalszym uogólnieniem jest zwiększenie rozmiaru alfabetu generującego słowa, zastępując operację przez . Tak uzyskany ciąg tworzy słowo beznakładkowe wtedy i tylko wtedy gdy dla i .

Historia Pierwsze badania nad ciągiem, w ramach teorii liczb przeprowadził 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 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

Uwagi

Przypisy

Bibliografia

Linki zewnętrzne

Thuego-Morse’a słowo