En mobilautomat består av et vanlig rutenett av "celler" som hver inneholder en "tilstand" valgt fra et endelig sett og som kan endres over tid. Tilstanden til en celle på tidspunktet t + 1 er en funksjon av tilstanden på tidspunktet t for et endelig antall celler som kalles "nabolaget". For hver nye tidsenhet blir de samme reglene brukt samtidig på alle celler i rutenettet, og produserer en ny "generasjon" av celler helt avhengig av forrige generasjon.
Studert i matematikk og teoretisk informatikk , er mobilautomater både en diskret dynamisk systemmodell og en beregningsmodell . Den cellulære automatmodellen er bemerkelsesverdig for forskjellen mellom enkelheten i definisjonen og kompleksiteten som visse makroskopiske atferd kan oppnå : utviklingen over tid av alle celler reduseres ikke (ganske enkelt) til den lokale regelen som definerer systemet. Som sådan utgjør den en av standardmodellene i studiet av komplekse systemer .
Den enkleste ikke-trivielle mobilautomaten vi kan tenke oss består av et endimensjonalt rutenett av celler som bare kan ta to tilstander ("0" eller "1"), med et nabolag som består av hver celle i seg selv. og de to cellene ved siden av den.
Hver av cellene kan ta to tilstander, det er 2 3 = 8 mulige konfigurasjoner (eller mønstre) for et slikt nabolag. For at mobilautomaten skal fungere, er det nødvendig å definere hva staten må være i neste generasjon av en celle av hver av disse grunnene. Det er 2 8 = 256 forskjellige måter å gjøre dette på, så 256 forskjellige mobilautomater av denne typen.
Automatene til denne familien sies å være “elementære”. De er ofte betegnet med et helt tall mellom 0 og 255 hvis binære representasjon er sekvensen av tilstander tatt av automaten på de påfølgende mønstrene 111, 110, 101, etc.
La oss som et eksempel se på mobilautomaten definert av følgende tabell, som gir evolusjonsregelen:
Opprinnelig grunn ( t ) | 111 | 110 | 101 | 100 | 011 | 010 | 001 | 000 |
---|---|---|---|---|---|---|---|---|
Neste verdi av den sentrale cellen ( t +1) | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
Dette betyr at hvis for eksempel på en gitt tid t , er en celle i tilstanden "1", den venstre naboen i tilstanden "1" og den høyre naboen i tilstanden "0" (kolonne 2 i tabellen), på tidspunktet t + 1 vil det være i tilstanden "0".
Hvis vi starter fra et innledende rutenett der alle cellene er i tilstanden "0" unntatt en, ender vi opp med:
der hver rad er resultatet av forrige rad.
Etter konvensjon kalles denne regelen "regel 30", fordi 30 i desimal er skrevet 00011110 i binær og 00011110 er den andre linjen i tabellen ovenfor, som beskriver evolusjonsregelen.
" Livets spill " er en todimensjonal mobilautomat der hver celle kan ta to verdier ("0" eller "1", men vi snakker snarere om "levende" eller "død") og hvor dens fremtidige tilstand er bestemt av dets nåværende tilstand og av antall levende celler blant de åtte som omgir den:
Tilsynelatende enkle, disse reglene gir mye kompleksitet.
På samme prinsipp kan vi forestille oss et stort antall regler ved å variere fødsels- eller overlevelsesterskelen, eller ved å legge til flere tilstander osv. Blant disse variasjonene kan vi sitere:
For å bestemme endringene i tilstanden til en celle, tar noen bare hensyn til de nærmeste naboene til boksen som er vurdert, men andre tar også hensyn til tilstanden til nabocellene innen en radius på to bokser, eller enda mer. Andre tillegger også større bokser i nabolaget større vekt enn andre ( WeightedLife ).
De mulige reglene for å definere en mobilautomat er svært mange, selv med et lite antall stater og et lite nabolag :
2 stater | 3 stater | 4 stater | 5 stater | |
---|---|---|---|---|
2 naboer | 16 | 19 683 | 4.294.967.296 | |
3 naboer | 256 | 7625597484987 | ||
4 naboer | 65.536 | |||
5 naboer | 4.294.967.296 | |||
6 naboer |
Modellen for mobilautomater tilbyr derfor et enormt felt av leting. Det er ikke vanskelig å programmere en mobilautomatsimulator, og nettet er fullt av mer eller mindre vellykkede prestasjoner. Mirek Wojtowicz 'side tilbyr for eksempel simuleringsprogramvare og et veldig rikt galleri med eksempler: Mireks Cellebration . Et annet interessant simulatoreksempel er Golly . Den er hovedsakelig dedikert til livets spill og optimalisert for denne automaten ved å bruke spesielt firetre kombinert med hasj .
På 1940-tallet studerte Stanislaw Ulam krystallvekst ved Los Alamos National Laboratory og modellerte den på et rutenett. Samtidig jobbet John von Neumann , Ulams kollega i Los Alamos, med selvrepliserende systemer og hadde problemer med å forklare sin opprinnelige modell av en robot som ville kopiere seg fra et sett med deler. Ulam foreslo at han skulle hente inspirasjon fra arbeidet sitt, noe som fikk von Neumann til å utforme en abstrakt matematisk modell for hans problem. Resultatet var "kopimaskin og universal konstruktør " ( universal konstruktør og kopi på engelsk), den første mobilautomaten: den var basert på et todimensjonalt rutenett der hver celle kunne ta 29 stater. Von Neumann konstruerte et merkelig mønster der og demonstrerte at han uendelig kunne produsere kopier av seg selv.
I 1969 publiserte Gustav Arnold Hedlund Endomorphisms and Automorphisms of the Shift Dynamical System , en monografi på rundt 60 sider som syntetiserer 10 års forskning av et samfunn som arbeider innen symbolsk dynamikk (en gren av studiet av dynamiske systemer i matematikk, spesielt grunnlagt av M. Morse og GA Hedlund). Det er denne publikasjonen som legger det matematiske grunnlaget for studiet av mobilautomater som spesielle dynamiske systemer.
Også i 1969 ga Konrad Zuse ut Rechnender Raum ("When Space Calculates") der han antydet at fysiske lover var diskrete og at universet var resultatet av en gigantisk mobilautomat.
På 1970-tallet oppnådde en todimensjonal, to-statlig mobilautomat kalt " Game of Life ", oppfunnet av John Conway , stor suksess, spesielt blant det nye datasamfunnet. Den ble popularisert av Martin Gardner i en artikkel i Scientific American .
I 1983 publiserte Stephen Wolfram den første av en serie publikasjoner der han systematisk analyserte en type veldig enkle mobilautomater. Kompleksiteten i deres oppførsel, indusert av elementære regler, førte ham til å anta at lignende mekanismer kunne forklare komplekse fysiske fenomener, ideer som han utviklet i sin bok A New Kind of Science utgitt i 2002.
Hvis populariteten til modellen til mobilautomater i stor grad kommer fra en eksperimentell tilnærming, ble den fra begynnelsen nærmet som et matematisk objekt av Von Neumann . Mest formelle arbeid med mobilautomater bruker definisjonen nedenfor, selv om modellen innrømmer mange interessante generaliseringer og variasjoner .
En mobilautomat er en -uplett der:
Tildelingen av en tilstand til hver celle i nettverket kalles da konfigurasjon : en konfigurasjon er et element av , det vil si en funksjon av in .
Med denne endelige og lokale beskrivelsen forbinder vi den globale funksjonen til evolusjon av automaten , som virker på konfigurasjonene og som er definert av for enhver konfigurasjon (hvor ).
Cellular automata har blitt studert som dynamiske systemer siden 1960-tallet med GA Hedlunds arbeid. Når størrelsen og alfabetet er festet, kan det gis romkonfigurasjoner for beregningen av Cantor etter avstanden definert av
Settet med mobilautomater i alfabetet og dimensjonen er da preget av Curtis-Hedlund-Lyondon-teoremet: er den globale funksjonen til en slik mobilautomat hvis og bare hvis det er en kontinuerlig funksjon som pendler med skiftfunksjonene (hvilken som helst posisjon i celleoppstillingen tilsvarer en skiftfunksjon ).
Derfra kan mobilautomater studeres med alle verktøyene i teorien om dynamiske systemklassikere, kaoteteorien og ergodisk teori , når vi utruster konfigurasjonsrommet til et mål .
Denne grenen av cellulær automatteori er fortsatt åpen og er fremdeles gjenstand for forskning (se her for et eksempel på et viktig uløst spørsmål til dags dato).
Vi kan betrakte mobilautomater som diskrete dynamiske systemer så vel som beregningssystemer . Dermed er hver automat i stand til å utføre bestemte beregninger eller vise visse dynamiske atferd. Enten man inntar et eller annet synspunkt, kan man stille det samme spørsmålet: er det en automat som er i stand til å gjøre alt som mobilautomater kan gjøre? En slik automat sies da å være universell .
Forestillingen om universalitet tilsvarer en veldig enkel og veldig generell idé, men vi må være forsiktige med det faktum at i henhold til betydningen vi legger bak uttrykket "i stand til å gjøre" er ikke den universelle automaten den samme. Vi kan skille mellom to typer forestillinger om universalitet for mobilautomater: Turing universalitet som er assosiert med beregningskapasiteten og iboende universalitet som er assosiert med evnen til å produsere visse dynamiske atferd.
Det bemerkelsesverdige faktum er at for hver av disse forestillingene er det universelle automater. Det skal også bemerkes at forestillingen om indre universalitet er sterkere enn Turing-universalitet: faktisk, uten å gå i detaljer, kan en automat som er i stand til å simulere alle automater, spesielt simulere en Turing-universal-automat og derfor utføre alle Turing-beregninger. I kontrast er det Turing-universelle mobilautomater som ikke er iboende universelle.
Turing UniversalityTuring universalitet er en tilpasning til mobilautomater av universalitet for beregning . Vi kan definere dette begrepet som kapasiteten til en automat for å simulere en universell Turing-maskin. Denne muligheten for å simulere en Turing-maskin av en mobilautomat er veldig enkel og var kjent fra John von Neumanns arbeid . Det er flere måter å formalisere det på, og det følgende er en av de enkleste. Hvis en Turing-maskin fungerer med et båndalfabet og et sett med tilstander , kan vi definere en mobilautomat som er i stand til å simulere :
Vi møter ofte en mer generell (men mer uformell) betydning av Turing-universalitet: en mobilautomat er Turing-universal hvis den er i stand til å simulere et Turing-komplett beregningssystem . Begrepet simulere er sjelden formalisert i en generell ramme. Det viktige poenget er at transformasjonen av innganger / utganger fra det simulerte systemet til innganger / utganger fra simulatoren forblir enkel: uten denne tilstanden får vi en forestilling om ingen interesse på grunn av automatene som ikke gjør noe ( for eksempel identitet ) blir universell takket være inngangs- / utgangstransformasjoner som gjør all beregningen for dem.
Iboende universalitetEn iboende universell mobilautomat er en automat som er i stand til trinn for trinn å simulere oppførselen til en hvilken som helst mobilautomat med samme dimensjon. Mer spesifikt er ideen om trinnvis simulering basert på følgende prinsipper:
Så, for eksempel, er livets spill i stand til å simulere trinn for trinn automaten med to tilstander (svart og rødt) som utfører en enkel forandring av stater mot sørøst:
For å simulere oppførselen til fra en viss innledende konfigurasjon, er det tilstrekkelig å produsere en konfigurasjon av livets spill der hver gruppe enten er fylt med døde celler, eller med en glider avhengig av tilstanden til cellen som samsvarer med den .
Det er bemerkelsesverdig at med dette veldig enkle simuleringsprinsippet, er noen automater i stand til å simulere hvilken som helst mobilautomat fra hvilken som helst konfigurasjon: dette er tilfelle med livets spill som forklart i neste avsnitt . Selvfølgelig, for å simulere automater med flere og flere tilstander, bruker en iboende universell automat større og større grupper av celler. Faktisk, med en fast type gruppe celler, er det bare et endelig antall mulige simuleringer. Dermed, når vi observerer en evolusjon av livets spill på en skjerm (hvor stor den også er), ser vi ikke all atferd som livets spill er i stand til å simulere; Likevel er denne automaten i stand til å produsere all oppførsel til mobilautomaten.
EksemplerHistorisk sett er den første mobilautomaten konstruert med en egenskap av universalitet (Turing i dette tilfellet) den universelle konstruktøren til John von Neumann : den handler om en dimensjon 2 automaton med 29 tilstander som dessuten er i stand til s 'selvreplikasjon.
Når det gjelder forestillingen om indre universalitet, måtte vi vente til 1970-tallet med arbeidet til ER Banks som foreslo en mobilautomat av dimensjon 2 med 2 stater og 5 naboer. Det tilbyr også en iboende universell 1-dimensjonal automat med 5 stater, men hvis nabolag er enormt.
Det mest berømte eksemplet på en universell automat er absolutt livets spill . Det ble bevist Turing-universal i boken Winning Ways for Your Mathematical Plays . Beviset består av bygningsdeler av konfigurasjoner som kan monteres og som tilsvarer alle komponentene som er nødvendige for fremstilling av logiske kretser (ledninger, ledningskryssinger, duplisering, logiske porter , etc.). En komplett konstruksjon av en Turing Machine in the Game of Life finner du på Paul Rendells nettsted . Fra de samme ideene har livets spill mer nylig blitt bevist å være iboende universelt.
For dimensjon 1 har det nylig skjedd et gjennombrudd angående Turing-universalitet: Mr. Cook har bevist at den elementære mobilautomat nummer 110 er Turing-universal. Han presenterte ideene sine allerede i 1998 på CA98- konferansen , men dette resultatet ble (delvis) formidlet skriftlig bare i 2002 gjennom A New Kind of Science av S. Wolfram. Faktisk var Mr. Cook ansatt av Wolfram Research for å jobbe med boken A New Type of Science, og hans arbeid ble ikke publisert i CA98-lovene etter en søksmål basert på en ikke- avsløringsavtale . Det fulle beviset på Dr. Cooks resultat ble endelig publisert i et vitenskapelig tidsskrift i 2004.
På den annen side vet vi fortsatt ikke i dag om automaten 110 er iboende universell eller ikke. Den minste 1-dimensjonale automaten med et nabolag på 3 celler som har vist seg å være iboende universell til dags dato, har 4 tilstander.
Generelt er det ekstremt vanskelig å bestemme den generelle oppførselen til en mobilautomat ved å undersøke dens lokale overgangsregel. Dette resulterer i ubestemmelsesresultater som påvirker de enkleste egenskapene. På dette feltet kan vi sitere arbeidet til Jarkko Kari, som ved å bruke de resultatene som allerede var kjent på fliser på en smart måte , viste at følgende problemer var ubesluttsomme:
Det faktum at mobilautomater kan simulere en hvilken som helst Turing-maskin , fører også til uavgjørelige problemer av en annen art. For eksempel, for noen mobilautomater, er også følgende problemer uavgjørelige :
Som forklart ovenfor er de lokale reglene for mobilautomater for mange for en uttømmende studie, og forutsigelsen av oppførselen i henhold til den lokale regelen er et veldig vanskelig problem generelt. Dette er grunnen til at studien av mobilautomater ofte har vært begrenset til bestemte familier, enten fordi de lettere benytter seg av analyser, eller fordi de tilsvarer en interessant egenskap.
En mobilautomat er reversibel hvis det eksisterer en mobilautomat som de to globale funksjonene til evolusjon og er omvendt av hverandre: er identitetsfunksjonen. Intuitivt “går tilbake i tid” av evolusjonen av og omvendt, “går tilbake i tid” av evolusjonen av . Ved Hedlund teorem, kan vi karakterisere reversibel cellular automata som de som global funksjon er bijective .
Denne klassen har blitt veldig studert, særlig fordi den gir en modell som nærmer seg den virkelige fysiske verden, antatt å være reversibel i mikroskopisk skala (se artikkelen om reversibilitet og irreversibilitet i termodynamikk ). T. Toffoli og N. Margolus er blant de første som er spesielt interessert i reversible mobilautomater. Interessen ligger også i søket etter reversible beregningssystemer som skal forbruke mindre energi i henhold til Landauer-prinsippet . Det er nå fastslått at visse reversible mobilautomater er universelle Turing (verk av Kenichi Morita).
AnerkjennelseDet er algoritmisk umulig å skille reversible mobilautomater fra de som ikke er når dimensjonen er større enn 2. På den annen side er det i dimensjon 1 en veldig effektiv algoritme.
En annen måte å presentere denne forskjellen mellom dimensjon 1 og større dimensjoner er som følger: størrelsen på nabolaget til det inverse av en automat kan ikke begrenses rekursivt i henhold til størrelsen på nabolaget når dimensjonen er 2 eller mer, mens den er polynomielt avgrenset i dimensjon 1 (et nylig resultat viser til og med at båndet er lineært ).
EksemplerDet er enkelt å konstruere reversible mobilautomater. For dette finnes flere former for konstruksjon.
Celleautomater er generelt dynamiske ikke-lineære systemer , noe som gjør studiet av konvensjonelle verktøy vanskelig. Men denne generelle sannheten hindrer ikke visse mobilautomater i å ha en mer eller mindre streng form for linearitet.
DefinisjonFormelt et alfabet automat sies å være lineær hvis vi kan gi en gruppe lov som:
I dette tilfellet, hvis vi strekker oss til en operasjon som virker celle for celle på konfigurasjonsområdet, er den globale funksjonen assosiert med automaten virkelig en lineær funksjon .
Linearitet letter studiet av automatikkens dynamikk betydelig. Dermed er det tilstrekkelig å kjenne dynamikken til en lineær automat på en " basis " av rommet til dens konfigurasjoner for å utlede fra den ved linearitet sin oppførsel over hele rommet. For en slik base kan man velge det (endelige) settet med konfigurasjoner overalt lik ( nøytral av ) bortsett fra muligens i den sentrale cellen.
TilsetningsautomaterEn av de mest studerte familiene til lineære automater er den av såkalte additive automata , introdusert av O. Martin, A. Odlyzko og S. Wolfram i. Disse kontrollerne er definert som følger:
Det typiske eksempelet er en der alle koeffisientene er lik 1: den lokale regelen består da i å ta summen modulo av alle cellene i nabolaget. I dimensjon 1 er således den elementære mobilautomaten 90 additiv: dens overgangsfunksjon består i å lage modulo 2-summen av tilstandene til de to naboene til cellen. Det er nok å kjenne oppførselen til denne automaten i konfigurasjonen overalt lik 0 unntatt i sentrum hvor det er verdt 1 å utlede sin generelle oppførsel fra den ved superposisjon:
Den elementære automaten 102 er også additiv. Dens virkning på konfigurasjonen produserer en Pascal-trekant modulo 2 (som også gir en tilnærming til Sierpinski-trekanten ). Så fra , cellen etter trinn er i tilstanden:
Ved superposisjon utleder vi et direkte uttrykk for tilstanden til den sentrale cellen etter trinn som starter fra en hvilken som helst konfigurasjon :
I en totalistisk mobilautomat avhenger den påfølgende tilstanden til en celle bare av summen av tilstandene til naboene; dette er tilfellet med livets spill der en levende celle forblir slik om to eller tre av naboene lever, og en død celle blir født hvis tre av naboene lever. En totalistisk automat tar derfor ikke hensyn til naboene til en celle i forhold til den.
Hvis en mobilautomat ikke er totalistisk, i tillegg til sin egen tilstand, påvirker posisjonen til en celle naboer dens påfølgende tilstand. For eksempel, for en endimensjonal mobilautomat, kan vi skille mellom nabocellen til venstre og naboen til høyre.
Denne klassifiseringen ble introdusert av Stephen Wolfram i 1983 i sin artikkel Universality and complexity in cellular automata og representerer det første forsøket på å klassifisere cellulære automata i henhold til deres utvikling fra tilfeldige innledende konfigurasjoner. Han foreslo fire klasser av atferd:
En av kritikkene av Wolframs klassifisering ligger i manglende evne til å si om en gitt mobilautomat er Turing-universal ; dessuten er det funnet universelle mobilautomater for hver av klassene foreslått av Wolfram. Denne tingenes tilstand stammer fra det Wolfram bare betraktet som tilfeldige innledende forhold, men ikke spesielle strukturer opprettet spesielt for anledningen. Spesielt blir ikke overføring av informasjon, for eksempel via fartøy , tatt i betraktning.
David Eppstein foreslo et alternativ til denne klassifiseringen:
A priori , bare de siste tilfellene tillater universalitet, selv om alle mobilautomatene som svarer på dem ikke er det. På den annen side er det heller ikke vist at det er umulig å bygge universelle strukturer for de andre tilfellene, andre strukturer enn fartøyene kan også overføre informasjon.
I den formelle definisjonen ovenfor er nettverket systematisk av form . Vi kan generalisere uten problemer til andre vanlige uendelige grafer .
Den første klassifiseringen av en mobilautomat gjelder måten reglene brukes på nettet:
Det er mulig å generalisere begrepet mobilautomat, for eksempel:
De kontinuerlige kontrollerne fungerer på samme prinsipp som mobilautomater, men bruker nett eller kontinuerlige tilstander (vanligvis mellom 0 og 1). Slike automater kan for eksempel simulere diffusjonen av en væske.
En sannsynlig mobilautomat er en deterministisk mobilautomat der den lokale regelen f erstattes av en tilfeldig lokal dynamikk, det vil si en overgangsmatrise som indikerer i henhold til tilstanden hvor vi er med hvilken sannsynlighet vi kan havne i en følgende tilstand.
Det er mulig å gjenta en mobilautomat på bildet som er funnet etter anvendelse av samme sannsynlige mobilautomat. Du kan gjenta om og om igjen. Jakten på uforanderlig lov der ergodisiteten (konvergensen) til startloven er fag som det forskes på for tiden.
Det antas (men ikke bevist) at sannsynlighetscelleautomater er ergodiske hvis startalfabetets kardinal er 2, og det er bevist at dette er falskt for alle veldig store alfabet. Dette ble demonstrert av Gàcs i 2001 for sannsynlig mobilautomat med et kardinalalfabet på omtrent størrelse .
Spørsmålet forblir åpent og antas ikke for sannsynlig mobilautomat med kardinalalfabet i mindre størrelse.
I matematisk forskning brukes også probabilistiske mobilautomater til å formodne visse lover om generaliserte siste-pass-perkolasjoner.
Vi kan betrakte modellen av mobilautomater som den diskrete motstykket til partielle differensiallikninger . Således, hver gang et fysisk fenomen blir beskrevet av partielle differensiallikninger, kan en (e) foreslås i form av en mobilautomat. Det gjenstår å avgjøre i hvilken grad mobilmodellen er relevant for å forklare og / eller forutsi det studerte fenomenet. Ingenting er garantert generelt, og å karakterisere den globale dynamikken i cellemodellen i henhold til den lokale definisjonen kan være minst like vanskelig som å løse systemet med delvise differensialligninger.
På den annen side kan mobilautomaten simuleres enkelt med datamaskiner! Således, numerisk analyse , er mange metoder å diskretisere bestemte mengder (rom, tid, verdi) for å utføre numeriske simuleringer (se metoden for endelig element , det endelige volumet eller den endelige forskjellen ).
Blant modellene som har blitt grundig studert, kan vi sitere nettverksgassautomater ( gittergaz automata ) som modellerer gasspartikler styrt av en diskret versjon av Navier Stokes-ligningene .
Den første formuleringen av denne modellen, kjent under navnet HPP , (den handler om en mobilautomat av dimensjon ) skyldes J. Hardy, Y. Pomeau og O. Pazzis på 1970-tallet. En annen formulering, FHP , ble foreslått på 1980-tallet av U. Frisch, B. Hasslacher og Y. Pomeau: det forbedrer den forrige ved å erstatte cellenettverket med et sekskantet nettverk.
Mobilautomater finner også anvendelse i modellering og simulering av skogbranner . Den første bruken skyldes Kourtz og O'Regan i 1971. Disse modellene gjør det enkelt å observere forplantningen av brannen i henhold til flere parametere som retning og kraft av vinden eller fuktigheten .
Mønstrene til visse skjell , som kjegler og cymbiolae , genereres av mekanismer som ligner modellen til mobilautomater. Cellene som er ansvarlige for pigmentering er plassert på en smal stripe langs munningen av skjell. Hver celle skiller ut pigmenter i henhold til sekresjonen (eller mangelen på sekresjon) fra naboene, og alle cellene produserer mønsteret av skallet når det vokser. For eksempel viser Conus-tekstilarten et mønster som ligner regel 30 beskrevet ovenfor.
K. Nagel og M. Schreckenberg foreslo på 1990-tallet en motorveitrafikkmodell basert på en 1-dimensjonal mobilautomat:
Denne modellen tilsvarer en mobilautomat hvis den tilfeldige forstyrrelsen er fraværende ( ). Hvis i tillegg (et kjøretøy enten er stille eller ved maksimal hastighet), blir modellen redusert til den elementære mobilautomaten 184: cellene kan bare ta to verdier som tilsvarer tomt eller tilstedeværelsen av et kjøretøy .
Flere forskere, som Andrew Ilachinski , har antatt at universet kan tenkes å være en mobilautomat. Ilachinski begrunner det med følgende observasjon: "La oss se på utviklingen til regel 110 : hvis det var en slags" alternativ fysikklov ", hva ville være den rasjonelle beskrivelsen av de observerte mønstrene? En observatør som ikke var klar over regelen som ble brukt for å generere bildene, kunne anta bevegelsen av diskrete objekter. " Fysikeren James Crutchfield utstedte en streng matematisk teori basert på dette prinsippet, og demonstrerte fremveksten av statistiske" partikler "i mobilautomater. I forlengelse kan universet , som kan beskrives som et sett med partikler, således betraktes som en mobilautomat.
I oktober 2014 gjenstår det å formulere en enhetlig teori basert på denne antagelsen; likevel har forskning i denne retningen hjulpet noen forskere med å definere universet som et diskret system: