Mała Delta

Fraktale z zer i jedynek

Tradycyjnie fraktale kojarzą nam się (często) z ładnymi rysunkami figur, które wykazują pewien zestaw cech odróżniających je od zwykłych obiektów. Nie precyzujemy tutaj uniwersalnego zestawu, gdyż sama definicja fraktala nie jest uniwersalna. W większości sytuacji chcemy, aby fraktal miał złożoną strukturę, spełniał pewne cechy samopodobieństwa oraz by nie dało się go zbyt prosto opisać geometrycznie. Mimo to często można go opisać względnie prosto pewnymi regułami rekurencyjnymi wykonywanymi na obiekcie startowym (lub zestawie takich obiektów).

Rozważmy nieskończony ciąg $(xn)nE0,$ którego elementami są skończone ciągi zer i jedynek. Wprowadzamy operację negatywu skończonego ciągu $|y.$ Operacja ta dokonuje zamiany zer na jedynki oraz jedynki na zera w ciągu $|y,$ a jej wynik oznaczamy przez $y.$ Jeśli więc $|y = 01010,$ to $-- |y = 10101.$ Definiujemy rekurencyjnie ciąg $(xn)nE0$ : niech $|x0 = 0$ oraz $--- |xn+1 = xnxn.$ A zatem $x1 = 01,x2 = 0110,x3 = 01101001$ i tak dalej. Ciągiem Thuego-Morse'a nazwiemy nieskończony ciąg $------ x = x0x0x1x2 ...,$ który ma tę własność, że każdy $x i$ jest jego prefiksem:

x = 0110100110010110100101100110100110010110011010010110100110010110...

Definicja ciągu $|(xn)nE0$ pozwala na wygenerowanie ciekawego obrazka przez odpowiednie kolorowanie pól macierzy $n M$ o wymiarach $2n× 2n$ (elementy macierzy rozmieszczamy w kwadracie $1× 1$ ). Mianowicie macierz $nM$ wypełniamy cyframi ciągu $x2n.$ Zaczynając od lewego górnego rogu, wypełniamy kolejne komórki, przesuwając się w prawo, a następnie, po wypełnieniu pierwszego wiersza przechodzimy niżej itd. Zauważmy, że kolumna najbardziej z lewej ma taką samą zawartość jak najwyższy wiersz. Podobnie druga kolumna od lewej ma taką samą zawartość jak drugi wiersz od góry itd. Pola z cyfrą zero malujemy na biało, te z jedynką na czarno. Otrzymujemy w ten sposób ciąg biało-czarnych szachownic takich, że cała szachownica $n |M$ jest podszachownicą $n+1. M$ Dokładniej: szachownica $n+1M$ zawiera dwie kopie szachownicy $n M$ oraz dwa jej negatywy (pola czarne stają się białe i odwrotnie).

Rozważmy szachownice narysowane dla dużych, coraz większych $|n,$ pokolorujmy nawet w ten sposób całą ćwiartkę płaszczyzny podzieloną na jednostkowe kwadraty. Pierwszy wiersz ćwiartki zawiera cały ciąg Thuego-Morse'a, tzn. jest pokolorowany zgodnie z jego oznaczeniami, podobnie pierwsza kolumna. Takie nieskończone pokolorowanie ma wiele ciekawych cech. Dla przykładu usuńmy z naszej ćwiartki drugi, czwarty i każdy parzysty wiersz, to samo zróbmy z kolumnami. Resztę sklejmy w całość (to nie będzie trudne, elementy będą do siebie pasować). Co powstało? Otrzymaliśmy kolorowankę identyczną z początkową.

Weźmy na ćwiartce kwadrat o $k k 2 × 2$ polach $|(k > 0),$ jego identyczną kopię można znaleźć w wielu, a nawet bardzo wielu, innych miejscach. Zachęcamy do zabawy w szukanie zależności między współrzędnymi lewego górnego rogu kwadratu i długością jego krawędzi a kolorami wierzchołków wszystkich jego kopii.

Żółw to zwierzę nieco powolne, ale rozumne i gdy określi się dla niego ciąg instrukcji, bezbłędnie je wykona. Na polecenie "0" żółw reaguje ruchem o jedną jednostkę do przodu, na polecenie "1" obraca się w miejscu o $|60o$ przeciwnie do ruchu wskazówek zegara. Naszą trasę (a raczej żółwia) nazwiemy grafiką żółwia.

Co się stanie, gdy polecenia będą kolejnymi cyframi ciągu Thuego-Morse'a? Przyjmijmy, że dla ustalonego $|n$ czytamy wszystkie cyfry ciągu $|xn$ i generujemy grafikę żółwia. Jak będzie wyglądać rysunek ciągu $|x0,x1,x4$ lub też $x10?$ Czy wraz ze wzrostem indeksu $|n$ rysunek będzie coraz bardziej chaotyczny, czy może zaobserwujemy jakiś porządek?

Zacznijmy od kilku prostych obrazków dla $n = 2,3,4,5,6,7,8.$

Prawdopodobnie nie jesteśmy jeszcze w stanie dostrzec schematu lub podobieństwa. Zróbmy rysunek dużo większy, to jest dla $|n = 14$ (rysunek na marginesie jest obrócony w stosunku do wcześniejszych przykładów).

Czytelnik znający podstawowe fraktale dostrzeże tutaj zarys krzywej Kocha, której schemat generowania kolejnych przybliżeń (niemający na oko związku z ciągiem Thuego-Morse'a) przedstawiamy poniżej.

Nie jest to przypadek. Okazuje się bowiem, że im większe $n,$ tym wierniej grafika żółwia dla naszego ciągu odtwarza krzywą Kocha. Należy jednak zaznaczyć, iż nie będzie to idealna i dokładna kopia. Otrzymany rysunek jest jedynie aproksymacją, ale wysoce porządną. Kolejne przybliżenia zbiegają bowiem jednostajnie (po odpowiednim skalowaniu i obracaniu) do prawdziwej krzywej Kocha (czyli "ostatniego" obrazka, jaki należałoby narysować w nieskończonym ciągu powyższych krzywych). Co to znaczy "jednostajnie"? Ciąg krzywych aproksymuje jednostajnie inną, gdy dla dowolnego błędu, który ustalimy (dowolnie małego, o więcej nie chcemy się mylić) od pewnego indeksu $n$ (odpowiada to krzywej ciągu $|xn$ ) wszystkie krzywe są odległe od tego, do czego zbiegają, o nie więcej niż wybrany na początku błąd. Ta zdumiewająca własność (generowanie fraktali) nie jest jedynie cechą ciągu Thuego-Morse'a, ale znacznie większej rodziny ciągów.

Czytelników ciekawych tych oraz innych związków zachęcamy do przeczytania artykułu When Thue-Morse Meets Koch, którego autorami są Jun Ma oraz Judy Holdener.