Wikipedia

Jocul Vieții al lui Conway

automat celular inventat de J.H. Conway în 1970

Jocul Vieții este un automat celular conceput de matematicianul britanic John Horton Conway în 1970.[1] Este un joc fără jucători,[2][3] în sensul că evoluția sa este determinată de starea sa inițială, nefiind nevoie de nicio intervenție suplimentară. Interacțiunea cu Jocul Vieții constă în crearea unei configurații inițiale și observarea cum evoluează. Este Turing-complet⁠(d) și poate simula un constructor universal von Neumann⁠(d) sau orice altă mașină Turing.

Un tun care lansează glidere conceput de Bill Gosper
O captură de ecran a unui pufăitor (roșu) care lasă în urma sa tunuri (verzi) care lansează glidere (albastre) (animație)

Reguli

modificare

Universul Jocului Vieții este o grilă ortogonală infinită, bidimensională, cu celule pătrate, fiecare dintre acestea fiind într-una dintre cele două stări posibile, vie sau moartă (sau populată, respectiv nepopulată). Fiecare celulă interacționează cu cele opt celule învecinate, care sunt celulele care sunt adiacente orizontal, vertical sau diagonal. La fiecare pas în timp, au loc următoarele schimbări:

  1. Orice celulă vie cu mai puțin de doi vecini vii moare, datorită subpopulării.
  2. Orice celulă vie cu doi sau trei vecini vii trăiește în generația următoare.
  3. Orice celulă vie cu mai mult de trei vecini vii moare, datorită suprapopulării.
  4. Orice celulă moartă cu exact trei vecini vii devine o celulă vie, datorită reproducerii.

Jocul începe prin inițializarea sistemului cu un model, modelul inițial. Prima generație este creată prin aplicarea regulilor de mai sus simultan la fiecare celulă, vie sau moartă, din modelul inițial. Nașterile și decesele au loc simultan, iar momentul discret în care se întâmplă acest lucru este uneori numit tact.[a] Fiecare generație este o funcție pură⁠(d) a stării precedente. Regulile se aplică repetat pentru a crea generațiile următoare.

Origine

modificare

Stanislaw Ulam, în timp ce lucra la Laboratorul Național Los Alamos în anii 1940, a studiat creșterea cristalelor, folosind ca model o simplă rețea cristalină.[7] În același timp, John von Neumann, colegul lui Ulam la Los Alamos, lucra la problema sistemelor de autoreplicare⁠(d).[8] Modelul inițial al lui Von Neumann a fost fondat pe ideea că un robot construiește un alt robot. Acest model este cunoscut sub numele de modelul cinematic.[9][10] Pe măsură ce a dezvoltat acest model, von Neumann a ajuns să-și dea seama de marea dificultate de a construi un robot cu autoreplicare și de costul mare în furnizarea robotului cu un ocean de piese din care să-și construiască replicantul. Neumann a scris o lucrare intitulată The general and logical theory of automata pentru Simpozionul Hixon din 1948.[8] Ulam a fost cel care a sugerat utilizarea unui sistem discret pentru crearea unui model simplu de autoreplicare.[8][11] Ulam și von Neumann au creat la sfârșitul anilor 1950 o metodă pentru calcularea mișcării unui lichid. Ideea metodei a fost de a considera lichidul ca un grup de unități discrete și de a calcula mișcarea fiecăreia pe baza comportamentelor vecinilor săi.[12] Astfel s-a născut primul sistem de automate celulare. La fel ca și rețeaua lui Ulam, automatele celulare Von Neumann sunt bidimensionale, cu autoreplicatorul său implementat algoritmic. Rezultatul a fost constructorul universal Von Neumann care lucrează într-un automat celular cu o vecinătate mică (doar acele celule care se ating sunt vecine; pentru automatele celulare ale lui von Neumann doar celule ortogonale), și cu 29 de stări pe celulă. Von Neumann a demonstrat că există modele care fac copii ale lor însele la nesfârșit în cadrul universului celular dat prin proiectarea unei configurații de 200 000 de celule care ar putea face acest lucru. Acest model este cunoscut ca modelul de teselare și se numește constructor universal von Neumann.[13]

Motivat de chestiuni din logica matematică și parțial de munca la jocurile de simulare a lui Ulam, printre altele, John Conway a început să facă experimente în 1968 cu o varietate de automate celulare bidimensionale cu diferite reguli. Scopul inițial al lui Conway a fost acela de a defini un automat celular interesant și imprevizibil.[3] Potrivit lui Martin Gardner, Conway a experimentat cu diferite reguli, urmărind să permită modelelor să crească „aparent” fără limită, însă fără ca demonstrația că orice model ar face acest lucru să fie ușoară. Mai mult, unele „modele inițiale simple” ar trebui „să crească și să evolueze o perioadă considerabilă de timp” înainte de a ajunge într-o configurație statică sau într-o buclă care se repetă.[1] Ulterior Conway a scris motivația de bază a fost crearea unui automat celular „universal”.[14]

