Automat celular

Gosper's Cannon, un exemplu clasic de automat celular în acțiune

Un automat celular (din engleza Cellular automat sau Cellular automata , abrev. CA ) este un model matematic folosit pentru a descrie evoluția sistemelor discrete complexe , studiată în teoria calculului , matematicii , fizicii și biologiei .

Generalitate

Un automat celular constă dintr-o grilă formată din celule, de exemplu o hârtie pătrată. Grila poate avea orice dimensiune finită; fiecare porțiune limitată de spațiu trebuie să conțină doar un număr finit de celule. Fiecare dintre aceste celule poate lua un set finit de stări (de exemplu, „viu” sau „mort”, o culoare, o formă etc.). Pentru fiecare celulă este de asemenea necesar să se definească setul de celule care trebuie considerate „apropiate” de celula dată (de exemplu, în cazul unei foi pătrate, două celule adiacente pot fi definite ca „închise” sau două celule la o distanță maximă de două pătrate). La un anumit moment t = 0 o anumită stare este atribuită fiecărei celule. Setul acestor stări constituie starea inițială a automatului celular. După un timp prestabilit, fiecare celulă își va schimba starea în același timp cu toate celelalte, conform unei reguli fixe (care variază în funcție de automatul celular considerat). Modul în care o celulă își schimbă starea depinde numai de starea sa actuală și de stările celulelor „vecine”.

Ideea a fost inițial dezvoltată de Stanislaw Ulam și John von Neumann la începutul anilor 1950 și a înflorit odată cu dezvoltarea teoriilor de calcul și a structurilor hardware. Un exemplu clasic de automat celular este jocul vieții conceput de matematicianul englez John Conway : este compus dintr-un set de poziții ocupate sau neocupate, care au loc pe o grilă și supraviețuiesc sau mor pe baza numărului de poziții ocupate apropiate unii către alții. ei. Fiecare CA are aceleași elemente: un set de locații conectate, un set de stări la fiecare locație și reguli de actualizare pentru starea locațiilor. ^[1]

Un automat celular bazat pe celule hexagonale mai degrabă decât dreptunghiulare (regula 34/2)

Forma celulelor nu este neapărat pătrată: un automat celular poate consta, de exemplu, din celule triunghiulare, hexagonale, cubice etc. Dacă un plan este împărțit în hexagoane obișnuite, acestea pot fi folosite ca celule. În multe cazuri, automatele celulare rezultate sunt echivalente cu cele construite pe rețele dreptunghiulare.

Clasificările unei CA, așa cum a subliniat Wolfram, sunt numerotate de la unu la patru. Acestea sunt, în ordine:

Automate în care tiparele sunt în general stabilizate în omogenitate.
Automate în care tiparele evoluează în structuri predominant stabile sau oscilatorii.
Automate în care tiparele evoluează într-o manieră aparent haotică.
Automate în care tiparele devin extrem de complexe și pot dura mult timp folosind structuri locale stabile.

Această ultimă clasă este considerată echivalentă Turing și capabilă să simuleze o mașină Turing . Tipuri speciale de automate celulare sunt așa-numitele reversibile, în care o singură configurație duce direct la una ulterioară și totalistă în care viitorul celulelor individuale depinde de valoarea totală a grupurilor de celule adiacente. Automatele celulare pot simula o multitudine de sisteme reale, cum ar fi sistemele biologice și chimice.

Cel mai simplu exemplu

Cel mai simplu tip nontrivial de automate celulare este unidimensional, cu doar două stări posibile pentru fiecare celulă și celule vecine definite ca celule adiacente pe ambele părți. O celulă cu cele două celule vecine (adică cele adiacente) alcătuiește un cartier de 3 celule, deci există $2^{3}=8$ ${\ displaystyle 2 ^ {3} = 8}$ $2 ^ {3} = 8$ configurații posibile pentru un cartier. Deci avem $2^{8}=256$ ${\ displaystyle 2 ^ {8} = 256}$ $2 ^ 8 = 256$ posibile reguli. Aceste 256 de automate celulare sunt descrise în general folosind notația Wolfram , o convenție, concepută tocmai de Stephen Wolfram , în care numele automatului celular este numărul zecimal care, în notație binară, ne oferă tabelul de reguli, cu cele 8 cartiere posibile. enumerate. De exemplu, mai jos sunt tabelele care definesc regulile „CA 30” și „CA 110” (unde CA înseamnă Automat celular).

