Automat celular elementar

Un automat celular elementar  este un automat celular cu o matrice unidimensională de celule sub forma unei benzi fără sfârșit pe ambele părți, care are două stări posibile de celule (0 și 1, „mort” și „viu”, „gol” și „umplut”) și o regulă pentru determinarea stării celulei în pasul următor, folosind doar starea celulei și a celor doi vecini ai săi în pasul curent. În general, astfel de automate sunt printre cele mai simple automate celulare posibile, cu toate acestea, în conformitate cu anumite reguli, prezintă un comportament complex; astfel, folosirea regulii 110 duce la un automat Turing-complet .

Codul Wolfram

În total, există combinații posibile între starea celulei și stările celor doi vecini ai săi. Regula care definește automatul celular elementar trebuie să indice următoarea stare (0 sau 1) pentru fiecare dintre aceste cazuri posibile, deci numărul total de reguli . Stephen Wolfram a propus o schemă de numerotare pentru aceste reguli, cunoscută sub numele de codul Wolfram , care mapează fiecare regulă la un număr între 1 și 255. Acest sistem a fost publicat pentru prima dată de Wolfram într-o lucrare din 1983 [1] și a fost folosit ulterior în cartea sa A. Nou tip de știință ” ( Ing. Știință de un nou tip ). [2]  

Pentru a obține codul Wolfram, trebuie să notați configurațiile posibile (111, 110, ..., 001, 000) în ordine descrescătoare, să scrieți stările corespunzătoare sub ele și să interpretați succesiunea rezultată de zerouri și unu ca număr. în sistemul numeric binar . De exemplu, următoarea schemă are ca rezultat codul corespunzător regulii 110 :

Reflecții și completări

Unele dintre cele 256 de reguli sunt trivial echivalente între ele datorită prezenței a două tipuri de transformări. Prima este o reflecție despre axa verticală, în care vecinii din stânga și din dreapta sunt schimbati și se obține o regulă în oglindă .  De exemplu, regula 110 devine regula 118:

Printre cele 256 de reguli, există 64 simetrice în oglindă ( ing.  amphichiral ).

Al doilea tip de transformare este înlocuirea rolurilor 0 și 1 din definiție, care dă o regulă suplimentară ( regulă complementară engleză  ). De exemplu, regula 118 devine regula 137:

Doar 16 reguli din 256 coincid cu adăugările lor. Până la această pereche de transformări (inclusiv cele aplicate simultan - ordinea nu este importantă), există 88 de automate celulare elementare neechivalente. [3]

Metode de cercetare

Cea mai simplă configurație

Una dintre metodele de studiu a automatelor celulare elementare este de a lua în considerare evoluția celei mai simple configurații inițiale, adică constând dintr-o singură celulă vie (conținând 1). Dacă regula are un cod Wolfram uniform, atunci nu există o generație spontană de viață (combinația 000 nu dă 1 la mijloc în generația următoare) și, prin urmare, fiecare stare din cea mai simplă configurație are un număr finit de non-zero. celule și poate fi interpretat ca un număr în notație binară.[ cum? ] Secvența acestor numere definește o funcție generatoare , care este rațională , adică raportul a două polinoame și are adesea o formă relativ simplă.

Configurații aleatorii

De asemenea, este util să se ia în considerare evoluția configurațiilor inițiale aleatoare. Pentru a face acest lucru, există o împărțire în următoarele clase informale de automate celulare , inventate de Wolfram: [4]

• Clasa 1: Converge rapid la o stare de toate zerourile sau unurile. Wolfram citează ca exemple regulile 0, 32, 160, 232.
• Clasa 2: converge rapid la o stare ciclică sau stabilă . De exemplu, regulile 4, 108, 218, 250.
• Clasa 3: Stocat într-o stare aleatorie. De exemplu, regulile 22, 30 , 126, 150, 182.
• Clasa 4: Se formează ambele regiuni cu stări ciclice sau stabile, precum și structuri care interacționează între ele în moduri complexe. Un exemplu este regula 110 , care este Turing complet .