Jocul și-a făcut prima apariție publică în numărul din octombrie 1970 al revistei Scientific American, la rubrica „Mathematical Games” a lui Martin Gardner, care s-a bazat pe discuții personale cu Conway. Teoretic, Jocul Vieții are puterea unei mașini Turing universale⁠(d): orice poate fi calculat algoritmic, poate fi calculat în cadrul Jocului Vieții.[2][15] Gardner a scris: „Din cauza analogiilor vieții cu ascensiunea, decăderea și schimbările dintr-o societate de organisme vii, acesta aparține unei clase în creștere a ceea ce se numesc «jocuri de simulare» (jocuri care seamănă cu procese din viața reală).”[1]

De la publicarea sa, Jocul Vieții a stârnit mult interes din cauza modurilor surprinzătoare în care modelele pot evolua. Acesta oferă un exemplu de emergență⁠(d) și autoorganizare.[3] O versiune a jocului care are fluctuații aleatoare a fost folosită în fizică pentru a studia transformările de fază și dinamica stărilor fără echilibru.[16] Jocul poate servi și ca o analogie didactică, folosită pentru a transmite noțiunea oarecum neintuitivă că organizarea poate apărea spontan în absența unui organizator. De exemplu, filosoful Daniel Dennett a folosit pe scară largă analogia cu „universul” Jocului Vieții pentru a ilustra posibila evoluție a construcțiilor filosofice complexe, cum ar fi conștiința și liberul arbitru, dintr-un set relativ simplu de legi fizice deterministe care ar putea guverna universul nostru.[17][18][19]

Popularitatea Jocului Vieții a fost ajutată de apariția sa în același timp cu accesul la computer din ce în ce mai ieftin. Jocul ar putea rula ore întregi pe aceste mașini, care altfel ar fi fost nefolosite noaptea. În acest sens, a prefigurat popularitatea ulterioară a fractalilor generați pe computer. Pentru mulți, Jocul Vieții a fost pur și simplu o provocare de programare: o modalitate distractivă de a folosi cicluri ale CPU, altfel nefolosite. Pentru unii, Jocul Vieții avea mai multe conotații filosofice. A dezvoltat un cult prin anii 1970 și ulterior. Evoluțiile actuale au mers atât de departe încât au creat emulări teoretice ale sistemelor informatice în limitele unei table cu Jocul Vieții.[20][21]

Exemple de modele

modificare

În Jocul Vieții apar multe tipuri diferite de modele, care sunt clasificate în funcție de comportamentul lor. Tipurile obișnuite de modele includ: naturi moarte, care nu se schimbă de la o generație la alta; oscilatoare, care revin la starea lor inițială după un număr finit de generații; și nave spațiale, care se se translează în grilă.

Cele mai vechi modele interesante din Jocul Vieții au fost descoperite fără utilizarea computerelor. Cele mai simple naturi moarte și oscilatoare au fost descoperite în timpul urmăririi destinelor diferitelor configurații de pornire mici folosind hârtie milimetrică și table de joc fizice, cum ar fi cele folosite în Go. În timpul acestei cercetări timpurii, Conway a descoperit că R-pentomino nu a reușit să se stabilizeze într-un număr mic de generații. De fapt, este nevoie de 1103 generații pentru a se stabiliza, timp în care are o populație de 116 și a generat șase glidere, care evadează,[22] acestea fiind primele „nave spațiale” descoperite.[23]

Frecvent apar[24][25] exemple (prin faptul că acestea apar frecvent din configurații aleatorii de pornire a celulelor) dintre cele trei tipuri de modele menționate mai sus sunt prezentate mai jos, cu celule vii prezentate în negru și celule moarte în alb. „Perioada” se referă la numărul de pași prin care un model trebuie să treacă înainte de a reveni la configurația sa inițială.

Pulsarul[26] este cel mai comun oscilator cu perioada 3. Marea majoritate a oscilatoarelor care apar în mod natural au o perioadă de 2, cum ar fi semaforul și broasca, dar se știe că există oscilatoare cu orice perioade,[27] și s-a văzut că apar din condiții inițiale aleatorii oscilatoare cu perioadele 4, 8, 14, 15, 30 și alte câteva.[28]

Modelele care au perioade lungi înainte de stabilizare se numesc Matusalem, dintre care primul descoperit a fost R-pentomino. Diehard este un model care în cele din urmă dispare în loc să se stabilizeze, după 130 de generații, care s-a conjecturat că este maximul pentru modelele cu șapte sau mai puține celule.[29] Acorn durează 5206 generații, generând 633 de celule, inclusiv 13 glidere care evadează.[30]

 
R-pentomino
 
Diehard
 
Acorn

Conway a conjecturat inițial că niciun model nu poate crește la infinit — adică pentru orice configurație inițială cu un număr finit de celule vii, populația nu poate crește dincolo de o limită superioară finită. La apariția inițială a jocului în „Mathematical Games”, Conway a oferit un premiu de cincizeci de dolari (echivalent cu $320 in 2017) primei persoane care a putut demonstra sau infirma conjectura înainte de sfârșitul anului 1970. Premiul a fost câștigat în noiembrie de o echipă de la Massachusetts Institute of Technology, condusă de Bill Gosper. „Tunul cu glidere Gosper” produce primul glider la generația a 15-a și câte un alt glider la fiecare a 30-a generație de atunci. Timp de mulți ani, acest tun cu glidere a fost cel mai mic astfel de automat cunoscut.[31] În 2015, s-a descoperit un alt tun, numit „tunul cu glidere Simkin”, care generează câte un glider la fiecare a 120-a generație, care are mai puține celule vii, dar ale cărui extremități se întind într-un dreptunghi mai mare.[32]

 
Tunul cu glidere Gosper
 
Tunul cu glidere Simkin

Ulterior au fost găsite modele mai mici care prezintă și o creștere infinită. Toate cele trei modele prezentate mai jos cresc nelimitat. Primele două creează un singur motor de comutare la așezarea blocurilor: o configurație care lasă în urmă blocuri de natură moartă două câte două, pe măsură ce se deplasează în universul jocului.[33] A treia configurație creează două astfel de modele. Primul are doar zece celule vii, ceea ce s-a demonstrat că este un minim.[34] Al doilea se încadrează într-un pătrat de cinci pe cinci, iar al treilea are înălțimea de o singură celulă.

       

 

Ulterior au fost descoperite tunuri, care sunt staționare și care produc glidere sau alte nave spațiale. Pufăitori, care se deplasează de-a lungul universului lăsând în urmă o dâră de resturi; și grebla, care se mișcă și emit nave spațiale.[35] Tot Gosper a construit primul model cu un algoritm optim asimptotic⁠(d) cu rata de creștere pătratică, numit crescător, care a funcționat lăsând în urmă o urmă de tunuri.

Este posibil ca gliderele să interacționeze cu alte obiecte în moduri interesante. De exemplu, dacă două glidere se ciocnesc într-un bloc într-o anumită poziție, blocul se va apropia mai mult de sursa gliderelor. Dacă trei glidere se ciocnesc în modul corect, blocul se va îndepărta mai mult. Această „memorie bloc alunecător” poate fi folosită pentru a simula un contor⁠(d). Este posibil să se construiască porți logice, cum ar fi ȘI, SAU și NU folosind glidere. Este posibil să se construiască un model care acționează ca un automat finit conectat la două contoare. Acesta are aceeași putere de calcul ca o mașină Turing universală, astfel încât Jocul Vieții este teoretic la fel de puternic ca orice computer cu memorie nelimitată și fără constrângeri de timp; este Turing-complet.[15][2] De fapt, în Jocul Vieții au fost implementate câteva arhitecturi de computere programabile,[36][37] inclusiv un model care simulează jocul Tetris.[38]

Mai mult, un model poate conține o colecție de tunuri care trag cu glidere astfel încât să construiască noi obiecte, inclusiv copii ale modelului original. Se poate construi un constructor universal care conține un computer Turing-complet și care poate construi multe tipuri de obiecte complexe, inclusiv mai multe copii ale lui însuși.[2]

În 2018 a fost descoperită de Adam P. Goucher prima navă-cal (în engleză knightship) cu adevărat elementară, Sir Robin.[39] O navă-cal este o navă spațială care se mișcă două pătrate la stânga pentru fiecare pătrat în jos (ca un cal la șah), spre deosebire de mișcarea ortogonală sau de-a lungul unei diagonale (la 45°). Acesta este primul model nou de mișcare a unei nave spațiale pentru o navă spațială elementară găsit în patruzeci și opt de ani. „Elementar” înseamnă că nu poate fi descompusă în modele de interacțiune mai mici, cum ar fi gliderele și naturile moarte.[40]

Indecidabilitate

modificare

Multe modele din Jocul Vieții devin în cele din urmă o combinație de naturi moarte, oscilatoare și nave spațiale. Alte modele pot fi numite haotice. Un model poate rămâne haotic pentru o perioadă foarte lungă, până când în cele din urmă ajunge la o astfel de combinație.

Jocul Vieții este indecidabil⁠(d), ceea ce înseamnă că, având în vedere un model inițial și un model ulterior, nu există niciun algoritm care să poată spune dacă modelul ulterior va apărea vreodată. Având în vedere că Jocul Vieții este Turing-complet, acesta este un corolar al problemei opririi⁠(d): problema de a determina dacă un anumit program se va opri din rulat sau va continua să ruleze pentru totdeauna pornind de la o intrare inițială.[2]

modificare

Până în anii 2010, toate navele spațiale cunoscute se puteau mișca doar ortogonal sau diagonal, în timp ce existența unor modele în mișcare care se mișcă precum caii la șah a fost prezisă de Berlekamp încă din 1982. Navele spațiale care nu se mișcă nici ortogonal, nici diagonal sunt numite de obicei nave spațiale oblice.[41][42] La 18 mai 2010, Andrew J. Wade a anunțat prima navă spațială oblică, numită „Gemini”, care creează o copie a sa pe (5,1) în continuare, în timp ce își distruge părintele.[43][42] Acest model se repetă în 34 de milioane de generații și folosește o bandă de instrucțiuni făcută din glidere care oscilează între două configurații stabile din brațe de construcție de tip Chapman-Greene. Acestea, la rândul lor, creează noi copii ale modelului și distrug copia anterioară. În decembrie 2015, au fost construite versiuni diagonale ale Gemini.[44]

Autoreplicare

modificare

