Despre automatele celulare | Jocul vieții, Regula 30, Regula 110 și altele

Cele patru părți de bază

Orice automat celular este construit din aceleași patru părți. Grila este spațiul în care trăiesc celulele. Poate fi o linie unidimensională, un plan bidimensional ca o tablă de șah sau chiar un spațiu tridimensional. Stările sunt ceea ce poate fi o celulă. În cazul cel mai simplu, o celulă este binară: neagră sau albă, 1 sau 0. Vecinătatea este mulțimea celulelor care influențează direct o celulă. Pe o grilă pătrată este de obicei vecinătatea Moore, toate cele opt celule din jur, sau vecinătatea von Neumann, doar nord, est, sud și vest. Regulile sunt creierul automatului: logica ce dă fiecărei celule noua ei stare. De exemplu: dacă sunt vie, dar am mai puțin de doi vecini vii, mor de singurătate. Fiecare celulă aplică aceleași reguli în același moment.

1. Jocul vieții al lui Conway

Reguli: B3/S23. O celulă vie supraviețuiește cu 2 sau 3 vecini vii. O celulă moartă prinde viață cu exact 3. Orice altă celulă este moartă în generația următoare. John Conway l-a conceput în 1970, iar rubrica lui Martin Gardner din Scientific American l-a făcut celebru. Produce planoare, oscilatoare și nave spațiale. Bill Gosper a găsit în același an primul tun de planoare: un model care lansează un planor nou la fiecare 30 de generații, la nesfârșit. Jocul vieții poate efectua calcule, pentru că planoarele pot transporta semnale și se pot ciocni ca niște porți logice. Mai presus de toate, arată cum un comportament complex crește din reguli simple.

Tunul de planoare al lui Gosper din Jocul vieții, care lansează un șir diagonal de planoare — Tunul de planoare al lui Gosper după 330 de generații. Randat în PictorX.

2. Regula 30

Tip: un automat celular elementar unidimensional. Starea următoare a fiecărei celule depinde de ea însăși și de cei doi vecini ai ei, iar fiecare generație este desenată ca un rând nou sub cel anterior. Stephen Wolfram a introdus Regula 30 în 1983. Pornește de la o singură celulă neagră și din ea crește un triunghi haotic. Pare aleatoare în ciuda regulii deterministe, atât de aleatoare încât coloana ei din mijloc a fost folosită ca generator de numere pseudoaleatoare. Același tip de triunghiuri apare în pigmentul cochiliei melcului marin Conus textile.

Triunghiul Regulii 30 crescut dintr-o singură celulă neagră, haotic în dreapta și dungat în stânga — Regula 30 dintr-o celulă neagră, 224 de generații. Randat în PictorX.

3. Regula 110

Tip: un automat celular elementar unidimensional, ca Regula 30, dar cu un alt tabel de opt răspunsuri. S-a demonstrat că Regula 110 este universală din punct de vedere computațional: Matthew Cook a arătat că, pornind de la un prim rând potrivit, poate emula orice calcul pe care îl poate efectua un calculator de uz general. În ea apar structuri mobile care se deplasează pe un fundal care se repetă și interacționează când se întâlnesc. Aceste ciocniri sunt cele pe care demonstrația le folosește drept logică. Regula 110 arată cum reguli foarte simple pot emula calcule arbitrare.

Regula 110 crescută dintr-o celulă din dreapta, extinzându-se spre stânga în triunghiuri imbricate — Regula 110 dintr-o celulă neagră de pe marginea din dreapta. Randat în PictorX.

4. Brian's Brain

Stări: stinsă, aprinsă (activă) și refractară. Reguli: o celulă stinsă se aprinde dacă exact 2 vecini sunt aprinși. O celulă aprinsă devine refractară. O celulă refractară se stinge. L-a conceput Brian Silverman. Pentru că o celulă trebuie să se odihnească o generație după ce devine activă, fiecare impuls se îndepărtează mereu de locul în care a fost. Rezultatul este o mulțime de modele care se deplasează singure și seamănă cu undele din mediile excitabile, precum țesutul nervos sau mușchiul cardiac, și care arată adesea vii și organice.

Brian's Brain extinzându-se dintr-o pată aleatoare, cu celulele active în galben și urmele care se estompează în violet — Brian's Brain la 70 de generații după o pată aleatoare, cu urme care se estompează. Randat în PictorX.

5. Wireworld

Stări: gol, cap de electron, coadă de electron și conductor. Reguli: un cap devine coadă, o coadă devine conductor, iar un conductor devine cap când exact 1 sau 2 dintre vecinii lui sunt capete. Celulele goale rămân goale. Tot Brian Silverman a conceput Wireworld, în 1987. Celulele conductoare sunt fire, iar un cap urmat de o coadă este un electron care aleargă de-a lungul lor. Poate simula circuite electronice: o buclă de fir cu un electron este un ceas, o mică crestătură este o diodă, iar câteva celule formează o poartă logică. În el au fost construite calculatoare complete, precum calculatorul Wireworld al lui David Moore și Mark Owen, care calculează numere prime.

