Regel 184

Regel 184, kör i 128 steg från slumpmässiga konfigurationer med var och en av tre olika startdensiteter: översta 25 %, mellersta 50 %, botten 75 %. Vyn som visas är en beskärning på 300 pixlar från en bredare simulering.

Regel 184 är en endimensionell binär cellulär automatregel , känd för att lösa majoritetsproblemet såväl som för dess förmåga att samtidigt beskriva flera, till synes ganska olika, partikelsystem :

• Regel 184 kan användas som en enkel modell för trafikflöde i ett enda körfält på en motorväg och utgör grunden för många mobila automatmodeller av trafikflöde med större sofistikering. I denna modell rör sig partiklar (som representerar fordon) i en enda riktning, och stannar och startar beroende på bilarna framför dem. Antalet partiklar förblir oförändrat under hela simuleringen. På grund av denna tillämpning kallas regel 184 ibland för "trafikregeln".
• Regel 184 modellerar också en form av avsättning av partiklar på en oregelbunden yta, där varje lokalt minimum av ytan fylls med en partikel i varje steg. Vid varje steg i simuleringen ökar antalet partiklar. En gång placerad rör sig en partikel aldrig.
• Regel 184 kan förstås i termer av ballistisk förintelse, ett system av partiklar som rör sig både åt vänster och höger genom ett endimensionellt medium. När två sådana partiklar kolliderar förintar de varandra, så att antalet partiklar förblir oförändrat eller minskar vid varje steg.

Den uppenbara motsättningen mellan dessa beskrivningar löses genom olika sätt att associera egenskaper hos automatens tillstånd med partiklar.

Namnet på regel 184 är en Wolfram-kod som definierar utvecklingen av dess tillstånd. Den tidigaste forskningen om Regel 184 är av Li (1987) och Krug & Spohn (1988) . Speciellt beskriver Krug och Spohn redan alla tre typerna av partikelsystem modellerade av Regel 184.

Definition

Ett tillstånd för regel 184-automaten består av en endimensionell grupp av celler, som var och en innehåller ett binärt värde (0 eller 1). I varje steg av dess utveckling tillämpar regel 184-automaten följande regel på var och en av cellerna i arrayen, samtidigt för alla celler, för att bestämma det nya tillståndet för cellen:

nuvarande mönster	111	110	101	100	011	010	001	000
nytt tillstånd för mittcellen	1	0	1	1	1	0	0	0

En post i denna tabell definierar det nya tillståndet för varje cell som en funktion av det tidigare tillståndet och de tidigare värdena för de angränsande cellerna på vardera sidan. Namnet på denna regel, Regel 184, är Wolfram-koden som beskriver tillståndstabellen ovan: den nedre raden i tabellen, 10111000, när det ses som ett binärt tal , är lika med decimaltalet 184 .

Regeluppsättningen för regel 184 kan också beskrivas intuitivt, på flera olika sätt:

• Vid varje steg, närhelst det i det aktuella tillståndet finns en 1 omedelbart följt av en 0, byter dessa två symboler plats. Baserat på denna beskrivning Krug & Spohn (1988) Regel 184 för en deterministisk version av en "kinetisk Ising-modell med asymmetrisk spin-utbytesdynamik".
• Om en cell med värdet 1 har en cell med värdet 0 omedelbart till höger vid varje steg, flyttas 1:an åt höger och lämnar en 0:an bakom sig. En 1 med en annan 1 till höger förblir på plats, medan en 0 som inte har en 1 till vänster förblir en 0. Den här beskrivningen är mest lämpad för applikationen för trafikflödesmodellering.
• Om en cell har tillstånd 0, tas dess nya tillstånd från cellen till vänster. Annars tas dess nya tillstånd från cellen till höger. Det vill säga, varje cell kan implementeras av en tvåvägsdemultiplexerare med de två intilliggande cellerna som indata, och cellen själv fungerar som väljarlinjen. Varje cells nästa tillstånd bestäms av demultiplexerns utsignal. Denna operation är nära besläktad med en Fredkin-port .