În 23 noiembrie 2013, Dave Greene a construit primul replicator din Jocul Vieții care creează o copie completă a lui, inclusiv banda de instrucțiuni.[45] În octombrie 2018 Adam P. Goucher a terminat construcția metacelulei sale 0E0P, o metacelulă capabilă de autoreplicare. Aceasta a fost diferită de metacelulele anterioare, cum ar fi metapixelul OTCA de Brice Due, care a funcționat doar cu copii deja construite în apropierea lor. Metacelula 0E0P funcționează folosind brațe de construcție pentru a crea copii care simulează regula programată.[46] Simularea reală a Jocului Vieții sau a altor reguli în vecinătatea Moore se realizează prin simularea unei reguli echivalente folosind vecinătatea von Neumann cu mai multe stări.[47] Denumirea 0E0P este prescurtarea pentru „Zero Encoded by Zero Population”, ceea ce indică faptul că, în loc ca o metacelulă să fie într-o stare off care simulează spațiul gol, metacelula 0E0P se șterge atunci când celula intră în acea stare, lăsând un spațiu gol.[48]

Iterații

modificare

La majoritatea modelelor inițiale aleatorii de celule vii de pe grilă, observatorii vor descoperi că populația se schimbă constant pe măsură ce generațiile trec. Modelele care apar din regulile simple pot fi considerate o formă de frumusețe matematică⁠(d). Submodele mici, izolate, fără simetrie inițială, tind să devină simetrice. Odată ce se întâmplă acest lucru, simetria poate deveni mai bogată, dar nu se poate pierde decât dacă un submodel din apropiere se apropie suficient de mult pentru a o perturba. În foarte puține cazuri, societatea se stinge în cele din urmă, cu toate celulele vii dispărând, deși acest lucru s-ar putea să nu se întâmple timp de multe generații. Cele mai multe modele inițiale se epuizează în cele din urmă, producând fie figuri stabile, fie modele care oscilează pentru totdeauna între două sau mai multe stări.[49][50] De asemenea, multe produc unul sau mai multe glidere sau nave spațiale care călătoresc la nesfârșit departe de locația inițială. Din cauza regulilor bazate pe cel mai apropiat vecin, nicio informație nu poate călători prin grilă cu o viteză mai mare de o celulă pe unitatea de timp, așa că se spune că această viteză este viteza luminii automatelor celulare⁠(d) și este notată cu c.

Algoritmi

modificare

Modelele timpurii cu evoluție necunoscută, cum ar fi R-pentomino, i-au determinat pe programatori să scrie programe pentru a urmări evoluția modelelor în Jocul Vieții. Majoritatea primilor algoritmi erau similari: ei reprezentau modelele în memoria computerului prin matrici bidimensionale. De obicei sunt utilizate două matrici: una pentru a păstra generația curentă și cealaltă pentru a calcula succesoarea acesteia. Adesea 0 și 1 reprezintă celule moarte, respectiv, vii. O buclă for⁠(d) examinează elementele matricii curente, numărând vecinii vii ai fiecărei celule pentru a decide dacă elementul corespunzător al matricii succesoare ar trebui să fie 0 sau 1. Matricea succesoare este afișată. Pentru următoarea iterație, matricile își pot interschimba rolurile astfel încât matricea succesoare din ultima iterație să devină matricea curentă în următoarea iterație, sau se pot copia valorile celei de-a doua matrice în prima.

Sunt posibile o serie de îmbunătățiri minore ale acestei scheme de bază și există multe modalități de a economisi calculele inutile. O celulă care nu s-a schimbat la ultimul pas de timp și nu s-a schimbat niciunul dintre vecinii săi, nu va fi schimbată în pasul de timp curent, astfel încât un program care ține evidența zonelor active poate economisi timp prin neactualizarea zonelor inactive.[51]

 
Jocul Vieții pe suprafața unui nod de trifoi toroidal

Pentru a evita deciziile și ramificările în bucla de numărare, regulile pot fi rearanjate de la o abordare egocentrică a celulei din interior cu privire la vecinii săi până la punctul de vedere al observatorului științific: dacă suma tuturor celor nouă câmpuri dintr-o anumită vecinătate este trei, starea celulei interioare pentru generația următoare va fi viața; dacă suma tuturor câmpurilor este patru, celula interioară își păstrează starea curentă; și orice altă sumă determină moartea celulei interioare.

Pentru a economisi memoria, stocarea poate fi redusă la o matrice plus două linii tampon. O linie tampon este utilizată pentru a calcula starea succesoare a unei linii, apoi a doua linie tampon este folosită pentru a calcula starea succesoare pentru linia următoare. Primul tampon este apoi scris pe linia sa și eliberat pentru a păstra starea succesoare pentru a treia linie. Dacă se folosește o matrice toroidală, este nevoie de un al treilea tampon, astfel încât starea inițială a primei linii din matrice să poată fi salvată până când este calculată ultima linie.

 
Tun cu glidere într-o matrice toroidală. Fluxul de glidere se înfășoară și în cele din urmă distruge tunul
 
Glider (roșu) într-o rețea pătrată cu condiții la limită periodice

În principiu, universul Jocului Vieții este infinit, dar computerele au memorie finită. Acest lucru duce la probleme atunci când zona activă ajunge la marginile matricii. Programatorii au folosit mai multe strategii pentru a rezolva aceste probleme. Cea mai simplă strategie este presupunerea că orice celulă din afara matricii este moartă. Acest lucru este ușor de programat, dar duce la rezultate inexacte atunci când zona activă depășește marginile. Un truc mai sofisticat este să se ia în considerare marginile din stânga și din dreapta ale grilei, care urmează să fie cusate împreună, precum și marginile de sus și de jos, producând o matrice toroidală. Rezultatul este că zonele active care trec peste marginea grilei reapar la marginea opusă. Inexactitatea poate apărea dacă modelul crește prea mult, dar nu există efecte patologice de margine. Tehnicile de alocare dinamică a stocării pot fi, de asemenea, utilizate, creând rețele din ce în ce mai mari pentru a stoca modelele în creștere. Jocul Vieții pe o grilă finită este uneori studiat în mod explicit; unele implementări, cum ar fi Golly, acceptă o alegere pentru grila infinită standard, o grilă infinită doar pentru o singură dimensiune sau o grilă finită, cu o anumită topologie, cum ar fi un cilindru, un tor sau o bandă Möbius.

Alternativ, programatorii pot abandona metoda de a reprezenta grila Jocului Vieții într-o matrice bidimensională și pot folosi o structură de date diferită, cum ar fi un vector de perechi de coordonate reprezentând celule vii. Acest lucru permite modelului să se miște pe câmp nestingherit, atâta timp cât populația nu depășește dimensiunea matricei de coordonate generate activ. Dezavantajul este că numărarea vecinilor vii devine o operație de căutare sau de căutare în tabel hash, încetinind viteza de simulare. Cu structuri de date mai sofisticate, în mare măsură această problemă poate fi rezolvată.

Pentru a explora modele mari pe durate mari de timp există algoritmi sofisticați precum Hashlife. De asemenea, există o metodă de implementare a Jocului Vieții și a altor automate celulare care, în timp ce emulează exact comportamentul jocului sincron, utilizează actualizări asincrone arbitrare.[52] Exemple de coduri sursă care implementează scenariul de bază al Jocului Vieții în diferite limbaje de programare, inclusiv în C, C++, Java și Python poate fi găsit la Rosetta Code.[53]

Variante

modificare

Încă de la începuturile Jocului Vieții au fost dezvoltate și alte automate celulare similare. Jocul Vieții standard este simbolizat în notația cu șirul de reguli ca B3/S23. Adică, o celulă se naște (în engleză born) dacă are exact trei vecini, supraviețuiește dacă are doi sau trei vecini vii și moare în celelalte cazuri. Primul număr, sau listă de numere, B, este ceea ce este necesar pentru ca o celulă moartă să se nască. Al doilea număr, S, este cerința ca o celulă vie să supraviețuiască până la următoarea generație. Prin urmare, B6/S16 înseamnă „o celulă se naște dacă există șase vecini și trăiește dacă există unul sau șase vecini”. Automatele celulare de pe o grilă bidimensională care pot fi descrise în acest fel sunt cunoscute sub numele de automat celular de tip Jocul Vieții. Highlife, este descris de regula B36/S23.[54][55]

 
O mostră de oscilator în 48 de pași trepte împreună cu un oscilator în 2 pași și un oscilator în 4 pași dintr-un joc al vieții bidimensional hexagonal (regula H:B2/S34)

Unele variante ale Jocului Vieții au altă geometrie a universului, precum și alte reguli. Variantele pot fi gândite ca un pătrat bidimensional, deoarece lumea este bidimensională și așezată într-o grilă pătrată. Au fost create și variante unidimensionale, cunoscute sub numele de automate celulare elementare,[56] precum și tridimensionale. Au fost create și variante bidimensionale pe pavări triunghiulare și hexagonale, și char variante pe pavări aperiodice.[57]

Regulile lui Conway pot fi, generalizate și cu privire la numărul de stări, astfel încât în loc de două stări, „vii” și „moarte”, să fie trei sau mai multe. Tranzițiile de stare sunt apoi determinate fie de un sistem de ponderare, fie de un tabel care specifică reguli de tranziție separate pentru fiecare stare, de exemplu familiile de reguli multicolore și ponderate din Mirek's Cellebration au fiecare seturi de reguli echivalente cu Jocul Vieții.

În anumite variante pot fi observate modele legate de fractali și sisteme fractale. De exemplu, automatul B1/S12 generează patru aproximări foarte apropiate de triunghiul Sierpiński⁠(d) atunci când este aplicat unei singure celule vii. Triunghiul Sierpiński poate fi observat și în Jocul Vieții examinând creșterea pe termen lung a unei linii de celule vii infinit de lungă și cu o grosime de o singură celulă,[58] în Highlife, Seeds (B2/S), și Rule 90.[59]

Immigration este o variantă foarte asemănătoare cu Jocul Vieții, cu excepția faptului că există două stări on, adesea exprimate prin două culori diferite. Ori de câte ori se naște o nouă celulă, aceasta capătă starea care este majoritară în cele trei celule care i-au dat naștere. Această caracteristică poate fi folosită pentru a examina interacțiunile dintre navele spațiale și alte obiecte din joc.[60] O variantă similară, numită QuadLife, are patru stări diferite. Când o nouă celulă se naște din trei vecini diferiți, aceasta ia a patra valoare, altfel, la fel ca în Immigration, ia valoarea majoritară.[61] Cu excepția variantelor de celule, ambele variante acționează identic cu Jocul Vieții.

Muzică

modificare

