Okrakiem na chaosie

O teorii chaosu dowiedziałem się w latach osiemdziesiątych i to zdaje się w pierwszej ich połowie. Pamiętam (ale nie należy zbytnio wierzyć temu wspomnieniu, bo czasem pamięć płata mi figle i zdarza jej się dorobić otoczkę, którą następnie kwestionują współuczestnicy wydarzeń o bardziej protokolarnej pamięci), że byłem z rodzicami na wczasach w Muszynie i czytałem jakieś czasopisma poświęcone technice, bodajże "Przegląd Techniczny" względnie "Horyzonty techniki" (były w dawnych czasach takie czasopisma) i był tam felieton o "efekcie motyla", chaosie, równaniach Lorenza itd. Strasznie te kilka słów rozpaliło moją wyobraźnię. Potem, kiedy zaczytywałem się w SF podobała mi się - ciągle jeszcze wspominana przez fanów gatunku jak widze po szybkim googlowaniu - drukowana w "Fantastyce" powieść Colina Kappa "Formy chaosu" i jej druga część "Bronie chaosu". Nie jest to wielka literatura ale na kilkunastoletniego chłopca wystarczy ;) Nie pamiętam dokładnie akcji, ale generalnie główny bohater był czymś w rodzaju języczka u wagi, kimś kto katalizował zmiany w rzeczywistości - generatorem niewielkich zaburzeń które miały doprowadzić do wielkich efektów. Fenomenalnie przewidująca przyszłość cywilizacja (musiała mieć jakiegoś swojego Laplace'a któremu spełniła się zachcianka wyrażona w słynnym wyznaniu wiary deterministy) miliony lat przed pojawieniem się owego człowieka postanowiła go zniszczyć precyzyjnie kierując wobec niego broń. OK. Moze coś pokręciłem...

Te moje podbijane co jakiś czas różnymi, coraz gęściej, im temat stawał sie modniejszy w naszym kraju, pojawiającymi się publikacjami (tak poularnonaukowymi jak i prozą fabularną) zainteresowania w końcu przyniosły taki efekt, że kiedy studiowałem matematykę, znalazłem sobie temat specjalizacji chyba najbliżej owych rozważań leżący - teorię układów dynamicznych, której częścia, przynajmniej od strony matematycznej jest teoria chaosu właśnie.
W ciągu wielu lat pojawiło się wiele innych pokrewnych tematów a w końcu i teorii, czy to kiełkując z samej teorii chaosu, czy wychodząć od analizy podobnych układów, czy niejako z boku w nawiązaniu do niej. Pojawiła się cała "nauka o złożoności" o zjawiskach "emergencji" czyli spontanicznego pojawiania się złożnoych struktur w wyniku prostych oddziaływań. Do klasycznych obszarów fizyki, które były tradycyjnym siedliskiem fenomenów "chaosu" jak mechanika, czy mechanika statystyczna dołączyła mechanika kwantowa i inne działy a w końcu okazuje się, że zjawiska kojarzone z chaosem są wszędobylskie.

Minęły lata i nie zajmuję się tym więcej, ale kiedy się na coś ciekawego natykam, to zawsze chętnie nadstawiam oko i ucho. Właśnie, zupełnie niespodziewanie, po przeczytaniu krótkiej recenzji, która nie do końca uświadomiła mi czego mam się spodziewać wpadła mi w ręce książka "Masa krytyczna" Philipa Balla. Książka traktuje o zastosowaniach tej nowej nauki o złożoności (ale i nie tylko bo bardziej klasyczne podejścia też są wzmiankowane a bywa, że i omawiane w szczegółach) do zagadnień społecznych i zjawisk otaczającego nas świata ludzi. Okazuje się, że własności obserwowane w bardzo prostych co do założeń i reguł modelach mających naśladować jakieś aspekty społecznego życia, od poruszania się po korytarzach, przez ekonomię i rynki finansowe, systemy polityczne i "mechanikę demokracji" czy reklamy wykazują zadziwiającą zbieżność z rzeczywistymi zjawiskami obserwowanymi w realnym świecie. Że w wielu aspektach naszego życia przejawiają się pewne stałe wzroce jakościowe, podobne rozkłady prawdopodobieństw pewnych zjawisk, wyłaniają się stale te same struktury. Że powszechne jest pojawianie się punktu krytycznego odpowiadającego zestawowi pewnych parametrów opisujących model przy zmianie których układ zmienia swoje odpowiedzi w jakościowo inny sposób w reakcji na zmianę wrunków początkowych czy innych parametrów. Że obserwujemy znane z fizyki przejścia fazowe - niewielka zmiana przenosi system z jednego stanu do kompletnie jakościowo od niego różnego, choć reguły rządzące pojedyńczymi cząstkami reprezentującymi w tym wypadku jednostki, firmy czy państwa nie zmieniają się.

Jedną z podstawowych cech takich układów, o której zresztą wspomniałem tutaj, jest nieproporcjonalnie wielka i nie dająca się ze swojej obliczeniowej natury przewidzieć reakcja systemu na małe odchylenia. Ow metaforyczny efekt motyla. Podobno na takiej zasadzie nieprzewidywalny jest El Ninio - anomalia pogodowa przynosząca klęski żywiołowe mieszkańcom Ameryki Południowej - obszar atraktora układu powietrze/ocean do którego ów chaotycznie zachowujący się system zbliża się co jakiś czas w swim nieregularnym ruchu.
Takie zjawiska zawsze niosą pokusę okiełznania ich w "inżynieryjny" sposób. Gdyby istaniało urządzenie bądź reguła zdolna przewidzieć efekty zmian w układzie chaotycznym, możnaby tanim kosztem osiągać wielkie efekty. By zmieniać pogodę wystarczyłoby wypuścić motyla w odpowiednim momencie...

Ciekawe, czy wiara w magię - w to, że pozornie drobne gesty, rytuały wtajemniczonego moga spowodować jakieś odczuwalne skutki - np. sprowadzić chorobę czy deszcz jest wyrazem jakiegoś pierwotnego uświadomienia sobie zjawiska krytyczności w systemach z którymi stykał się człowiek? Namiastką inżynierii chaosu?
W końcu, czy powstanie kiedyś prawdziwa "inżynieria chaosu"? Czy taka dziedzina w ogóle jest możliwa? Czy byłaby w ogóle pożądana?

Odkurzone, wygrzebane

Czasem zakopane w starych czasopismach, pożółkłych książkach czy innych tego typu zapomninych miejscach do których nikt nie zagląda leżą ciekawe, potencjalnie pożyteczne i eleganckie perełki. Bywa, że odkrywane po wielokroć na nowo stają się elementem folkloru i nikt w zasadzie już nie pamięta kiedy, jak i po co je odkryto po raz pierwszy.
Postanowiłem od czasu do czasu, kiedy natknę się na coś godnego uwagi zanotować to w tym blogu - żeby nacieszyć oko odkurzonym drobiażdżkiem i licząc, że może komuś się przyda...

Dziś następujący problem:
Niech A będzie nieskończonym podzbiorem zbioru liczb naturalnych N (bez 0 dla uniknięcia niepotrzebnych subtelności w rozważaniach o indeksach). Załóżmy, że mamy daną fukcję, COUNT: N->N która dla liczby naturlanej n daje informację ile liczb w zbiorze A jest mniejszych bądź równych n:
COUNT(n) = #{x \in A | x <= n}
poszukujemy algorytmu pozwalającego dla zadanej liczby m wyznaczyć m-ty element zbioru A.

Rozwiązanie jest następujące (użyję c-podobnego pseudokodu):

ORD(m)
{
retval = m;
x = COUNT(retval);
while(x != m)
{
retval += (m - x);
x = COUNT(retval);
}
return retval;
}

miłośnikom dobrej zabawy polecam udowodnienie poprawności algorytmu używając indukcji matematycznej.
"Intuicjonistom", którzy lubią czuć skąd się wziął pomysł, może spodoba się następujące rozumowanie:
Pierwszy strzał to najmniejsza liczba dla której fukcja COUNT ma w ogóle szansę równać się m czyli po prostu m.
Trafiony - świetnie, szukaną liczbą jest właśnie m. Jeżeli nie trafiony, to znaczy, że COUNT(m) < m. Kolejną najmniejszą liczbą m_2 dla której możliwe będzie, że COUNT(m_2)=m jest oczywiście liczba większa od m o tyle ile COUNT(m) zabrakło do m czyli (m-COUNT(m)). Zatem następny strzał to m_2=m+(m-COUNT(m)).
Sprawdzamy więc ile wynosi COUNT(m_2). Jeżeli m to mamy swoją liczbę. Jeżeli nie, to powtarzamy "strzelanie" opierając się na tym samym rozumowaniu i dostajemy m_3 = m_2+(m-COUNT(m_2)) itd. Aż do - murowanego - skutku (pamiętamy - A jest nieskończone!).