Dynamik och majoritetsklassificering

Från beskrivningarna av reglerna ovan kan två viktiga egenskaper hos dess dynamik omedelbart ses. Först, i regel 184, för varje ändlig uppsättning celler med periodiska randvillkor , förblir antalet 1:or och antalet 0:or i ett mönster oföränderligt under mönstrets utveckling. Regel 184 och dess reflektion är de enda icke-triviala elementära cellulära automaterna som har denna egenskap av nummerbevarande. På liknande sätt, om densiteten av 1s är väldefinierad för en oändlig array av celler, förblir den oföränderlig när automaten utför sina steg. Och för det andra, även om Regel 184 inte är symmetrisk under vänster-höger-omkastning, har den en annan symmetri: vända vänster och höger och samtidigt byta rollerna för 0- och 1-symbolerna producerar en cellulär automat med samma uppdateringsregel.

Mönster i regel 184 stabiliseras vanligtvis snabbt, antingen till ett mönster där celltillstånden rör sig i låssteg en position åt vänster vid varje steg, eller till ett mönster som flyttar en position åt höger vid varje steg. Specifikt, om den initiala tätheten av celler med tillstånd 1 är mindre än 50 %, stabiliseras mönstret till kluster av celler i tillstånd 1, åtskilda två enheter från varandra, med klustren åtskilda av block av celler i tillstånd 0. Mönster av denna typ rör sig åt höger. Om, å andra sidan, den initiala tätheten är större än 50 %, stabiliseras mönstret till kluster av celler i tillstånd 0, åtskilda två enheter från varandra, med klustren åtskilda av block av celler i tillstånd 1, och mönster av denna typ rör sig åt vänster. Om densiteten är exakt 50 %, stabiliseras det initiala mönstret (långsammare) till ett mönster som på motsvarande sätt kan ses röra sig antingen åt vänster eller höger vid varje steg: en alternerande sekvens av 0:or och 1:or.

Majoritetsproblemet är problemet med att konstruera en cellulär automat som, när den körs på vilken ändlig uppsättning celler som helst, kan beräkna värdet som innehas av en majoritet av dess celler . På sätt och vis löser regel 184 detta problem enligt följande. om regel 184 körs på en ändlig uppsättning celler med periodiska randvillkor, med ett ojämnt antal 0:or och 1:or, kommer varje cell så småningom att se två på varandra följande tillstånd av majoritetsvärdet oändligt ofta, men kommer att se två på varandra följande tillstånd av minoriteten värde endast ändligt många gånger. Majoritetsproblemet kan inte lösas perfekt om det krävs att alla celler så småningom stabiliserar sig till majoritetsstaten, men lösningen enligt Regel 184 undviker detta omöjlighetsresultat genom att mildra kriteriet enligt vilket automaten erkänner en majoritet.

Trafikflöde

Regel 184 tolkad som en simulering av trafikflödet. Varje 1 cell motsvarar ett fordon, och varje fordon rör sig bara framåt om det har öppet utrymme framför sig.

Om man tolkar varje 1-cell i Regel 184 som att de innehåller en partikel, beter sig dessa partiklar på många sätt som bilar i ett enda körfält: de rör sig framåt med konstant hastighet om det finns öppet utrymme framför dem, och annars de slutar. Trafikmodeller som regel 184 och dess generaliseringar som diskretiserar både rum och tid kallas vanligtvis partikelhoppningsmodeller . Även om den är väldigt primitiv förutsäger Rule 184-modellen av trafikflöde redan några av de välbekanta framväxande särdragen hos verklig trafik: kluster av fritt rörliga bilar åtskilda av sträckor av öppen väg när trafiken är lätt, och vågor av stopp-och-kör-trafik när den är mycket primitiv . är tung.

