Sierpiński i automat numer 90

https://xpil.eu/f4w

Dawno, dawno temu pisałem o algorytmie Game Of Life. O, tutaj można poczytać: !klik!.

Game of Life to automat komórkowy. Kolejne generacje są tworzone na podstawie ściśle ustalonych reguł oraz odpowiednio dobranego ustawienia początkowego.

Jest to automat komórkowy dwuwymiarowy; świat rozciąga się w dwa poprzeki: wzdłużny i wpoprzeczny.

A co, jeżeli zredukujemy ilość wymiarów i zamiast płaszczyzny weźmiemy na warsztat linię?

Okazuje się, że tu też można skonstruować rozmaite automaty komórkowe. Najprostszy z nich wygląda tak, że startujemy od pojedynczej poziomej linii wypełnionej komórkami (każda komórka ma wartość 1 lub 0) a każa następna linia składa się z komórek wyliczonych na podstawie trzech górnych sąsiadów.

Jak konkretnie wyliczonych?

A to już zależy tylko i wyłącznie od nas.

Można na przykład przyjąć regułę, że jeżeli co najmniej dwie z trzech komórek powyżej są równe 1, komórka poniżej też jest 1, w przeciwnym przypadku - 0.

Efekt?

Dość banalny, okazuje się. Po kilku pierwszych pokoleniach sytuacja stabilizuje się, kolejne pokolenia są identyczne do swoich poprzedników. W efekcie dostajemy nudne, pionowe pasy.

Spróbujmy zapisać powyższą regułę w bardziej sformalizowanej postaci. Każdej kombinacji trzech bitów wejściowych odpowiada jeden bit wyjściowy. Czyli:

000 => 0
001 => 0
010 => 0
011 => 1
100 => 0
101 => 1
110 => 1
111 => 1

Upraszczając (ale bez utraty szczegółowości) możemy powyższy automat zapisać jako 00010111, czyli po przeliczeniu na układ dziesiętny: 23.

Automat numer 23 działa więc według reguły mówiącej, że w kolejnym pokoleniu komórka pojawia się tam, gdzie jest co najmniej dwóch rodziców.

Czy można sobie wyobrazić inne takie atomaty?

Oczywiście! Po prawej stronie strzałek może pojawić się dowolna ośmioelementowa kombinacja zer i jedynek. A więc 256 różnych automatów, z których jeden właśnie sobie obejrzeliśmy.

Temat jest dość rozległy, a nie chcę doprowadzić do zaśnięcia tych Czytelników, którzy jakimś cudem jeszcze nie przycięli komara. Przejdę więc od razu do samego gęstego, czyli do automatu numer 90.

90 to binarnie 01011010.

Rozkładając to na poszczególne kombinacje bitów, dostajemy:

000 => 0
001 => 1
010 => 0
011 => 1
100 => 1
101 => 0
110 => 1
111 => 0

Jak na razie nudy.

Nic się nie dzieje.

Koń, krowa, kura, kaczka... Kura, kaczka, drób...

Droga!

Chyba na Ostrołękę...

Żeby tę nudę nieco zniwelować, dodajmy do powyższego automatu jeszcze jeden warunek: w pierwszym pokoleniu jest tylko jedna komórka. A więc: dłuuuuuga linia z jedną kropką.

Co się dalej wydarza?

Wydarzają się czary.

Okazuje się, że tak zdefiniowany automat komórkowy generuje nam w kolejnych pokoleniach trójkąt Sierpińskiego!

Czysta magia.

Temat, po raz kolejny, zerżnięty z blogu Johna D. Cooka: https://www.johndcook.com/blog/2017/09/23/sierpinski-triangle-strikes-again/

https://xpil.eu/f4w

5 komentarzy

      1. Ty, to umiesz podnieść na duchu, nie ma co. Chociaż w tych oko-licznościach przyrody, tylko duch pozostał, chociażby epoki (i epiki, ale to przecież dramat- nie tylko mat-ematyka) 😀 Ale mam jeszcze jednego matematyka w zamyśle, od trzech lat, i chyba o nim w końcu wspomnę.

  1. można też zapisać generowanie tego trójkąta za pomocą funkcji logicznej: Y = A xor C, czyli Y nie zależy od sygnału B

Leave a Comment

Komentarze mile widziane.

Jeżeli chcesz do komentarza wstawić kod, użyj składni:
[code]
tutaj wstaw swój kod
[/code]

Jeżeli zrobisz literówkę lub zmienisz zdanie, możesz edytować komentarz po jego zatwierdzeniu.