În binar 30 și 110, sunt scrise respectiv 11110 și 1101110. Sub fiecare tabel este reprezentată grafic evoluția automatului, în cazul în care starea inițială constă dintr-o singură celulă neagră (toate celelalte albe). 0 corespunde unei celule albe, iar 1 unei celule negre. Prima linie a fiecărei figuri reprezintă starea inițială, următoarele linii următoarele stări ale automatului pe măsură ce timpul progresează de-a lungul axei verticale.

configurația cartierului	111	110	101	100	011	010	001	000
stare nouă pentru celula centrală	0	0	0	1	1	1	1	0

Regula 30 automat celular

configurația cartierului	111	110	101	100	011	010	001	000
stare nouă pentru celula centrală	0	1	1	0	1	1	1	0

Regula 110 automat celular

Descriere

Definiție formală

Este posibil să se definească în mod formal automatele celulare luând în considerare trei caracteristici fundamentale:

reprezentarea spațială a entităților implicate.
uniformitate: entitățile găsite în fiecare punct al spațiului sunt identice.
locația: fiecare entitate își schimbă starea ținând cont doar de ceea ce se întâmplă la o anumită distanță.

Definiția presupune că se află într-un spațiu euclidian : dimensiunea mediului și numărul stărilor sunt fixe (trebuie să fie un număr finit egal cu cel puțin două pentru a nu cădea într-o situație banală). Ultima cantitate care trebuie fixată este distanța maximă a entităților care trebuie luate în considerare pentru schimbarea stării. De asemenea, trebuie să setăm o funcție de schimbare a stării (definește modul în care se schimbă starea). Un automat celular poate fi definit ca un cvadruplu <d, Q, N, f> în care:

d este un număr întreg pozitiv, numit dimensiune ;
Q este un set finit, numit spațiu de stare;
N este un subset finit al lui Z ^d , numit indicele de vecinătate ;
f este o funcție definită pe Q ^{| N |} cu valori în Q astfel încât, numită c _i ^t starea entității în punctul i al spațiului Z ^d la momentul t , și notată cu n ₁ , n ₂ , ..., n _{| N |} elementele lui N , rezultă: c _i ^{t + 1} = f (c _{i + n ₁} ^t , c _{i + n ₂} ^t , ..., c _{i + n _{| N |}} ^t ) în fiecare punct i și în fiecare instant de timp t .

Utilizări ale automatelor celulare

Automatele celulare sunt potrivite pentru reprezentarea și simularea evoluției globale a fenomenelor care depind doar de legile locale. Exemple de fenomene de acest tip sunt comportamentul fizic al gazelor perfecte , evoluția unei populații, un ecosistem (de exemplu Wa-Tor ), mișcarea șuvițelor de ADN într-o soluție.

Automatele celulare sunt utilizate în mod eficient pentru generarea de tonuri de apel. Un întreg portal web ( tonuri Wolfram ) arată cum este posibilă transformarea unei secvențe de pași a unui automat celular cu reguli speciale în note muzicale, generând muzică.

Sunt folosite și în domeniul muzicii contemporane. Un exemplu de utilizări timpurii în acest domeniu este compoziția Horos din 1986 a lui Iannis Xenakis , în care automatele celulare sunt utilizate pentru a „produce progresii armonice și noi combinații timbrale”. ^[2]

Automate celulare în natură

Textura Conus prezintă un model al unui automat celular pe coajă

Automatele celulare sunt de obicei foarte elegante pentru a descrie modelele găsite în natură: de la dungi de zebră, la haina pătată a ghepardului, până la dungi de dune din deșert. Un alt exemplu se găsește în unele scoici marine, cum ar fi cele din genul Conus , a căror colorare este generată de automatele celulare naturale. ^[3]

Clasificarea lui Wolfram

