Automaty komórkowe i Reguła 110

Automaty komórkowe są bardzo ciekawym działem matematyki. Wnioski wyciągnięte z ich badania można zastosować do praktycznie wszystkich działów nauki: chemii, biologii, fizyki a nawet astronomii.

Najprostszym przykładem automatu komórkowego jest jednowymiarowy automat. Wyobraźmy sobie nieskończoną taśmę podzieloną na komórki. Każda komórka może być czarna lub biała. Można tym kolorom przypisać liczby: białe – 0, czarne – 1. Zatem całkiem biała taśma wygląda tak:

...00000000000000000...

Całkiem czarna tak:

...11111111111111111...

Możliwe są też różnorodne wzory. Co druga komórka biała (jednowymiarowa szachownica):

...01010101010101010101...

Dodajmy teraz możliwość przekształcania komórek. Załóżmy, że stan komórki będzie zależał od jej koloru oraz od koloru jej sąsiadów. Dla przykładu, reguła:

010 => 0

oznacza, że jeśli komórka jest czarna (środkowa jedynka) a po bokach ma komórki białe to sama też staje się biała.

Reguła:

110 => 0

oznacza, że czarna komórka zmienia kolor gdy jej lewy sąsiad jest czarny a prawy biały.

Ponieważ istnieje osiem różnych kombinacji trzech cyfr 0 i 1 to podając osiem takich reguł można określić kompletną metodę przekształcania każdej z komórek.

poprzedni wzór 111 110 101 100 011 010 001 000
wynik           0   0   1   1   0   0   1   1

Powyższa reguła zamienia wszystkie białe komórki w taśmie na czarne i na odwrót. Jak widać nie są brane pod uwagę kolory sąsiadów.

Jeśli popatrzymy na cyfry 0 i 1 w wyniku to można je potraktować jako liczbę binarną. Ośmiocyfrowa liczba binarna oznacza, że jest 256 różnych reguł opisujących transformację taśmy. Można też użyć tych liczb do oznaczania reguł. Podana powyżej miałaby numer 51 (kolejne cyfry mnożone przez potęgi dwójki czyli 0*128+0*64+1*32+1*16+0*8+0*4+1*2+1*1=51).

Możemy zatem dokładnie opisać następny stan komórki biorąc pod uwagę kolor jej oraz jej sąsiadów. Zastosujmy teraz tą regułę do wszystkich komórek (nieskończonej) taśmy. Otrzymamy drugą taśmę – zwaną drugą generacją. Proces ten można powtarzać w nieskończoność. Taśma ma tylko jeden wymiar ale jeśli narysujemy kolejne generacje jedna pod drugą to pokryją one płaszczyznę tworząc dwuwymiarowe wzory. Poniżej znajduje się wzór generowany przez regułę 30 z taśmy początkowej zawierającej pojedynczą czarną komórkę:

Reguła 30

Rysunek ten pokazuje dwa znaczące fakty:

  • oprócz numeru reguły istotny jest również stan początkowy, od którego zaczynamy generować kolejne taśmy
  • nawet proste stany początkowe mogą prowadzić do bardzo skomplikowanych wzorów, nawet wyglądających na losowe

Mimo, że istnieje 256 różnych reguł to niektóre z nich można traktować jak bliźniaki. Jeśli ciąg cyfr 0 i 1 opisujący regułę odwrócimy to wzory przez nią generowane również się odwrócą ale ich kształt i zachowanie pozostanie bez zmian. Podobnie jeśli zamienimy zera na jedynki a jedynki na zera. Kształt i zachowanie generowanych wzorów będzie bez zmian – zmieni się tylko ich kolor na przeciwny. Oczywiście oba przekształcenia można połączyć: odwrócić kolejność cyfr i zamienić kolory. Ponownie: nie wpłynie to na zachowanie reguły.

Podsumowując, istnieje tylko 88 istotnie różnych reguł, co trochę ułatwia ich klasyfikację. Dokonał jej Stephan Wolfram dzieląc reguły na cztery klasy:

  • Klasa 1. Reguły szybko prowadzące do taśmy jednolitego koloru (całej czarnej lub całej białej). Przykładem reguły 0, 32, 160 i 250.
  • Klasa 2. Reguły prowadzące do stanu stałego lub oscylującego. Stan stały oznacza, że wzór nie zmienia się z pokolenia na pokolenie a oscylujący oznacza, że co określoną liczbę pokoleń stan powtarza się. Przykładem reguły 4, 108, 218 i 232
  • Klasa 3. Reguły pozostające w stanie losowym. Przykładem reguły 22, 30, 126, 150, 182
  • Klasa 4. Reguły tworzące fragmenty losowe lub oscylujące ale także formy przenikające się lub wchodzące w zależności. Przykładem reguła 110