Diverse tehnici de compoziție muzicală folosesc Jocul Vieții, în special la generarea melodiilor în MIDI.[62] Există diverse programe pentru a crea muzică din modele generate în Jocul Vieții.[63][64][65]

Programe notabile

modificare
 
Cea de a 6366548773467669985195496000-a (6×1027) generație făcută în Jocul Veții de o mașină Turing, calculată în mai puțin de 30 de secunde de o CPU Intel Core Duo 2 GHz rulând Golly în mod Hashlife

Computerele au fost folosite pentru a urmări și simula Jocul Vieții de când a fost făcut public pentru prima dată. Când John Conway a investigat pentru prima dată modul în care au evoluat diferitele configurații de pornire, le-a urmărit manual folosind o tablă de go cu pietrele sale albe și negre. Acest lucru a fost plictisitor și predispus la erori. Primul program interactiv pentru Jocul Vieții a fost scris de Michael Guy și Stephen R. Bourne într-o versiune timpurie de ALGOL 68C pentru PDP-7. Rezultatele au fost publicate în numărul din octombrie 1970 al revistei Scientific American, împreună cu declarația: „Fără ajutorul lui, unele descoperiri despre joc ar fi fost dificil de făcut”.[1]

O versiune color a Jocului Vieții a fost scrisă de Ed Hall în 1976 pentru microcalculatoarele Cromemco, iar o captură de ecran din acel program a apărut pe coperta ediției din iunie 1976 a revistei Byte.[66] Apariția graficii color bazate pe microcomputerul Cromemco a determinat o renaștere a interesului pentru joc.[67]

Două implementări timpurii ale Jocului Vieții pe computerele personale au fost scrise de Malcolm Banthorpe în BBC BASIC. Prima a apărut în numărul din ianuarie 1984 al revistei Acorn User, urmată de o versiune tridimensională în numărul din mai 1984.[68] Susan Stepney, profesor de informatică la Universitatea din York, a continuat acest lucru în 1988 cu Life on the Line, un program care a generat automate celulare unidimensionale.[69]