Circuit Wireworld cu două bucle de ceas, două diode și o poartă XOR, cu electroni albaștri și roșii pe fir galben — Două ceasuri, două diode și o poartă XOR în Wireworld. Randat în PictorX.

Cele 256 de reguli și cele patru clase ale lui Wolfram

O celulă unidimensională cu doi vecini vede unul dintre opt modele, de la 111 până la 000. O regulă dă noua stare pentru fiecare dintre ele, deci are opt biți, și există 2⁸ = 256 de reguli elementare. Citește cele opt răspunsuri ca pe un număr binar și obții numele regulii: Regula 30 este 00011110, iar Regula 110 este 01101110. Stephen Wolfram a ordonat regulile după ce fac, de la ordine la haos. 1. Clasa 1 ajunge la o stare uniformă. 2. Clasa 2 ajunge la structuri stabile sau care se repetă. 3. Clasa 3 rămâne haotică și pare aleatoare, ca Regula 30. 4. Clasa 4 construiește structuri care se mișcă și interacționează la granița dintre ordine și haos, ca Regula 110.

Clasament după dificultate

Jocul vieții ★☆☆☆☆ · Regula 30 ★☆☆☆☆ · Brian's Brain ★★☆☆☆ · Wireworld ★★★★☆ · Regula 110 ★★★★★. Primele două se explică singure în timp ce le urmărești. Regula 110 își ascunde structurile mobile într-un fundal care se repetă.

Cele mai frumoase vizual

1. Brian's Brain · 2. Jocul vieții al lui Conway · 3. Regula 30 · 4. Regula 110 · 5. Wireworld.

Cele mai importante matematic

1. Regula 110, pentru universalitate · 2. Jocul vieții, pentru universalitate și emergență · 3. Regula 30, pentru haos și caracter aleatoriu · 4. Wireworld, pentru logica digitală · 5. Brian's Brain, pentru sistemele excitabile.

În natură, fizică și criptografie

Automatele celulare sunt folosite pentru a simula sisteme complexe din natură, fizică și criptografie. Ideea vine de la Stanisław Ulam și John von Neumann, care în anii 1940 au folosit o grilă de celule pentru a proiecta o mașină capabilă să se copieze singură. În lumea reală poți vedea automate celulare în pigmentul unor cochilii, precum cea a melcului Conus textile, ale cărei triunghiuri seamănă cu Regula 30, și în solzii șopârlei ocelate, care comută între verde și negru după o regulă apropiată de un automat celular. Fizicienii le folosesc pentru a modela curgerea gazelor, grămezile de nisip și incendiile de pădure. Caracterul aparent aleatoriu al Regulii 30 a făcut din ea o candidată pentru generatoare de numere aleatoare și cifruri flux.

Explorează-le în PictorX

Deschide Automate celulare ca să le rulezi pe toate cinci. Urmărește tunul de planoare, o flotă de nave spațiale sau R-pentomino-ul, care are nevoie de 1.103 generații ca să se stabilizeze. Scrie orice regulă de tip Life, precum B36/S23, sau orice număr de regulă elementară de la 0 la 255. Desenează și șterge celule, trimite electroni prin circuitele Wireworld, unește marginile și treci la modul colorat. Salvează un PNG sau deschide pânza în editorul PictorX.

Întrebări frecvente

Ce este un automat celular?

O grilă de celule în care fiecare celulă are o stare. La fiecare pas toate celulele se actualizează împreună după o singură regulă fixă, care se uită doar la o celulă și la vecinii ei. În ciuda regulilor simple, modelele pot fi complexe și imprevizibile.

Cine a inventat automatele celulare?

Stanisław Ulam și John von Neumann, în anii 1940, la Los Alamos. Jocul vieții al lui John Conway (1970) a făcut ideea populară, iar Stephen Wolfram a studiat cele 256 de reguli elementare în anii 1980.

Care automate celulare sunt Turing-complete?

Dintre cele cinci de aici, s-a demonstrat că Regula 110 și Jocul vieții sunt universale, iar Wireworld poate găzdui un calculator complet. Universal înseamnă că, pornind de la modelul inițial potrivit, pot efectua orice calcul pe care îl poate face un calculator de uz general.

Care sunt cele patru clase ale lui Wolfram?

Clasa 1 se stinge într-o stare uniformă, clasa 2 ajunge la structuri stabile sau care se repetă, clasa 3 rămâne haotică precum Regula 30, iar clasa 4 construiește structuri mobile care interacționează, precum Regula 110.

De ce pare aleatoare Regula 30?

Fiecare pas este fix, dar fiecare celulă își amestecă vecinul din stânga cu celelalte două într-un mod care răspândește repede micile diferențe. În coloana ei din mijloc nu s-a găsit niciun model simplu, de aceea a fost folosită pentru a genera numere aleatoare.