Cellulær automat

En cellulær automat er en diskret model studeret i matematik , beregningsteori , fysik , teoretisk biologi og mikromekanik. Grundlaget er rummet af celler (celler), der støder op til hinanden, og danner et gitter. Hver celle kan være i en af et endeligt sæt af tilstande (f.eks. 1 og 0). Gitteret kan være af enhver dimension, uendeligt eller endeligt; for et gitter med endelige dimensioner er der ofte tilvejebragt looping, når grænsen (grænsen) er nået. For hver celle er der defineret et sæt celler, kaldet nabolaget . For eksempel von Neumann-kvarteretaf rang 2 omfatter alle celler i en afstand på ikke mere end 2 fra den nuværende. Regler for overgangen af celler fra en tilstand til en anden er etableret. Normalt er overgangsreglerne de samme for alle celler. Et trin i automaten involverer at gennemgå alle cellerne og, baseret på dataene om den aktuelle tilstand af cellen og dens omgivelser, bestemme den nye tilstand for cellen, som den vil have ved næste trin. Inden maskinen startes, specificeres cellernes begyndelsestilstand, som kan indstilles målrettet eller tilfældigt.

Hovedretningen i studiet af cellulære automater er den algoritmiske løselighed af visse problemer. Spørgsmålene om at konstruere begyndelsestilstande, under hvilke den cellulære automat vil løse et givet problem, overvejes også.

Historie

Stanislav Ulam , der arbejdede ved Los Alamos National Laboratory i 1940'erne, studerede krystalvækst ved hjælp af en simpel gittermodel [1] . På samme tid arbejdede John von Neumann , en kollega til Ulam, på problemet med selvreproducerende systemer. Von Neumanns originale koncept var baseret på ideen om en robot, der samler en anden robot. En sådan model er kendt som kinematisk. Efter at have udviklet denne model, erkendte von Neumann vanskeligheden ved at bygge en selvreplikerende robot og i særdeleshed sørge for det nødvendige "lager af dele", som robotten skal bygges ud fra. Ulam foreslog von Neumann, at der skulle bruges en mere abstrakt matematisk model, svarende til den, Ulam brugte til at studere krystalvækst. Således opstod det første cellulære automatsystem. Ligesom Ulam-gitteret er von Neumann-celleautomaten todimensionel, og den selvreplikerende robot er beskrevet algoritmisk. Resultatet var en universel konstruktør, der arbejder "inde i" en cellulær automat med et kvarter, der omfatter umiddelbart tilstødende celler og har 29 stater. Von Neumann beviste, at for en sådan model er der et mønster, der uendeligt vil kopiere sig selv.

Også i 1940'erne udviklede Norbert Wiener og Arturo Rosenblueth den cellulære automatmodel af det excitable miljø . Målet var en matematisk beskrivelse af udbredelsen af en impuls i hjerteganglionerne. Deres originale arbejde bliver fortsat citeret i nutidig forskning om arytmier og excitable miljøer.

I 1960'erne blev cellulære automater undersøgt som en særlig type dynamiske systemer, og for første gang blev deres forbindelse med feltet symbolsk dynamik etableret. I 1969 gennemgik G. A. Hedland ( eng. Gustav A. Hedlund ) de opnåede resultater i denne retning. Det mest betydningsfulde resultat var beskrivelsen af regelsættet for en cellulær automat som et sæt af kontinuerlige endomorfismer i et skiftrum.