Najciekawsza jest klasa 4. Szczególnie reguła 110. Udowodniono bowiem, że za jej pomocą można przeprowadzać obliczenia. Co więcej można na jej podstawie zbudować system będący kompletny w sensie Turinga. Co oznacza kompletność Turinga? Alan Turing badał języki programowania. Starał się uprościć je pozostawiając jednakże możliwość tworzenia dowolnych programów i algorytmów. Stworzył maszynę Turniga (abstrakcyjną, bardzo prostą maszynę pozwalającą na jej programowanie przy użyciu nieskończonej taśmy) i dowiódł, że jest ona w stanie wykonać dowolnie skomplikowany algorytm (jest kompletna w sensie Turinga). Jeśli zatem uda się przy pomocy języka programowania zasymulować działanie maszyny Turinga to tym samym dowiedzie się, że tenże język jest kompletny w sensie Turinga.

Reguła 110 w połączeniu ze specjalnie dobranym stanem początkowym jest w stanie zasymulować maszynę Turinga. Mimo swej prostoty jest równoważna językom programowania używanym do pisania aplikacji. Można – odpowiednio kolorując taśmę – rozwiązać za jej pomocą dowolny problem, dla którego znamy algorytm. Oczywiście nie będzie to praktyczne rozwiązanie. Nawet tak proste zadanie jak dodanie dwóch liczb będzie wymagało bardzo wielu symboli na taśmie oraz setek tysięcy generacji. Jednak z punktu widzenia matematyki nie ma to znaczenia.

Odkrycie kompletności reguły 110 ma istotne implikacje. Oznacza to, że nawet tak wydawałoby się prymitywne mechanizmy mogą tworzyć bardzo skomplikowane struktury. Nie da się ich opisać prostą matematyczną formułą – trzeba zasymulować wszystkie pokolenia aby poznać wynik.

Analogiczne cechy wykazuje dwuwymiarowa wersja automatu komórkowego zwana grą w życie. Również za jej pomocą można zbudować maszynę Turinga. Ale to już opowieść na inną okazję.

Muzyka z automatów

Niestety nie każdemu dany jest słuch absolutny, mało kto potrafi też tworzyć muzykę. Istnieją na szczęście sposoby aby choć przez chwilę poczuć się jeśli nie Szopenem to choćby Jankiem Muzykantem. Otomata pozwala na półautomatyczne tworzenie dźwięków, które brzmią zaskakująco melodyjnie.

Do tworzenia muzyki zaprzęgnięto bardzo proste automaty komórkowe. Każda komórka może być w jednym z pięciu stanów: lewo, prawo, góra, dół i pusta. W następnym pokoleniu komórka przesuwa się zgodnie z kierunkiem strzałki. Gdy dotknie ściany zawraca i wydaje dźwięk. Gdy dotknie innej komórki obraca się o 90 stopni. Program nie działa idealnie ale jest na tyle funkcjonalny aby zapewnić dużo zabawy.

Tylko koni żal

Witam serdecznie.

Nam raczej te słowa, kojarzą się ze słowamo piosenki nomen omen “Dziś prawdziwych cyganów już nie ma”. Ale mnie od dzisiaj będą się już kojarzyły nie tylko w ten miły sposób. Jako że jesteśmy narodem, który nie odpowiada “tylko za gradobicie, trzęsienie ziemi i koklusz” to proponuję abyśmy przywdziali w końcu ten worek pokutny i udali się do Kanossy. Najwyższa pora.

Koniecznie przeczytajcie cały artykuł.

– Przeciw cywilom też. Atakowaliśmy konwoje na ulicach. Leciałem w “łańcuchu” (formacja trzech samolotów – red.). Samolot delikatnie przechylał się, a potem odbijaliśmy ostro w lewo, i waliliśmy ze wszystkich karabinów, które mieliśmy (na pokładzie – red.) (…) Czasem koło nas fruwały konie – opowiada o atakach pilot Pohl. – To okropne, z tymi końmi, przestań! – komentuje Meyer. – Koni było mi żal. Ludzi absolutnie nie. Ale koni było mi żal aż do końca – odpowiada Pohl.