Det är svårt att peka ut den första användningen av regel 184 för simulering av trafikflöden, delvis eftersom fokus för forskningen inom detta område har varit mindre på att uppnå den högsta nivån av matematisk abstraktion och mer på sannolikhet: till och med de tidigare artiklarna om cellulära automater baserade Trafikflödessimulering gör vanligtvis modellen mer komplex för att mer exakt simulera verklig trafik. Icke desto mindre är regel 184 grundläggande för trafiksimulering med cellulära automater. Wang, Kwong & Hui (1998) säger till exempel att "den grundläggande cellulära automatmodellen som beskriver ett endimensionellt trafikflödesproblem är regel 184." Nagel (1996) skriver "Mycket arbete med att använda CA-modeller för trafik bygger på denna modell." Flera författare beskriver endimensionella modeller med fordon som rör sig i flera hastigheter; sådana modeller degenererar till regel 184 i fallet med en hastighet. Gaylord & Nishidate (1996) utökar regel 184-dynamiken till tvåfilig motorvägstrafik med filbyten; deras modell delar med regel 184 egenskapen att den är symmetrisk under samtidig vänster-höger och 0-1 omkastning. Biham, Middleton & Levine (1992) beskriver en tvådimensionell stadsrutnätsmodell där dynamiken för enskilda körfält i huvudsak överensstämmer med regel 184. Se Maerivoet för en djupgående undersökning av mobila automaters trafikmodellering och tillhörande statistisk mekanik. & De Moor (2005) och Chowdhury, Santen & Schadschneider (2000) .

När man ser Regel 184 som en trafikmodell är det naturligt att ta hänsyn till fordonens medelhastighet. När trafiktätheten är mindre än 50 % är denna medelhastighet helt enkelt en enhet av avstånd per tidsenhet: efter att systemet har stabiliserats saktar ingen bil någonsin ner. Men när densiteten är ett tal ρ större än 1/2 är trafikens medelhastighet ${\tfrac {1-\rho }{\rho }}$ . Således uppvisar systemet en andra ordningens kinetisk fasövergång vid ρ = 1/2 . När Regel 184 tolkas som en trafikmodell och utgår från en slumpmässig konfiguration vars densitet är vid detta kritiska värde ρ = 1/2 , då närmar sig medelhastigheten sin stationära gräns som kvadratroten av antalet steg. I stället, för slumpmässiga konfigurationer vars densitet inte är vid det kritiska värdet, är tillvägagångssättet till den begränsande hastigheten exponentiell.

Ytdeponering

Regel 184 som en modell av ytavsättning. I ett lager av partiklar som bildar ett diagonalt orienterat kvadratiskt gitter fastnar nya partiklar i varje tidssteg till ytans lokala minima. De cellulära automattillstånden modellerar ytans lokala lutning.

Såsom visas i figuren och som ursprungligen beskrivits av Krug & Spohn (1988), kan Regel 184 användas för att modellera avsättning av partiklar på en yta. I denna modell har man en uppsättning partiklar som upptar en delmängd av positionerna i ett kvadratiskt gitter orienterat diagonalt (de mörkare partiklarna i figuren). Om en partikel finns i någon position av gittret måste gitterpositionerna under och till höger, och under och till vänster om partikeln också fyllas, så den fyllda delen av gittret sträcker sig oändligt nedåt till vänster och höger . Gränsen mellan fyllda och ofyllda positioner (den tunna svarta linjen i figuren) tolkas som att modellera en yta, på vilken fler partiklar kan avsättas. Vid varje tidssteg växer ytan genom avsättning av nya partiklar i varje lokalt minimum av ytan; det vill säga vid varje position där det är möjligt att lägga till en ny partikel som har befintliga partiklar under sig på båda sidor (de lättare partiklarna i figuren).