I 1970'erne vandt en todimensionel cellulær automatmodel med to celletilstande, kendt som Life Game, fremtrædende plads . Opfundet af John Conway og populariseret af Martin Gardner , bruger den følgende regler: på et kvadratisk gitter har hver celle 8 naboer; hvis cellen har to "levende" naboer, forbliver den i samme tilstand. Hvis en celle har tre "levende" naboer, går den i en "levende" tilstand. Ellers "dør" cellen. På trods af dets enkelhed udviser systemet en enorm variation af adfærd, der svinger mellem kaos og orden. Et af fænomenerne i spillet "Life" er svævefly - kombinationer af celler "bevæger sig" langs gitteret som helhed og interagerer med andre statiske eller bevægelige strukturer. Det er muligt at indstille starttilstanden for cellerne, hvor svæveflyene vil udføre nogle beregninger. Det blev efterfølgende bevist, at Game of Life kunne efterligne Universal Turing Machine fuldstændigt . Den 11. november 2002 byggede Paul Chapman en variant af "Life", som er RMM (Register Machine Minsky ). Den første version af prøven var stor (268'096 levende celler i et område på 4.558 x 21.469 celler) og langsom (20 generationer/sek. ved hjælp af Johan Bontes' Life32 på 400 MHz AMD K6-II) . Således blev det bevist, at i spillet "Life" er det muligt at udføre enhver beregningsalgoritme.

I 1969 udgav den tyske ingeniør Konrad Zuse The Computable Cosmos, hvor han foreslog, at fysikkens love er diskrete i naturen, og at hele universet er en kæmpe cellulær automat. Det var den første bog i det, der nu kaldes digital fysik .

I USSR udgav professor VZ Aladiev en række artikler om teorien om cellulære automater [2] . Som en generel term blev udtrykket " homogene strukturer " brugt. Der er også foreslået anden terminologi for at beskrive visse aspekter af dette problem.

I 1983 offentliggjorde Stephen Wolfram den første af en række artikler, der udforskede elementære cellulære automater . Den uventede kompleksitet af adfærden af disse simple endimensionelle automater fik Wolfram til at foreslå, at kompleksiteten af naturlige systemer skyldes en lignende mekanisme. Derudover formulerer Wolfram i denne periode begrebet ægte tilfældighed og beregningsmæssig irreducerbarhed og foreslår, at en automat med en " regel på 110 " kan være universel ( Turing komplet ). Dette blev bevist i 1990 af hans assistent Matthew Cook.

I 1987 foreslog Brian Silverman Wireworld - celleautomaten .

I 2002 udgav Wolfram en 1280-siders tekst , A New Kind of Science , hvor han argumenterer bredt for, at fremskridt inden for cellulære automater ikke er isolerede, men er meget stabile og af stor betydning for alle områder af videnskaben.

Matematisk definition

En todimensionel cellulær automat kan defineres som et sæt af endelige automater i planet, mærket med heltalskoordinater (i, j), som hver kan være i en af tilstandene : $\sigma _{i,j}$

{\displaystyle \sigma _{i,j}\in \Sigma \equiv \{0,1,2...k-1,k\))

Automaternes tilstand ændres i henhold til overgangsreglen

\sigma _{i,j}(t+1)=\phi (\sigma _{k,l}(t)|(k,l)\in {\mathcal {N))(i,j ))

hvor er et område af punktet . For eksempel er von Neumann-kvarteret defineret som ${\mathcal {N}}(i,j)$ $(i,j)$

{\mathcal {N}}_{N}^{1}(i,j)=\{(k,l)|~|ik|+|jl|\leq 1\}

og kvarteret Moore

{\displaystyle {\mathcal {N}}_{M}^{1}(i,j)=\{(k,l)|~|ik|\leq 1,|jl|\leq 1\))

Antallet af alle mulige overgangsregler bestemmes af antallet af stater og antallet af naboer n og er $\sigma$

N_{r}=\sigma ^{\sigma ^{n))

[3]

Klassifikation

Klassificering efter adfærdstyper

Stephen Wolfram foreslog i sin bog A New Kind of Science 4 klasser, hvor alle cellulære automater kan opdeles afhængigt af typen af deres udvikling. Wolframs klassificering var det første forsøg på at klassificere reglerne i sig selv, snarere end reglernes adfærd isoleret. I rækkefølge af stigende kompleksitet ser klasserne således ud:

Klasse 1: Resultatet af udviklingen af startbetingelserne er en hurtig overgang til homogen stabilitet. Eventuelle inhomogene strukturer forsvinder hurtigt.
Klasse 2: Resultatet af udviklingen af startbetingelserne er en hurtig overgang til en uforanderlig inhomogen tilstand eller fremkomsten af en cyklisk sekvens. De fleste af de oprindelige tilstandsstrukturer forsvinder hurtigt, men nogle forbliver. Lokale ændringer i startforholdene har en lokal karakter på det videre forløb af systemets udvikling.
Klasse 3: Resultatet af udviklingen af næsten alle startbetingelser er pseudo-tilfældige, kaotiske sekvenser. Eventuelle stabile strukturer, der dukker op, bliver næsten øjeblikkeligt ødelagt af støjen omkring dem . Lokale ændringer i startforholdene har en ubestemt effekt på systemets udvikling.
Klasse 4: Evolution resulterer i strukturer, der interagerer på komplekse måder for at danne lokale, stabile strukturer . Som et resultat af evolutionen kan nogle sekvenser af klasse 2 beskrevet ovenfor opnås. Lokale ændringer i startforholdene har en ubestemt effekt på systemets udvikling. Nogle cellulære automater i denne klasse har Turing-universalitetsegenskaben , som bevist for Rule 110 og Life -spillet .

Sådanne definitioner er for det meste kvalitative og kan fortolkes på forskellige måder. Her er, hvad Wolfram har at sige om det:

I næsten hvert forsøg på klassificering vil der opstå situationer, hvor et objekt ifølge en egenskab kan henføres til en klasse og til en anden egenskab til en anden klasse. Situationen er den samme med cellulære automater: Der er regler, der viser egenskaber, der samtidig er iboende i den ene og den anden klasse.

Originaltekst (engelsk)[ Visskjule] ... med næsten enhver generel klassifikationsordning er der uundgåeligt tilfælde, som bliver tildelt en klasse ved én definition og en anden klasse ved en anden definition. Og sådan er det med cellulære automater: der er nogle gange regler ... der viser nogle funktioner i en klasse og nogle af en anden.

Totalistiske cellulære automater

Der er en særlig klasse af cellulære automater kaldet totalistic . Ved hvert trin i udviklingen af en cellulær automat er cellens værdi lig med et eller andet heltal (normalt valgt fra et endeligt sæt ), og cellens nye tilstand bestemmes af summen af værdierne af naboceller og muligvis den tidligere tilstand af cellen. Hvis tilstanden af en celle i et nyt trin afhænger af dens tidligere tilstand, kaldes en sådan cellulær automatik ekstern totalistisk . The Game of Life er et eksempel på en ekstern totalistisk cellulær automat med et sæt celleværdier . ${0,1}$

Udtrykket totalistic kommer fra det engelske totalistic . Til gengæld kan total oversættes som en sum , hvilket afspejles i princippet om drift af denne type automater, når den nye værdi af en celle afhænger af summen af værdierne af andre celler.

Relaterede definitioner af cellulære automater

Der er mange mulige generaliseringer af begreberne cellulære automater.

En af dem er brugen af et gitter, ikke med firkanter ( hyperkuber i det flerdimensionale tilfælde), men med andre geometriske former i sin kerne. For eksempel, hvis feltet er repræsenteret af en sekskantet parket , så ville sekskanterne være celler. Nogle gange viste sådanne cellulære automater sig dog at være identiske med cellulære automater på et gitter med firkantede celler, kun i dette tilfælde var det nødvendigt at indføre særlige regler for forhold til naboceller. En anden måde at generalisere på er at bruge et uregelmæssigt gitter (for eksempel i form af en Penrose-mosaik ).

En anden måde er at bruge probabilistiske regler. Sådanne cellulære automater kaldes stokastiske . I sådanne systemer er der givet sandsynlighed for, at cellen ved næste trin vil skifte farve til en anden. Eller, for eksempel, i spillet " Life " tilføjes en regel om, at en celle med en vis sandsynlighed kan ændre sin farve til det modsatte, mens andre regler for denne cellulære automat forbliver uændrede.

Definitionen af cellekvarter kan ændre sig over tid og/eller rum. For eksempel, i det første trin vil naboerne være vandret tilstødende celler, og i det andet trin vil de være lodret tilstødende.

I cellulære automater påvirkes den nye tilstand af en celle ikke af de nye tilstande af tilstødende celler. Reglen kan ændres: du kan gøre det sådan, at for eksempel i 2 gange 2 blokke afhænger cellernes tilstand af tilstanden af cellerne inde i blokken og af de samme tilstødende blokke.

Der er kontinuerlige cellulære automater . I sådanne systemer, i stedet for et diskret sæt af tilstande, bruges kontinuerlige funktioner (normalt defineret på intervallet ). $[0,1]$

Reversibilitetsegenskab

En cellulær automat siges at være reversibel , hvis der kun er én tidligere konfiguration for hver aktuelle konfiguration. Hvis vi betragter en cellulær automat som en funktion, der kortlægger en konfiguration til en anden, så indebærer reversibilitet denne funktions bijektivitet . Hvis en cellulær automat er reversibel, så kan dens omvendte udvikling også beskrives af en cellulær automat. Konfigurationer, der ikke har forgængere, det vil sige uopnåelige i en given cellulær automat, kaldes " Edens haver ".

For endimensionelle cellulære automater er der algoritmer til at bestemme reversibilitet eller irreversibilitet. Der er dog ingen sådanne algoritmer for cellulære automater med to eller flere dimensioner.

Reversible cellulære automater bruges ofte til at modellere fysiske fænomener såsom væske- og gasdynamik, fordi de adlyder termodynamikkens love . Sådanne automater er specielt designet til at være reversible. Sådanne systemer er blevet undersøgt af Tommaso Toffoli og Norman Margolus. Der er flere typer vendbare tilstandsmaskiner. De mest kendte er den andenordens cellulære automat og blokcelleautomaten . Begge disse modeller følger en noget modificeret version af definitionen af en cellulær automat, men det er blevet bevist, at de kan emuleres af en traditionel cellulær automat med en meget større kvarterstørrelse og antal stater. Det er også blevet bevist, at enhver reversibel cellulær automat kan emuleres af en blokcellulær automat.

Elementære cellulære automater

Den enkleste ikke-trivielle cellulære automat vil være en endimensionel cellulær automat med to mulige tilstande, og naboerne til en celle vil være de celler, der støder op til den. Sådanne automater kaldes elementære. Tre celler (den centrale, dens naboer) genererer kombinationer af disse tre cellers tilstande. Baseret på analysen af triplens aktuelle tilstand træffes der endvidere en beslutning om, hvorvidt den centrale celle vil være hvid eller sort ved næste trin. I alt er der mulige regler. Disse 256 regler er kodet i henhold til Wolframs kode , en standardkonvention, en regel, der blev foreslået af Wolfram . I nogle artikler er disse 256 regler blevet undersøgt og sammenlignet. Det mest interessante er reglerne med tallene 30 og 110 . De to billeder nedenfor viser udviklingen af disse regler. Den oprindelige betingelse for hver automat er, at en central celle er sort, resten er hvide. Diskret tid er plottet langs aksen, og tilstande af automatceller er plottet langs aksen. $2^{3}=8$ $2^{8}=256$ $Y$ $x$

Regel 30

Nuværende tilstand	111	110	101	100	011	010	001	000
Ny tilstand af den centrale celle	0	0	0	en	en	en	en	0

Regel 110

Nuværende tilstand	111	110	101	100	011	010	001	000
Ny tilstand af den centrale celle	0	en	en	0	en	en	en	0

Regel 161

Nuværende tilstand	111	110	101	100	011	010	001	000
Ny tilstand af den centrale celle	en	0	en	0	0	0	0	en

Regel 30 udviser klasse 3-adfærd, hvilket betyder, at udviklingen af simple begyndelsesbetingelser fører til kaotisk , tilsyneladende tilfældig dynamik.

Regel 110 , ligesom Game of Life , udviser klasse 4 adfærd, der ikke er helt tilfældig, men mangler periodicitet. I dette tilfælde opstår strukturer, der interagerer med hinanden på en ikke-oplagt, kompleks måde. Mens han skrev A New Kind of Science , beviste Stephen Wolframs assistent Matthew Cook i 1994 , at nogle af de strukturer, der genereres af en regel, er tilstrækkeligt forskellige til at være Turing komplet . Dette faktum er af interesse, fordi regel 110 i sin kerne er et simpelt endimensionelt system. Det er også et godt argument, at klasse 4-systemer i en eller anden forstand er universelle. Matthew Cooke fremlagde sit bevis på Santa Fe Institute-konferencen i 1998 , men Wolfram forbød det at blive inkluderet i papirversionen af konferenceforhandlingerne, fordi han ikke ønskede, at det skulle blive offentliggjort, før A New Kind of Science blev offentliggjort . I 2004 blev Cooks bevis offentliggjort i Wolframs tidsskrift Complex Systems (udgave 15, bind 1), 10 år efter at Cook først præsenterede det. Regel 110 var grundlaget for at bygge de mindste Turing-maskiner .

Regel 161 genererer fraktale strukturer, som kan ses på figuren. Man kan se indlejrede lignende trekanter .

Regelrummet for cellulære automater

Den enkleste endimensionelle cellulære automat er specificeret ved hjælp af otte bit. Således er alle reglerne for den cellulære automatik placeret på hjørnerne af den 8-dimensionelle enhedsterning . En sådan hyperkube er rummet for alle mulige endimensionelle cellulære automater. For en endimensionel cellulær automat, hvor naboerne til en celle er naboer til dens naboer, er der brug for en smule, og rummet for alle mulige regler vil være en 32-dimensionel enhedsterning. Afstanden mellem to cellulære automater kan betragtes som antallet af trin, der kræves for at flytte fra en regel til en anden langs kanterne af en flerdimensionel terning. Denne afstand kaldes Hamming-afstanden . $2^{5}=32$

Studiet af rummet af regler for cellulære automater giver os mulighed for at besvare spørgsmålet, som stilles som følger: er de regler, der er tæt i forhold til hinanden, som genererer cellulære automater, der ligner hinanden (med hensyn til dynamik). Grafisk repræsentation af en højdimensionel hyperkube på et todimensionalt plan er en meget vanskelig opgave. Men på et todimensionalt plan kan man nemt forestille sig udviklingsprocessen for en endimensionel cellulær automat. I dette tilfælde plottes diskret tid langs den ene akse, og de tilsvarende tilstande af den cellulære automat plottes langs den anden. I tilfælde af en todimensionel cellulær automat kan en tredje akse tilføjes. I dette tilfælde vil to akser svare til tilstandene for den cellulære automat, og den tredje akse vil svare til diskret tid. Udviklingsprocessen for en sådan automat er en vis tredimensionel figur i rummet. Sådanne eksperimenter er beskrevet mere detaljeret i Stephen Wolframs bog A New Kind of Science . Undersøgelser har vist, at cellulære automater klassificeret som klasse 1 havde færre 1 bits i regellinjen, og de var koncentreret på cirka ét sted på hyperkuben. Samtidig havde klasse 3 regler et større (ca. 50%) antal på 1 bit.

For større regelrum af cellulære automater blev det vist, at klasse 4-regler er placeret mellem klasse 1 og 3.

Denne observation fører til begrebet kanten af kaos som anvendt på teorien om cellulære automater og minder om konceptet om en faseovergang i termodynamikken .

Cellulære automater i det naturlige miljø

Nogle levende organismer udviser egenskaberne af cellulære automater. Skalfarven af en række marine bløddyr , såsom dem af slægterne Conus eller Cymbiola , er genereret af en naturlig endimensionel cellulær automat, hvis evolutionære resultat ligner regel 30 . Deres pigmentceller er arrangeret i en tynd strimmel langs kanten af skallen. Sekretionen af pigmentet i hver celle afhænger af den aktiverende og hæmmende aktivitet af naboceller. Når skallen vokser, danner et bånd af celler et farvet mønster på dens overflade. Farven af skæl af firbenet Timon lepidus er beskrevet af en stokastisk cellulær automat [4] .

Planter regulerer ind- og udstrømningen af gasformige stoffer gennem mekanismen af cellulære automater. Hver stomata på bladoverfladen fungerer som en automatcelle [5] .

Neurale netværk kan også bruges som cellulære automater. Det komplekse bevægelige mønster på blækspruttehud er en afspejling af aktiveringsmønstre i dyrehjernen.

Belousov-Zhabotinsky-reaktionen er en rum-tid kemisk oscillator, der kan modelleres af en cellulær automat. I 1950'erne opdagede A. M. Zhabotinsky , der fortsatte med B. P. Belousovs arbejde , at et tyndt homogent lag af en blanding af visse kemikalier er i stand til at danne bevægelige geometriske mønstre, såsom koncentriske cirkler og spiraler.

Cellulære automater bruges også til modellering af økosystemer og populationsdynamik [6] .

Anvendelser af cellulære automater

Computerprocessorer

Processorer på cellulære automater er den fysiske implementering af ideerne om en cellulær automat. Processorelementer er placeret på et ensartet gitter af identiske celler. Cellernes tilstand bestemmes af interaktionen med naboceller. Til gengæld kan nabolaget bestemmes af von Neumann eller af Moore . En sådan processor er i form af en systolisk matrix . Samspillet mellem partikler kan implementeres ved hjælp af elektrisk strøm, magnetisme, vibration (for eksempel fononer ) eller ved hjælp af enhver anden metode til informationsoverførsel. Overførsel af information kan ske på flere måder, der ikke involverer brug af dirigenter til at overføre information mellem elementer. Denne måde at designe processoren på er meget anderledes end de fleste processorer i brug i dag og bygget efter von Neumann princippet , hvor processoren er opdelt i flere sektioner, der kan interagere med hinanden ved hjælp af direkte ledere.

Kryptografi

Regel 30 er blevet foreslået som en mulig blokchiffer til brug i kryptografi . Todimensionelle cellulære automater bruges til at generere tilfældige tal . Cellulære automater foreslås til brug i offentlige nøglekryptosystemer . I dette tilfælde er envejsfunktionen resultatet af udviklingen af en finit cellulær automat, hvis begyndelsestilstand er svær at finde . Ifølge en given regel er det let at finde resultatet af udviklingen af en cellulær automat, men det er meget vanskeligt at beregne dens tidligere tilstande.

Simulering af fysiske processer

Cellulære automater bruges til computersimulering af rekrystalliseringsprocesser [7] .

Grundlæggende fysik

Som Andrew Ilachinski påpeger i sin bog Cellular Automata (originaltitel Cellular Automata ), har mange forskere spekuleret på, om vores univers er en cellulær automat. Andrew Ilachinski påpeger, at betydningen af dette spørgsmål bedre kan forstås med en simpel observation, der kan gøres som følger. Overvej udviklingen af Regel 110 : Hvis det var noget som "fremmed fysik" (oprindelig - fremmed fysik ), hvordan kunne de nye mønstre så beskrives? Hvis du ikke vidste, hvordan det endelige billede af automatens udvikling blev opnået, kunne du antage, at denne figur på en eller anden måde afspejler bevægelsen af nogle partikler. Så gøres følgende antagelse: måske kan vores verden, godt beskrevet af elementær partikelfysik , være en cellulær automat på et grundlæggende niveau.

En komplet teori baseret på disse udsagn er dog stadig langt fra at blive betragtet som fuldstændig (såvel som at den på nogen måde er almindeligt accepteret). Båret væk og udviklet denne hypotese, kommer forskere til interessante konklusioner om, hvordan denne teori kan bruges til at beskrive verden omkring. Marvin Minsky , en AI - pioner , udviklede en måde at studere partikelinteraktioner ved hjælp af en 4D-cellulær automat. Konrad Zuse , kendt som skaberen af den første virkelig fungerende programmerbare computer Z3 , var engageret i cellulære automater på uregelmæssige gitter for at studere informationsindholdet i partikler. Edward Fredkin introducerede, hvad han kalder "finite universe hypothesis" (original finite nature hypothesis ). Meningen med hypotesen er det

… enhver størrelse i fysik, inklusive tid og rum, er begrænset og diskret.

Originaltekst (engelsk)[ Visskjule] i sidste ende vil enhver mængde fysik, inklusive rum og tid, vise sig at være diskret og endelig.

Fredkin og Wolfram er konsekvente tilhængere af digital fysik .

Nobelpristageren Gerard 't Hooft udviklede en fortolkning af kvantemekanik baseret på cellulære automater [8] .

Se også

Specifikke regler

Problemer under overvejelse

Shooter-synkroniseringsproblem

Relaterede artikler

Noter

↑ Pickover, Clifford A., Pickover, Clifford A. Matematikbogen: Fra Pythagoras til den 57. Dimension, 250 milepæle i matematikkens historie. - Sterling Publishing Company, Inc., 2009. - ISBN 978-1402757969 .
↑ Viktor Aladiev om de grundlæggende elementer i homogene strukturer og teorien om cellulære automater . Hentet 31. maj 2021. Arkiveret fra originalen 2. juni 2021. (ubestemt)
↑ AGHoekstra, J.Kroc, P.Sloot. Simulering af komplekse systemer med cellulære automater. Springer, 2010. ISBN 978-3-642-12202-6
↑ Liana Manukyan, Sophie A. Montandon, Anamarija Fofonjka, Stanislav Smirnov & Michel C. Milinkovitch. En levende mesoskopisk cellulær automat lavet af hudskæl // Nature. - 2017. - Bd. 544.—S. 173–179. - doi : 10.1038/nature22031 .
↑ Peak, West og Messinger, Mott. Beviser for kompleks, kollektiv dynamik og emergent, distribueret beregning i planter (engelsk) // Proceedings of the National Institute of Science of the USA: journal. - 2004. - Bd. 101 , nr. 4 . - P. 918-922 . - doi : 10.1073/pnas.0307811100 . - . — PMID 14732685 .
↑ Andreas Deutsch og Sabine Dormann. 4.2 Biologiske applikationer // Cellulær automatonmodellering af biologisk mønsterdannelse. - Springer Science + Business Media, 2017. - ISBN 978-1-4899-7980-3 .
↑ KGF Janssens. En indledende gennemgang af cellulær automatmodellering af bevægelige korngrænser i polykrystallinske materialer // Mathematics and Computers in Simulation. - 2010. - Bd. 80. - P. 1361-1381. - doi : 10.1016/j.matcom.2009.02.011 .
↑ 't Hooft, Gerard. Den cellulære automatonfortolkning af kvantemekanik . - Springer International Publishing Springer, 2016. - ISBN 978-3-319-41285-6 , 978-3-319-41284-9.

Links

Toffoli T., Margolus N. Machines of cellular automata, M.: Mir, 1991. ISBN 5-03-001619-8
Life Universal Computer Arkiveret 8. december 2006 på Wayback Machine
S. Wolfram "New Kind of Science" Arkiveret 8. maj 2007 på Wayback Machine
Engelsk side med masser af information om CA, opdateret af Tim Tyler se usenet: comp.theory.cell-automata Arkiveret 12. oktober 2007 på Wayback Machine
Usenet-konference om KA
KA i WolframMathWorld Mathematical Encyclopedia Arkiveret 26. marts 2008 på Wayback Machine
Vanag V. K. Studie af rumligt distribuerede dynamiske systemer ved brug af probabilistiske cellulære automater // Uspekhi fizicheskikh nauk : zhurnal. - Det russiske videnskabsakademi , maj 1999. - T. 169 , nr. 5 . - S. 481-505 . (Russisk)
Lineær cellulær automat, Turing maskine ækvivalens Arkiveret 17. juli 2014 på Wayback Machine
Aristov A. O. Teori om kvasicellulære netværk: videnskabelig monografi - M: MISiS, 2014. - 188 s. ISBN 978-5-600-00321-7

Ordbøger og encyklopædier	Britannica (online) Universalis
I bibliografiske kataloger	BNF : 12144918z GND : 4190671-8 J9U : 987007284821605171 LCCN : sh85021692 NKC : ph119038

Conways Game of Life og andre cellulære automater

Konfigurationsklasser

Konfigurationer

Svævefly
Blok
R-pentomino
Pentadecatlon

Vilkår

Andre rumfartøjer på et
todimensionelt gitter

Livsagtig	Dag og nat Liv uden død vildt liv frø
Andet	sandbunke model Von Neumann kampgevær Wireworld Ant Langton Critters Worms of Paterson

Et-dimensionelt rumfartøj

Software og algoritmer

Golly
Mireks
hashlife

KA-forskere