Elementarne automaty komórkowe Wolframa: 256 zasad i…

Definicja i kodowanie

Elementarny automat komórkowy (ECA) jest jednowymiarowym, dwustanowym, trójneighbourowym automatem komórkowym. Unwersum stanowi ciąg binarny — każda komórka zawiera 0 (biały) lub 1 (czarny) — a na każdym dyskretnym kroku każda komórka jednocześnie aktualizuje swoją wartość na podstawie siebie samej i jej bezpośrednich sąsiadów z lewej i prawej strony. Ponieważ każe sąsiedztwo ma 2³ = 8 możliwych konfiguracji, a reguła musi określić jedno z 2 wyjść dla każdego, istnieje 2⁸ = 256 możliwych reguł. Reguła 0 mapuje każe sąsiedztwo na 0 (wszystkie komórki umierają); reguła 255 mapuje każe sąsiedztwo na 1 (wszystkie komórki żyją w nieskończoność); reguły 30 i 110 stanowią końce spektrum skomplikowania.

Czytanie tabeli zasad

Aby odszyfrować zasady N, napisz N w postaci dwubitowej o 8 bitach. K-ta bit od prawej strony mówi, jaką wyjście produkuje sąsiadujący obszar wartości k numerycznej:

Zasada 110 = 01101110₂ sąsiadujący obszar: 111 110 101 100 011 010 001 000 wyjście: 0 1 1 0 1 1 1 0 Standardowa wizualizacja stosuje czas do dolnej strony — wiersz 0 to warunek początkowy (jedna czarna komórka na białym jest kanoniczny), wiersz 1 po jednym kroku, a dalej tak dalej. Z 256 zasad wielu są równoważne pod względem odbicia lub dopełnienia barw; po uwzględnieniu obu symetrii pozostaje tylko 88 prawdziwie różnych zasad. Zasada 30 i jej odzwierciedlenie, zasada 86, produkcją różne wzory, ale są tak samo skomplikowane; zasada 110 i zasada 137 są odzwierciedlaniem siebie.

Rule 110 = 01101110₂
neighbourhood: 111 110 101 100 011 010 001 000
output:          0   1   1   0   1   1   1   0

demo na żywo · powiązana symulacja● LIVE

Przezroczystość obliczeń dla zasady 110

Matthew Cook udowodnił w 1994 roku (publikacja w 2004 roku po rozstrzygnięciu prawnej sporu dotyczącego praw do publikacji) że zasada 110 może symulować system tagowy okresowy, znany jako układ rekonstrukcyjny Turinga. Wizyty przestrzenno-czasowe zasady 110 zawierają trwałe struktury poruszające się nazywane cząsteczkami wlozone w półtorakokreślonym tle okresowym o nazwie ether. Kluczowa myśl Cooka polegała na tym, że kolizje cząstek — około 16 typów interakcji — są wystarczająco bogate, aby symulować operacje dodawania i usuwania w systemie tagowym, gdzie ether działa jako pusta taśma a cząstki kodują symbole danych. Ponieważ dowolna maszyna Turinga może być zredukowana do niej, pytanie „czy zasada 110 zaczynając od warunku X kiedykolwiek wygeneruje 1 w jakiś miejscu?” jest nierozstrzygalne i równoważne problemowi haltowania — znakomita osiągnięcie dla zasady posiadającej tylko 8 dwubitowych stopni swobody.

Zasada 184 i przepływność ruchu

Nie każda znaną zasadę nie dotyczy chaosu ani obliczeń. Zasada 184 to minimalna modela ruchu pojazdów na jednopasmowej drodze: komórki reprezentują odcinki drogi, stan 1 oznacza obecność samochodu, a samochód porusza się w prawo, jeśli nastepny odcinek jest pusty, w przeciwnym razie pozostaje na miejscu. Zasada poprawnie powtarza fazę wolnego ruchu przy gęstości poniżej 0,5, formację szosowych zatłoczeń ponad tą granicą, fale szokowe propagujące się wstecz przez zatłoczenie oraz zachowanie liczby samochodów — najprostszy automat komórkowy, który wykazuje obie fazy pełniejszego modelu ruchu Nagel-Schreckenberg.

Odwracalne zasady i większe okolice

Zasada automatu komórkowego (CA) jest odwracalna, gdy każda stan ma dokładnie jednego przodka. Z 256 elementarnych zasad tylko Rule 51 (komplement) i Rule 204 (identyczność) są odwracalne — Toffoli i Margolus rozwinięli formalizm blokowych automatów komórkowych, aby konstruować odwracalne zasady 2D do modelowania czasowej odwrotnej fizyki. Wolfram również rozszerzył badania na k-kolorowe, promieniu r okolice: dla k=2 i promienia r=2 (pięcioelementowe okolica) jest około 4 miliarda zasad, a kod Wolframa generalizuje się w taki sam sposób — pravidło N mapuje konfigurację okolictwa i na bit i zasady N.

Często zadawane pytania

Jak odczytasz regułę Wolframa, jak np. reguła 110?

Zapisz numer reguły w postaci binarnej na 8 bitów. Reguła 110 to 01101110 w systemie dwójkowym. k-ta bit od prawej strony powinien wskazywać wyjście dla sąsiedztwa, którego 3-bitowy (lewo-środek-prawo) wzór wynosi k w systemie dwójkowym — więc sąsiedztwo 110 (które jest równe 6) czyta bit 6, który to 1, co oznacza, że sąsiedztwo wygeneruje komórkę żywe na następną generację. Wykonując ten proces dla wszystkich 8 możliwych sąsiedztw pełnościami określa regułę.

Dlaczego reguła 110 jest taka zaskakująca?

Reguła 110 ma tylko 8 stopni swobody binarnych — 8 bitów wyjściowych w tabeli reguły — jednak Matthew Cook udowodnił w 1994 roku (opublikowane w 2004 roku), że może symulować system tagowy cykliczny, rodzaj systemu zapisywania Turinga. To oznacza, że pytanie «czy reguła 110, rozpoczęta z warunkiem X, kiedykolwiek wygeneruje 1 w jakimś miejscu?» jest nieodludzalne, równoważne problemowi haltinga, mimo że sama reguła jest opisana jednym bajtem.

Co modeluje reguła 184?

Reguła 184 to minimalny model ruchu pojazdów na jednolinii: komórki reprezentują sekcje drogi, stan 1 oznacza obecność pojazdu, a pojazd porusza się w prawo tylko wtedy, gdy nastepna komórka jest pusta. Poprawnie powtarza zarówno fazę wolnego ruchu przy niskiej gęstości, jak i zatłoczoną fazę przy wysokiej gęstości, z propagowaniem fal zatoki wstecz i zachowaniem całkowitego licznika pojazdów — co sprawia, że jest to najprostsza automata komórkowy pokazujący obie fazy modelu ruchu Nagel-Schreckenberg'a.

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Wolfram 1D Cellular Automata — Elementary Rules & Complex Behaviour i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.

▶ Otwórz symulację Wolfram 1D Cellular Automata — Elementary Rules & Complex Behaviour

Elementarne automaty komórkowe Wolframa: 256 zasad i granica obliczeń