źródło: Taśmy Wehrmachtu: jak żołnierze Hitlera opowiadali o wojnie.

 

Algorytmy sortowania

Nauczać informatyki można na różne sposoby. Najczęściej każe się uczniom przepisywać różnie sformatowany tekst w MS Wordzie (co nawiasem mówiąc z informatyką nie ma nic wspólnego). Można jednak uczyć algorytmiki (w tym wypadku algorytmów sortowania) w ciekawszy sposób – przez taniec. Polecam nawet dla tych, którzy zawodowo nie zajmują się komputerami.

Na zachętę jeden film, reszta tutaj.

Witaj miły poniedziałku

Prolog:

http://www.youtube.com/watch?v=-_uZ4S7YAzs&feature=related

Witam serdecznie,

tym bardziej serdecznie że kwiecień zaczął nam w rocznice obfitować. Mdli strasznie, ale co zrobić, człowiek zwymiotuje, a mdli dalej. Podobno jak ma się torsje, to trzeba dużo pić, żeby się nie odwodnić. Humphrey Bogart mawiał: „Kłopot ze światem jest taki, że jest on zawsze o trzy drinki do tyłu.” Franz był bardziej bezpośredni w stwierdzeniu: „A… kiedy świat na trzeźwo jest nie do przyjęcia…”. No i ostatnio nie opuszcza mnie takie wrażenie, że świat postawił sobie za punkt honoru, żeby nie zostać w tyle, a społeczeństwo postawiło sobie za punkt honoru, żeby go przyjąć z otwartymi rękami, bo podobno można nie pić, ale jeszcze nigdy nikt nie próbował. Czytaj dalej Witaj miły poniedziałku

Witaj miły poniedziałku czyli Łódź Obiecana

Prolog:

Odsłona I

Motto:

“To ja się leczę, ja nic nie robię, tylko sobie chodzę po Łodzi i patrzę, jak ona mi rośnie, to jest najlepsze lekarstwo na moją chorobę.”*

Witam serdecznie,

dzisiaj spróbuję rozpocząć nowy podcykl starego cyklu i chrzczę go mianem Poniedziałkowe Historyjki. Postanowiłem nie tworzyć nowego wątku-kategorii, co pozwoli, mam nadzieję, urozmaicić moje Poniedziałkowe wynurzenia, nie zanudzić Was doszczętnie, a przy okazji  nieść kaganek 🙂 Mam niejednokrotnie takie wrażenie, że swego do końca nie znacie (również ja dowiaduję się mnóstwa nowych, ciekawych rzeczy i najśmieszniejsze i najsmutniejsze jest to, że bez wielkiego wysiłku,  jedynie odrobiną chęci pchnięty do działania, choć wiecie jak to bywa z chęćmi naszymi i co nimi jest wybrukowane i jak to się przeważnie kończy, czyli tak jak polskie autostrady, lecz może w końcu uda się i nam, czego sobie i wam serdecznie z całego serca życzę), a jak poznacie, to cudzego bezmyślnie chwalić nie będziemy. Tak sobie teraz myślę, że chciałbym, aby Poniedziałkowe Historyjki odnosiły się głównie do Łodzi, ale kto wie, jak historyjka się potoczy. Aby uprościć nam zadanie, otagowałem dodatkowo moje dokonania na tej niwie słowami historyjki i Łódź, niech płynie dalej w świat. Na zakończenie króciutkiego wstępu, jedna podstawowa informacja, a właściwie dogmat i teraz jest dobry moment, żeby zakończyć – jest wiele łodzi na świecie, ale Łódź jest jedna, niepowtarzalna, przerażająco cudowna i okropnie wspaniała. Przepraszaliśmy za wszystko, za wszystkich, wystarczająco długo, wystarczająco cierpliwie i wystarczy. Pora rozwinąć żagle i wyruszyć w stronę Scylli i Charybdy, coby oskrobać nieco rybie ogony i przytkać fałszywe usteczka. Czytaj dalej Witaj miły poniedziałku czyli Łódź Obiecana