Acum există mii de programe online cu Jocul Vieții, așa că o listă completă nu va fi furnizată aici, ci doar o mică selecție de programe, mai populare sau cu caracteristici neobișnuite. Cele mai multe dintre aceste programe au o interfață grafică cu utilizatorul pentru editarea și simularea modelelor, capacitatea de a simula mai multe reguli, inclusiv Jocul Vieții, o bibliotecă mare de modele interesante în Jocul Vieții și de alte reguli ale automatelor celulare.

  • Golly este un sistem de simulare cu sursă deschisă multiplatformă (Windows, Macintosh, Linux, iOS și Android) pentru Jocul Vieții și alte automate celulare (inclusiv toate automatele celulare de tip Jocul Vieții, familia Generations de automate celulare din Mirek's Cellebration și automatul celular cu 29 de stări al lui John von Neumann) de Andrew Trevorrow și Tomas Rokicki. Include algoritmul Hashlife pentru generare extrem de rapidă și scripturi Lua sau Python atât pentru editare, cât și pentru simulare.
  • Mirek's Cellebration este un vizualizator, explorator și editor liber (în engleză freeware) de automate celulare uni și bidimensionale pentru Windows. Are capacități mari de simulare și vizualizare a unei game largi de reguli pentru automate celulare, inclusiv Jocul Vieții, precum și un editor de scripturi.
  • Xlife este un laborator de automate celulare de Jon Bennett. Aplicația standard de simulare pe UNIX X11 a Jocului Vieții a fost portată și pe Windows. Poate gestiona regulile automatelor celulare cu aceeași vecinătate ca Game of Life și până la opt stări posibile pe celulă.[70]
  • Dr. Blob's Organism este un Shoot 'em up bazat pe Jocul Vieții. În joc se generează continuu un grup de celule într-o „cutie Petri”. Modelele formate sunt netezite și rotunjite pentru a arăta ca o amibă în creștere care împrăștie altele mai mici (de fapt glidere). „Probe” speciale elimină „blobul” pentru a-l împiedica să reverse din vas în timp ce îi distruge nucleul.[71]

În 2012 Google a implementat pentru Jocul Vieții o surpriză⁠(d). Utilizatorilor care caută termenul „Game of Life” li se arată în pagina cu rezultatele căutării o implementare a jocului.[72][b]

Note explicative

modificare
  1. ^ Simultaneitatea înseamnă că atunci când la o celulă se numără numărul de vecini vii din jurul ei se folosesc stările vechi ale vecinilor săi, înainte de actualizare, nu stările lor noi, după actualizare. Dacă celulele ar fi actualizate în ordinea de citire, astfel încât fiecare celulă să folosească stările vechi ale celulelor din dreapta și de dedesubt, dar noile stări ale celulelor din stânga și de deasupra acesteia, rezultă un automat celular diferit, care este cunoscut drept NaiveLife[4][5] deoarece este o greșeală obișnuită a începătorilor din rândul persoanelor care încearcă să programeze Jocul Vieții al lui Conway.[6]
  2. ^ Încercați, și puțină răbdare!

Note

modificare
  1. ^ a b c d en Gardner, Martin (octombrie 1970). „The fantastic combinations of John Conway's new solitaire game 'life'” (PDF). Mathematical Games. Scientific American. Vol. 223 nr. 4. pp. 120–123. doi:10.1038/scientificamerican1070-120. JSTOR 24927642. Arhivat din original (PDF) la . 
  2. ^ a b c d e en Berlekamp, Elwyn R.; Conway, John Horton; Guy, Richard K. (). Winning Ways for your Mathematical Plays (ed. 2nd). A K Peters Ltd. 
  3. ^ a b c en Izhikevich, Eugene M.; Conway, John H.; Seth, Anil (). „Game of Life”. Scholarpedia. 10 (6): 1816. Bibcode:2015SchpJ..10.1816I. doi:10.4249/scholarpedia.1816  . ISSN 1941-6016. 
  4. ^ en „NaiveLife Emulated: A reading-order simulation of Life”. ConwayLife.com. . Accesat în . 
  5. ^ en Goucher, Adam. „Re: Thread For Your Accidental Discoveries”. ConwayLife.com. Accesat în . 
  6. ^ en Ian07. „Re: Strange spaceship that is supposed to be impossible and infinite cell spread”. ConwayLife.com. Accesat în . I'm pretty sure this is because you've accidentally created an implementation of what's sometimes known as NaiveLife (as it's a common mistake made by many people coding CGoL for the first time): 
  7. ^ en Pickover, Clifford A. (). The Math Book: From Pythagoras to the 57th Dimension, 250 Milestones in the History of Mathematics . Sterling Publishing Company, Inc. p. 406. ISBN 978-1402757969. 
  8. ^ a b c en Schiff, Joel L. (). Cellular Automata: A Discrete View of the World. Wiley & Sons, Inc. pp. 1–3. ISBN 9781118030639. 
  9. ^ en John von Neumann, "The general and logical theory of automata," in Lloyd A. Jeffress, ed., Cerebral Mechanisms in Behavior – The Hixon Symposium, John Wiley & Sons, New York, 1951, pp. 1–31.
  10. ^ en Kemeny, John G. (). „Man viewed as a machine”. Sci. Am. 192 (4): 58–67. Bibcode:1955SciAm.192d..58K. doi:10.1038/scientificamerican0455-58. ; Sci. Am. 1955; 192:6 (errata).
  11. ^ en Ilachinski, Andrew (). Cellular Automata: A Discrete Universe. World Scientific. p. xxix. ISBN 978-981-238-183-5. 
  12. ^ en Bialynicki-Birula, Iwo; Bialynicka-Birula, Iwona (). Modeling Reality: How Computers Mirror Life. Oxford University Press. p. 8. ISBN 978-0198531005. 
  13. ^ en von Neumann, John; Burks, Arthur W. (). Theory of Self-Reproducing Automata. University of Illinois Press. 
  14. ^ en Conway, private communication to the 'Life list', 14 April 1999.
  15. ^ a b en Paul Chapman (). „Life Universal Computer”. Arhivat din original la . Accesat în .  „Este un model și o simulare care sunt interesante de urmărit și pot arăta că lucrurile simple pot deveni probleme complicate.”
  16. ^ en Alstrøm, Preben; Leão, João (). „Self-organized criticality in the game of Life”. Physical Review E. 49 (4): R2507–R2508. Bibcode:1994PhRvE..49.2507A. doi:10.1103/PhysRevE.49.R2507. PMID 9961636. 
  17. ^ en Dennett, D. C. (). Consciousness Explained . Boston: Back Bay Books. ISBN 978-0-316-18066-5. 
  18. ^ en Dennett, D.C. (). Darwin's Dangerous Idea: Evolution and the Meanings of Life . New York: Simon & Schuster. ISBN 978-0-684-82471-0. 
  19. ^ en Dennett, D.C. (). Freedom Evolves. New York: Penguin Books. ISBN 978-0-14-200384-8. 
  20. ^ en Paul Rendell (). „A Turing Machine in Conway's Game of Life”. Accesat în . 
  21. ^ en Adam P. Goucher. „Spartan universal computer-constructor”. LifeWiki. Accesat în . 
  22. ^ en „R-pentomino”. LifeWiki. . pp. 219, 223. Accesat în . 
  23. ^ en Stephen A. Silver. „Glider”. The Life Lexicon. Accesat în . 
  24. ^ en „Census Results in Conway's Game of Life”. The Online Life-Like CA Soup Search. Arhivat din original la . Accesat în . 
  25. ^ en „Spontaneous appeared Spaceships out of Random Dust”. Achim Flammenkamp (1995-12-09). Accesat în . 
  26. ^ en Stephen A. Silver. „Pulsar”. The Life Lexicon. Accesat în . 
  27. ^ en [1], retrieved 2023-07-22
  28. ^ en Achim Flammenkamp (). „Most seen natural occurring ash objects in Game of Life”. Accesat în . 
  29. ^ en Stephen A. Silver. „Diehard”. The Life Lexicon. Accesat în . 
  30. ^ en Koenig, H. (). „New Methuselah Records”. Arhivat din original la . Accesat în . 
  31. ^ en Stephen A. Silver. „Gosper glider gun”. The Life Lexicon. Accesat în . 
  32. ^ en The Hunting of the New Herschel Conduits, ConwayLife forums, April 28th, 2015, posts by Michael Simkin ("simsim314") and Dongook Lee ("Scorbie").
  33. ^ en „Block-laying switch engine”. LifeWiki. Accesat în . 
  34. ^ en Stephen A. Silver. „Infinite Growth”. The Life Lexicon. Accesat în . 
  35. ^ en Stephen A. Silver. „Rake”. The Life Lexicon. Accesat în . 
  36. ^ en „Programmable computer”. conwaylife.com forums. Accesat în . 
  37. ^ en „A Turing Machine in Conway's Game of Life, extendable to a Universal Turing Machine”. Paul Rendell. Accesat în . 
  38. ^ en „Build a working game of Tetris in Conway's Game of Life”. StackExchange. Accesat în . 
  39. ^ en „Elementary knightship”. Accesat în . 
  40. ^ en "Elementary", LifeWiki, retrieved 2018-11-21
  41. ^ en Aron, Jacob (). „First replicating creature spawned in life simulator”. New Scientist. Accesat în . 
  42. ^ a b en „Gemini – LifeWiki”. Conwaylife.com. Accesat în . 
  43. ^ en „Universal Constructor Based Spaceship”. Conwaylife.com. Accesat în . 
  44. ^ en „Demonoid”. LifeWiki. Accesat în . 
  45. ^ en „Geminoid Challenge”. Conwaylife.com. Accesat în . 
  46. ^ en Passe-Science (). „Automate Cellulaire - Passe-science #27”. YouTube. Arhivat din original la . Accesat în . 
  47. ^ en apgoucher (). „Fully self-directed replication”. Complex Projective 4-Space. Accesat în . 
  48. ^ en „0E0P metacell - LifeWiki”. www.conwaylife.com. Accesat în . 
  49. ^ en Andrzej Okrasinski. „Game of Life Object Statistics”. Arhivat din original la . Accesat în . 
  50. ^ en Nathaniel Johnston. „The Online Life-Like CA Soup Search”. Arhivat din original la . Accesat în . 
  51. ^ en Alan Hensel. „About my Conway's Game of Life Applet”. Accesat în . 
  52. ^ en Nehaniv, Chrystopher L. (). Self-Reproduction in Asynchronous Cellular Automata. 2002 NASA/DoD Conference on Evolvable Hardware. Alexandria, Virginia, USA: IEEE Computer Society Press. pp. 201–209. doi:10.1109/EH.2002.1029886. hdl:2299/6834  . ISBN 0-7695-1718-8. 
  53. ^ „Conway's Game of Life”. 
  54. ^ en HighLife – An Interesting Variant of Life by David Bell (.zip file)
  55. ^ en Stephen A. Silver. „Replicator”. The Life Lexicon. Accesat în . 
  56. ^ en „Elementary Cellular Automaton”. Wolfram Mathworld. Accesat în . 
  57. ^ en „First gliders navigate ever-changing Penrose universe”. New Scientist. 
  58. ^ en Stephen Wolfram, A New Kind of Science online, Note (f) for structures in class 4 systems: Structures in the Game of Life: "A simpler kind of unbounded growth occurs if one starts from an infinite line of black cells. In that case, the evolution is effectively 1D, and turns out to follow elementary rule 22"
  59. ^ en „Life Imitates Sierpinski”. ConwayLife.com forums. Accesat în . 
  60. ^ en Stephen A. Silver. „Immigration”. The Life Lexicon. Accesat în . 
  61. ^ en Stephen A. Silver. „QuadLife”. The Life Lexicon. Accesat în . 
  62. ^ en Burraston, Dave; Edmonds, Ernest; Livingstone, Dan; Miranda, Eduardo Reck (). „Cellular Automata in MIDI based Computer Music”. Proceedings of the 2004 International Computer Music Conference. CiteSeerX 10.1.1.6.3882  . hdl:10453/1425. ISBN 9780971319226. 
  63. ^ en „glitchDS – Cellular Automaton Sequencer For The Nintendo DS”. Synthtopia.com. . Accesat în . 
  64. ^ en „Game Of Life Music Sequencer”. Synthtopia.com. . Accesat în . 
  65. ^ en „Game Of Life Music Sequencer For iOS, Runxt Life”. Synthtopia.com. . Accesat în . 
  66. ^ en Helmers, Carl (iunie 1976). „About the Cover”. Byte. Nr. 10. pp. 6–7. Accesat în . 
  67. ^ en McIntosh, Harold (). „Introduction” (PDF). Journal of Cellular Automata. 13: 181–186. Arhivat din original (PDF) la . Accesat în . With the advent of microcomputers and Cromemco’s graphics board, Life became a favorite display program for video monitors and led to a revival of interest in the game. 
  68. ^ en „Acorn User Magazine Scans”. The BBC and Master Computer Public Domain Library. Accesat în . 
  69. ^ en Stepney, Susan. „AcornUser articles”. www-users.cs.york.ac.uk. AcornUser. Accesat în . 
  70. ^ en „Xlife”. 
  71. ^ en „Dr. Blob's Organism freeware”. 
  72. ^ en Wasserman, Todd (). „Type 'Conway's Game of Life' on Google and See What Happens”. Mashable. Accesat în . 

Vezi și

modificare

Legături externe

modificare
  Portal Matematică
Adus de la https://ro.wikipedia.org/w/index.php?title=Jocul_Vieții_al_lui_Conway&oldid=16652412