För att modellera denna process enligt Regel 184, observera att gränsen mellan fyllda och ofyllda gitterpositioner kan markeras med en polygonal linje, vars segment separerar angränsande gitterpositioner och har lutningar +1 och -1. Modellera ett segment med lutning +1 av en automatcell med tillstånd 0, och ett segment med lutning −1 av en automatcell med tillstånd 1. Ytans lokala minima är de punkter där ett segment av lutningen −1 ligger till vänster av ett segment med lutning +1; det vill säga i automaten, en position där en cell med tillstånd 1 ligger till vänster om en cell med tillstånd 0. Att lägga till en partikel till den positionen motsvarar att ändra tillstånden för dessa två intilliggande celler från 1,0 till 0,1 , så att den polygonala linjen går framåt. Detta är exakt beteendet i regel 184.

Relaterat arbete med denna modell avser deponering där ankomsttiderna för ytterligare partiklar är slumpmässiga, snarare än att partiklar anländer till alla lokala minima samtidigt. Dessa stokastiska tillväxtprocesser kan modelleras som en asynkron cellulär automat .

Ballistisk förintelse

Regel 184 som en modell för ballistisk förintelse. Partiklar och antipartiklar (modellerade av på varandra följande celler med samma tillstånd) rör sig i motsatta riktningar och förintar varandra när de kolliderar.

Ballistisk förintelse beskriver en process genom vilken rörliga partiklar och antipartiklar förintar varandra när de kolliderar. I den enklaste versionen av denna process består systemet av en enda typ av partikel och antipartikel, som rör sig med lika hastigheter i motsatta riktningar i ett endimensionellt medium.

Denna process kan modelleras av Regel 184, enligt följande. Partiklarna modelleras som punkter som är i linje, inte med automatens celler, utan snarare med mellanrummen mellan cellerna. Två på varandra följande celler som båda har tillstånd 0 modellerar en partikel i utrymmet mellan dessa två celler som rör sig åt höger en cell vid varje tidssteg. Symmetriskt modellerar två på varandra följande celler som båda har tillstånd 1 en antipartikel som rör sig åt vänster en cell vid varje tidssteg. De återstående möjligheterna för två på varandra följande celler är att de båda har olika tillstånd; detta tolkas som att man modellerar ett bakgrundsmaterial utan några partiklar i det, genom vilket partiklarna rör sig. Med denna tolkning interagerar partiklarna och antipartiklarna genom ballistisk förintelse: när en åt höger rörlig partikel och en åt vänster rörlig antipartikel möts, är resultatet ett område av bakgrunden från vilket båda partiklarna har försvunnit, utan någon effekt på några andra närliggande partiklar.

Beteendet hos vissa andra system, såsom endimensionella cykliska cellulära automater , kan också beskrivas i termer av ballistisk förintelse. Det finns en teknisk begränsning av partikelpositionerna för den ballistiska förintelsesynen av Regel 184 som inte uppstår i dessa andra system, som härrör från bakgrundens alternerande mönster: i partikelsystemet som motsvarar ett Regel 184-tillstånd, om två på varandra följande partiklar är båda av samma typ måste de vara ett udda antal celler ifrån varandra, medan om de är av motsatta typer måste de vara ett jämnt antal celler ifrån varandra. Denna paritetsbegränsning spelar dock ingen roll i detta systems statistiska beteende.

Pivato (2007) använder en liknande men mer komplicerad partikelsystemsyn av regel 184: han ser inte bara alternerande 0–1-regioner som bakgrund, utan anser också att regioner som enbart består av ett enda tillstånd också är bakgrund. Baserat på detta synsätt beskriver han sju olika partiklar som bildas av gränser mellan regioner och klassificerar deras möjliga interaktioner. Se Chopard & Droz (1998 , s. 188–190) för en mer allmän översikt av de cellulära automatmodellerna för förintelseprocesser.

Kontextfri analys

I sin bok A New Kind of Science påpekar Stephen Wolfram att regel 184, när den körs på mönster med densitet 50 % , kan tolkas som att tolka det fria språket i sammanhanget som beskriver strängar bildade från kapslade parenteser . Denna tolkning är nära besläktad med den ballistiska förintelsesynen av regel 184: i Wolframs tolkning motsvarar en öppen parentes en partikel som rör sig till vänster medan en nära parentes motsvarar en partikel som rör sig till höger.