Stephen Wolfram , în Un nou tip de știință și alte publicații datate la mijlocul anilor 1980 , a definit patru clase în care fiecare automat celular și alte modele de calcul simple pot fi împărțite, pe baza comportamentului lor. În timp ce studiile anterioare care implicau automatele celulare au avut tendința de a identifica tipuri de modele pentru reguli specifice, clasificarea lui Wolfram a fost prima care a încercat să clasifice regulile în sine. În ordinea complexității, regulile sunt:

Clasa 1: Aproape toate tiparele timpurii evoluează rapid pentru a ajunge în stări stabile și omogene. Orice aleatorie a tiparelor inițiale dispare.
Clasa 2: Aproape toate tiparele timpurii evoluează rapid în structuri stabile sau oscilante. Aleatoritatea în tiparele inițiale poate fi ignorată, dar pentru unii este prezentă. Modificările locale față de modelul inițial tind să rămână locale.
Clasa 3: Aproape toate tiparele inițiale evoluează într-o manieră pseudo-aleatorie sau haotică. Orice structură stabilă pare a fi distrusă rapid de zgomotul din jur. Modificările locale de la modelul inițial tind să se răspândească la nesfârșit.
Clasa 4: Aproape toate tiparele inițiale evoluează în structuri care interacționează într-un mod complex și interesant. Rezultatele clasei 2, fie structuri stabile, fie oscilante, pot fi rezultatul final, dar numărul de pași necesari pentru a ajunge la această stare poate fi mare, chiar și atunci când modelul inițial este relativ simplu. Modificările locale ale modelului inițial pot fi distribuite pe termen nelimitat.

Wolfram a susținut că multe, dacă nu toate automatele de clasa 4 sunt capabile de calcul universal. Acest lucru a fost dovedit pentru regula numărul 110 și jocul vieții lui John Conway . Aceste definiții sunt calitative prin natura lor și pot lăsa loc interpretării. Conform celor afirmate de Wolfram, "... cu aproape orice schemă generală de clasificare există inevitabil cazuri care sunt atribuite unei clase printr-una din definiții și unei alte clase printr-o definiție diferită. Și așa este cu automatele. Telefoanele mobile: există reguli ocazionale ... care arată unele caracteristici ale unei clase și ale altora din alte clase. " ^[4]

Reversibilitate

Se spune că un automat celular este reversibil dacă pentru fiecare configurație curentă a automatului există o singură configurație trecută (pre-imagine). Dacă vă gândiți la un automat celular ca o funcție pentru maparea configurațiilor la alte configurații, reversibilitatea implică faptul că funcția de mai sus este bijectivă . Dacă un automat celular este reversibil, comportamentul său invers în timp poate fi totuși descris ca un automat celular; acest fapt este o consecință a teoremei Curtis - Hedlund - Lyndon, o caracterizare topologică a unui automat celular ^[5] ^[6] . Pentru automatele celulare care nu au o imagine prealabilă pentru fiecare model, configurațiile menționate mai sus fără o imagine prealabilă se numesc modelul „Grădina Edenului”.

Pentru un automat celular unidimensional, există algoritmi specifici pentru a determina dacă o regulă este reversibilă sau ireversibilă. Cu toate acestea, pentru un automat celular cu două sau mai multe dimensiuni reversibilitatea nu este determinabilă; adică nu există algoritmi care să ia ca intrare o regulă pentru a determina corect dacă un automat este reversibil sau nu. Demonstrația lui Jarko Kari se referă la problema țiglelor cunoscută sub numele de tigla Wang .

Automatele celulare reversibile sunt adesea folosite pentru a simula fenomene fizice precum dinamica gazelor și fluidelor, deoarece respectă legile termodinamicii. Aceste automate au reguli construite special pentru a fi reversibile. Aceste sisteme au fost studiate de Tommaso Toffoli , Norman Margolus și alții. Unele tehnici pot fi utilizate pentru a construi în mod explicit un automat reversibil cu invers cunoscut a priori. Două tipuri bine cunoscute sunt automatul celular de ordinul doi și automatul celular bloc . Deși aceste automate nu îndeplinesc strict definiția dată mai sus, se poate arăta că pot fi emulate de automatele celulare convenționale cu un vecinătate și un număr suficient de mari de stări și, prin urmare, pot fi considerate un subset al automatelor celulare convenționale. Dimpotrivă, s-a arătat că orice automat reversibil poate fi emulat cu un automat celular bloc. ^[7] ^[8]