Se även

• Regel 30 , Regel 90 och Regel 110 , andra endimensionella cellulära automater med annat beteende

Anteckningar

•   Alonso-Sanz, Ramon (2011). "Nummerbevarande regler" . Diskreta system med minne . World Scientific-serien om icke-linjär vetenskap, Ser. A. Vol. 75. World Scientific. s. 55–57. ISBN 9789814343633 .
•    Belitsky, Vladimir; Ferrari, Pablo A. (1995). "Ballistisk förintelse och deterministisk yttillväxt". Journal of Statistical Physics . 80 (3–4): 517–543. Bibcode : 1995JSP....80..517B . CiteSeerX 10.1.1.4.7901 . doi : 10.1007/BF02178546 . S2CID 16293185 .
•    Biham, Ofer ; Middleton, A. Alan; Levine, Dov (1992). "Självorganisering och en dynamisk övergång i trafikflödesmodeller". Fysisk granskning A . 46 (10): R6124–R6127. arXiv : cond-mat/9206001 . Bibcode : 1992PhRvA..46.6124B . doi : 10.1103/PhysRevA.46.R6124 . PMID 9907993 . S2CID 14543020 .
•   Boccara, Nino; Fukś, Henryk (1998). "Regler för mobilautomater som bevarar antalet aktiva webbplatser". Journal of Physics A: Mathematical and General . 31 (28): 6007–6018. arXiv : adap-org/9712003 . Bibcode : 1998JPhA...31.6007B . doi : 10.1088/0305-4470/31/28/014 . S2CID 14807539 .
•   Capcarrere, Mathieu S.; Sipper, Moshe; Tomassini, Marco (1996). "Tvåtillstånd, r = 1 cellulär automat som klassificerar densitet" (PDF) . Fysiska granskningsbrev . 77 (24): 4969–4971. Bibcode : 1996PhRvL..77.4969C . doi : 10.1103/PhysRevLett.77.4969 . PMID 10062680 .
•   Chopard, Bastien; Droz, Michel (1998). Cellulär automatmodellering av fysiska system . Cambridge University Press . ISBN 978-0-521-67345-7 .
•   Chowdhury, Debashish; Santen, Ludger; Schadschneider, Andreas (2000). "Statistisk fysik för fordonstrafik och vissa relaterade system". Fysiska rapporter . 329 (4): 199–329. arXiv : cond-mat/0007053 . Bibcode : 2000PhR...329..199C . doi : 10.1016/S0370-1573(99)00117-9 . S2CID 119526662 .
•   Fukś, Henryk (1997). "Lösning av densitetsklassificeringsproblemet med två liknande regler för cellulära automater". Fysisk granskning E . 55 (3): R2081–R2084. arXiv : comp-gas/9703001 . Bibcode : 1997PhRvE..55.2081F . doi : 10.1103/PhysRevE.55.R2081 . S2CID 118954791 .
•   Fukś, Henryk; Boccara, Nino (1998). "Generaliserade deterministiska trafikregler" (PDF) . International Journal of Modern Physics C . 9 (1): 1–12. arXiv : adap-org/9705003 . Bibcode : 1998IJMPC...9....1F . doi : 10.1142/S0129183198000029 . S2CID 119938282 . Arkiverad från originalet (PDF) den 27 september 2007.
• Fukui, M.; Ishibashi, Y. (1996). "Trafikflöde i 1D cellulär automatmodell inklusive bilar som rör sig med hög hastighet". Journal of the Physical Society of Japan . 65 (6): 1868–1870. Bibcode : 1996JPSJ...65.1868F . doi : 10.1143/JPSJ.65.1868 .
•   Gaylord, Richard J.; Nishidate, Kazume (1996). "Trafikflöde". Modeling Nature: Cellular Automata Simulations with Mathematica . Springer-Verlag . s. 29–34 . ISBN 978-0-387-94620-7 .
•   Krug, J.; Spohn, H. (1988). "Universalitetsklasser för deterministisk yttillväxt". Fysisk granskning A . 38 (8): 4271–4283. Bibcode : 1988PhRvA..38.4271K . doi : 10.1103/PhysRevA.38.4271 . PMID 9900880 .
•   Landmärke; Belew, Richard (1995). "Det finns inga perfekta tvåtillståndscellulära automater för densitetsklassificering". Fysiska granskningsbrev . 74 (25): 1548–1550. Bibcode : 1995PhRvL..74.5148L . doi : 10.1103/PhysRevLett.74.5148 . PMID 10058695 .
• Li, Wentian (1987). "Kraftspektra för vanliga språk och cellulära automater" (PDF) . Komplexa system . 1 : 107–130. Arkiverad från originalet (PDF) 2007-10-07.
•    Li, Wentian (1992). "Fenomenologi av icke-lokala cellulära automater". Journal of Statistical Physics . 68 (5–6): 829–882. Bibcode : 1992JSP....68..829L . CiteSeerX 10.1.1.590.1708 . doi : 10.1007/BF01048877 . S2CID 17337112 .
•   Maerivoet, Sven; De Moor, Bart (2005). "Modeller av mobilautomater för vägtrafik". Fysiska rapporter . 419 (1): 1–64. arXiv : fysik/0509082 . Bibcode : 2005PhR...419....1M . doi : 10.1016/j.physrep.2005.08.005 . S2CID 41394950 .
•   Moreira, Andres (2003). "Universalitet och bestämbarhet av nummerbevarande cellulära automater". Teoretisk datavetenskap . 292 (3): 711–721. arXiv : nlin.CG/0306032 . Bibcode : 2003nlin......6032M . doi : 10.1016/S0304-3975(02)00065-8 . S2CID 14909462 .
•    Nagel, Kai (1996). "Partikelhoppningsmodeller och trafikflödesteori". Fysisk granskning E . 53 (5): 4655–4672. arXiv : cond-mat/9509075 . Bibcode : 1996PhRvE..53.4655N . doi : 10.1103/PhysRevE.53.4655 . PMID 9964794 . S2CID 20466753 .
•   Nagel, Kai; Schreckenberg, Michael (1992). "En mobilautomatmodell för motorvägstrafik" . Journal de Physique I. 2 (12): 2221–2229. Bibcode : 1992JPhy1...2.2221N . doi : 10.1051/jp1:1992277 . S2CID 37135830 .
•   Pivato, M. (2007). "Defekt partikelkinematik i endimensionell cellulär automat". Teoretisk datavetenskap . 377 (1–3): 205–228. arXiv : math.DS/0506417 . doi : 10.1016/j.tcs.2007.03.014 . S2CID 12650387 .
•   Redner, Sidney (2001). "8.5 Ballistisk förintelse" . En guide till processer i första passagen . Cambridge University Press . sid. 288. ISBN 9780521652483 .
• Sukumar, N. (1998). "Effekt av randvillkor på cellulära automater som klassificerar densitet". arXiv : comp-gas/9804001 .
•    Tadaki, Shin-ichi; Kikuchi, Macato (1994). "Jam-faser i en tvådimensionell cellulär automatmodell av trafikflöde". Fysisk granskning E . 50 (6): 4564–4570. arXiv : patt-sol/9409004 . Bibcode : 1994PhRvE..50.4564T . doi : 10.1103/PhysRevE.50.4564 . PMID 9962535 . S2CID 17516156 .
• Wang, Bing-Hong; Kwong, Yvonne-Roamy; Hui, Pak-Ming (1998). "Statistisk mekanisk inställning till Fukui-Ishibashi trafikflödesmodeller". Fysisk granskning E . 57 (3): 2568–2573. Bibcode : 1998PhRvE..57.2568W . doi : 10.1103/PhysRevE.57.2568 .
• Wolfram, Stephen (2002). En ny typ av vetenskap . Wolfram Media .

externa länkar

• Regel 184 i Wolframs atlas över cellulära automater