Automatele celulare ca modele fizice

După cum subliniază Andrew Ilachinski în monografia sa Cellular Automata , mulți cercetători cu interese fundamentale au pus mai devreme sau mai târziu întrebarea: „Și dacă Universul ar fi o CA?” ^[9] Ilachinsky susține că importanța problemei poate fi ușor apreciată printr-un argument simplu. De fapt, luați în considerare evoluția regulii 110 : dacă acea lume ar fi un fel de alt univers guvernat de o „fizică extraterestră”, ce descriere rezonabilă am putea da despre modelele observate? ^[10] Dacă nu am ști cum sunt generate imaginile - adică cu ajutorul regulilor locale simple - probabil că vom presupune că obiectele similare cu „particulele” se mișcă conform anumitor reguli din spațiu (nu este surprinzător, fizicianul Jim Crutchfield a a creat un model matematic riguros de AC simplu în care poate fi demonstrată apariția statistică a „particulelor”). ^[11] Dacă acest lucru este valabil pentru acel univers, de ce lumea noastră - descrisă în prezent de fizicieni prin particule - nu ar putea fi o AC la nivelul său cel mai fundamental?

Deși o teorie completă pe această bază nu a fost încă dezvoltată, explorarea consecințelor acestei ipoteze a condus oamenii de știință la speculații foarte interesante și noi perspective asupra modului în care putem explica fenomenele fizice aparent continue într-un cadru teoretic total discret. Marvin Minsky - pionierul AI - a investigat interacțiunea dintre particule într-o rețea cu patru dimensiuni ^[12] Konrad Zuse - primul cercetător care a construit un computer Turing universal ^{[ neclar ]} (practic orice sistem fizic real calculabil poate fi modelat printr-o implementare adecvată a unui CA) - în schimb a dezvoltat un model cu o rețea neregulată, în încercarea de a oferi idei noi cu privire la cantitate de informații pe care ar trebui să le asumăm pe particulă ^[13] . Mai recent, Edward Fredkin a expus și a apărat ceea ce el numește „Ipoteza naturii finite”, adică ideea că „în final, fiecare cantitate fizică, inclusiv spațiul și timpul, se va dovedi discretă și finită”. ^[14] Fredkin - împreună cu Stephen Wolfram - este probabil cel mai important exponent al unei fizici inspirate de AC: atât din punct de vedere matematic, cât și din punct de vedere filosofico-teoretic, ideile lui Fredkin cu privire la acest subiect sunt originale și articulate. .

Automate celulare în lucrări fictive

În romanul științifico-fantastic de Robert J. Sawyer intitulat în Italia „WWW 1: Awakening” ^[15] autorul își imaginează nașterea unei forme de viață „pe internet” compusă din automatele celulare.

Notă

^ Neil Gershenfeld, Natura modelării matematice pag. 102
^ Makis Solomos, Automate celulare în muzica lui Xenakis. Teorie și practică , Simpozion internațional Iannis Xenakis (Atena, mai 2005), Atena, 2005.
^ Stephen Wolfram, Automate celulare ca modele de complexitate , în Nature , n. 311, 4 octombrie 1984, pp. 419-424.
^ Stephen Wolfram, Un nou tip de știință pag. 231
^ Richardson, D., Tessellations with local transformations , 1972, DOI : 10.1016 / S0022-0000 (72) 80009-6 .
^ Margenstern, Maurice, Automate celulare în spații hiperbolice - Volumul I - Volumul I , 2007, p. 134, ISBN 978-2-84703-033-4 .
^ Kari, Jarkko, On the circuit depth of structural reversible cellular automata , Fundamenta Informaticae, p. 93-107.
^ Durand-Lose, Jérôme, Representing reversible cellular automates with reversible block cellular automates , în Discrete Mathematics and Theoretical Computer Science , 2001.
^ A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, pp. 660.
^ A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, pp. 661-662.
^ JP Crutchfield, "Calculul apariției: calcul, dinamică și inducție", Physica D 75, 11-54, 1994.
^ M. Minsky, "Vacuum celular", Int. Jour. a lui Theo. Phy. 21, 537-551, 1982.
^ K. Zuse, „Universul de calcul”, Int. Jour. a lui Theo. Phy. 21, 589-600, 1982.
^ E. Fredkin, „Mecanica digitală: un proces informațional bazat pe automatele celulare universale reversibile”, Physica D 45, 254-270, 1990
^ WWW1 Awakening on Urania Blog.

Bibliografie

Neil Gershenfeld , Natura modelării matematice , Cambridge University Press (28 noiembrie 1998). ISBN 0-521-57095-6 .
Stephen Wolfram , Un nou tip de știință , Wolfram Media, Inc. ISBN I-57955-008-8
A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001 , pe ilachinski.com . Adus la 16 septembrie 2010 (arhivat din original la 18 aprilie 2011) .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere pe un automat celular

linkuri externe

( EN ) Automat celular , în Encyclopedia Britannica , Encyclopædia Britannica, Inc.
( EN ) Definiția automatului celular pe Mathworld , la mathworld.wolfram.com .
Latticeworld: un automat celular pentru studiul fenomenelor sociale , pe cash-cow.it .
(EN) Tonuri Wolfram: automatele celulare pentru a genera muzică pe tones.wolfram.com.
( EN ) Articol de istorie naturală despre tiparele naturale generate de automatele celulare ( PDF ), pe bill.srnr.arizona.edu . Adus la 30 iunie 2010 (Arhivat din original la 30 iunie 2010) .
( EN ) Articol despre formarea dungi de zebră , pe classes.yale.edu . Adus la 30 iunie 2010 (Arhivat din original la 19 iunie 2010) .
Matematica modelelor de referință , cu un tutorial general despre AC, applet-uri interactive, cod sursă gratuit și diverse resurse pe AC și modele fizice.
Implementare gratuită Cafun Java pentru simularea și vizualizarea automatelor celulare cu configurație bazată pe XML

Controlul autorității	Tezaur BNCF 58285 · LCCN (EN) sh85021692 · GND (DE) 4190671-8 · BNF (FR) cb12144918z (data)

Portalul de matematică : accesați intrările Wikipedia care se ocupă cu matematica

[1] Neil Gershenfeld, Natura modelării matematice pag. 102

[2] Makis Solomos, Automate celulare în muzica lui Xenakis. Teorie și practică , Simpozion internațional Iannis Xenakis (Atena, mai 2005), Atena, 2005.

[3] Stephen Wolfram, Automate celulare ca modele de complexitate , în Nature , n. 311, 4 octombrie 1984, pp. 419-424.

[4] Stephen Wolfram, Un nou tip de știință pag. 231

[5] Richardson, D., Tessellations with local transformations , 1972, DOI : 10.1016 / S0022-0000 (72) 80009-6 .

[6] Margenstern, Maurice, Automate celulare în spații hiperbolice - Volumul I - Volumul I , 2007, p. 134, ISBN 978-2-84703-033-4 .

[7] Kari, Jarkko, On the circuit depth of structural reversible cellular automata , Fundamenta Informaticae, p. 93-107.

[8] Durand-Lose, Jérôme, Representing reversible cellular automates with reversible block cellular automates , în Discrete Mathematics and Theoretical Computer Science , 2001.

[9] A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, pp. 660.

[10] A. Ilachinsky, Cellular Automata, World Scientific Publishing, 2001, pp. 661-662.

[11] JP Crutchfield, "Calculul apariției: calcul, dinamică și inducție", Physica D 75, 11-54, 1994.

[12] M. Minsky, "Vacuum celular", Int. Jour. a lui Theo. Phy. 21, 537-551, 1982.

[13] K. Zuse, „Universul de calcul”, Int. Jour. a lui Theo. Phy. 21, 589-600, 1982.

[14] E. Fredkin, „Mecanica digitală: un proces informațional bazat pe automatele celulare universale reversibile”, Physica D 45, 254-270, 1990

[15] WWW1 Awakening on Urania Blog.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]