Blokovat mobilní automat - Block cellular automaton

Sousedství Margolus pro dvourozměrný blokový buněčný automat. Oddíl buněk se střídá mezi sadou 2 × 2 bloky označené plnými modrými čarami a sada bloků označená přerušovanými červenými čarami.

A blokovat buněčný automat nebo dělení celulárního automatu je zvláštní druh buněčný automat ve kterém je mřížka buněk rozdělena na nepřekrývající se bloky (s různými oddíly v různých časových krocích) a pravidlo přechodu se použije spíše na celý blok než na jednu buňku. Blokové mobilní automaty jsou užitečné pro simulace fyzikálních veličin, protože je snadné zvolit pravidla přechodu, která se řídí fyzickými omezeními, jako je reverzibilita a zákony na ochranu přírody.[1]

Definice

Blokový buněčný automat se skládá z následujících komponent:[1][2]

  • Pravidelný mříž buněk
  • Konečná množina stavů, ve kterých může být každá buňka
  • Rozdělení buněk do uniformy mozaikování ve kterém má každá dlaždice oddílu stejnou velikost a tvar
  • Pravidlo pro posunutí oddílu po každém časovém kroku
  • Přechodové pravidlo, funkce, která bere jako vstup přiřazení stavů pro buňky v jedné dlaždici a vytváří jako výstup další přiřazení stavů pro stejné buňky.

V každém časovém kroku se pravidlo přechodu použije současně a synchronně na všechny dlaždice v oddílu. Potom se oddíl posune a stejná operace se opakuje v dalším časovém kroku atd. Tímto způsobem, stejně jako u jiných buněčných automatů, se vzor buněčných stavů v průběhu času mění, aby provedl nějaký netriviální výpočet nebo simulaci.

Sousedství

Nejjednodušší schéma rozdělení je pravděpodobně Sousedství Margolus, pojmenoval podle Norman Margolus, který nejprve studoval blokové buněčné automaty pomocí této struktury sousedství. V sousedství Margolus je mříž rozdělena na 2-bunkové bloky (nebo 2 × 2 čtverce ve dvou rozměrech, nebo 2 × 2 × 2 kostky ve třech rozměrech atd.), které jsou posunuty o jednu buňku (podél každé dimenze) v alternativních časových krocích.[1][2][3]

Úzce související technika způsobená K. Moritou a M. Harao[4] spočívá v rozdělení každé buňky na konečný počet částí, přičemž každá část je věnována nějakému sousedovi. Evoluce probíhá výměnou odpovídajících částí mezi sousedy a následným nanesením čistě lokální transformace na každou buňku v závislosti pouze na stavu buňky (a ne na stavech jejích sousedů). S takovým konstrukčním schématem je buněčný automat zaručeně reverzibilní, pokud dojde k místní transformaci je sám o sobě bijekce. Na tuto techniku ​​lze pohlížet jako na blokový buněčný automat na jemnější mřížce buněk, tvořené částmi každé větší buňky; bloky této jemnější mřížky se střídají mezi sadami částí v jedné velké buňce a sadami částí v sousedních buňkách, které spolu sdílejí části.

Reverzibilita a ochrana

Dokud platí pravidlo pro vývoj každého bloku reverzibilní, bude také celý automat. Silněji v tomto případě lze časově obrácené chování automatu také popsat jako blokový buněčný automat se stejnou blokovou strukturou a s přechodovým pravidlem, které invertuje původní pravidlo automatu v každém bloku. Platí také obrácení: pokud bloky nejsou individuálně reverzibilní, globální vývoj nemůže být reverzibilní: pokud existují dvě různé konfigurace X a y bloku vedou ke stejnému stavu výsledku z, pak globální konfigurace s X v jednom bloku by bylo nerozeznatelné po jednom kroku od konfigurace, ve které X je nahrazen y. To znamená, že buněčný automat je celosvětově reverzibilní tehdy a jen tehdy, pokud je reverzibilní na úrovni bloku.[5]

Snadnost navrhování reverzibilních blokových celulárních automatů a testování blokových celulárních automatů na reverzibilitu je v silném kontrastu s celulárními automaty s jinými neblokovými sousedními strukturami, pro které je nerozhodnutelný zda je automat reverzibilní a pro které může reverzní dynamika vyžadovat mnohem větší sousedství než dopředná dynamika.[6] Libovolný reverzibilní buněčný automat může být simulován reverzibilním blokovým celulárním automatem s větším počtem stavů; z důvodu nerozhodnutelnosti reverzibility u neblokových celulárních automatů však neexistuje žádná vypočítatelná vazba na poloměr oblastí v neblokovém automatu, které odpovídají blokům v simulaci, a překlad z neblokového pravidla na blokové pravidlo také nelze vypočítat.[7]

Blokové mobilní automaty jsou také praktickým formalismem, ve kterém lze navrhovat pravidla, která se kromě reverzibility implementují zákony na ochranu přírody jako je zachování počtu částic, zachování hybnosti atd. Například pokud pravidlo v každém bloku zachovává počet živých buněk v bloku, pak globální vývoj automatu také zachová stejný počet. Tato vlastnost je užitečná v aplikacích celulárních automatů pro fyzickou simulaci.[8]

Simulace konvenčními celulárními automaty

Jak píší Toffoli a Margolus,[2] model blokového celulárního automatu nezavádí žádnou další energii ve srovnání s konvenčním celulárním automatem, který používá stejnou strukturu sousedství v každém časovém kroku: jakýkoli blokový celulární automat může být simulován na konvenčním celulárním automatu pomocí více stavů a ​​většího sousedství. Konkrétně nechte dva automaty používat stejnou mřížku buněk, ale nechte každý stav konvenčního automatu určit stav blokového automatu, fázi vzoru posunutí jeho oddílu a polohu buňky v jeho bloku. Například v sousedství Margolus by to zvýšilo počet států o faktor osm: existují čtyři možné pozice, které může buňka zaujmout ve své 2 × 2 blok a dvě fáze do oddílu. Dále nechte sousedství konvenčního automatu sjednocení bloků obsahujících danou buňku v blokovém buněčném automatu. Pak s touto strukturou sousedství a stavu může být každá aktualizace blokového automatu simulována jedinou aktualizací konvenčního celulárního automatu.

Aplikace

K implementaci se běžně používají blokové mobilní automaty mřížkové plyny a další kvazi-fyzikální simulace, kvůli snadnosti simulace fyzických omezení, jako jsou zákony zachování v těchto systémech.[1][8]Například model Margolus lze použít k simulaci modelu mřížkového plynu HPP, ve kterém se částice pohybují ve dvou kolmých směrech a při srážce se navzájem rozptylují v pravých úhlech. V blokové buněčné simulaci tohoto modelu pravidlo aktualizace přesune každou buňku do buňky diagonálně naproti ve svém bloku, s výjimkou případu, kdy buňka obsahuje dvě diagonálně protilehlé částice, v takovém případě jsou nahrazeny doplňkovou dvojicí diagonálně protilehlých částice. Tímto způsobem se částice pohybují úhlopříčně a rozptylují se podle modelu HPP.[2][9] Alternativní pravidlo, které simuluje model mřížkového plynu HPP s horizontálním a vertikálním pohybem částic, spíše než s diagonálním pohybem, zahrnuje otáčení obsahu každého bloku ve směru hodinových ručiček nebo proti směru hodinových ručiček ve střídavých fázích, s výjimkou opět v případě, že buňka obsahuje dva úhlopříčně opačné částice, v takovém případě zůstane nezměněn.[2]V jednom z těchto modelů hybnost (součet vektory rychlosti pohyblivých částic) je zachována, stejně jako jejich počet, základní vlastnost pro simulaci fyzikálních plynů. Avšak modely HPP jsou poněkud nereálné jako model dynamiky plynů, protože mají další pravidla nefyzické ochrany: celková hybnost v každé linii pohybu i celková hybnost celého systému jsou zachovány. Složitější modely založené na šestihranné mřížce se tomuto problému vyhýbají.[9]

Tyto automaty lze také použít k modelování pohybu zrn z písek v hromadách písku a přesýpací hodiny. V této aplikaci lze použít sousedství Margolus s aktualizačním pravidlem, které zachovává počet zrn v každém z nich 2 × 2 blok, ale to posune každé zrno co nejvíce dolů v jeho bloku. Pokud blok obsahuje dvě zrna, která jsou naskládána svisle na sebe, přechodová funkce automatu jej nahradí blokem, ve kterém jsou zrna vedle sebe, což ve skutečnosti umožňuje převrhnutí a roztažení vysokých hromád písku. Tento model není reverzibilní, ale stále se řídí zákonem zachování počtu částic.[10] Upravené pravidlo, využívající stejné sousedství, ale pohybující částice do stran v maximální možné míře i dolů, umožňuje simulované pískoviště šířit, i když nejsou příliš strmé.[11] Jsou také možné sofistikovanější modely pískových pilot s celulárním automatem, které zahrnují jevy, jako je větrný transport a tření.[10]

Původní aplikací Margoluse pro model blokového buněčného automatu byla simulace model kulečníkové koule reverzibilního výpočtu, ve kterém Logická logika signály jsou simulovány pohybujícími se částicemi a logické brány jsou simulovány pomocí elastické srážky těchto částic. Je například možné provádět výpočty kulečníkových koulí v dvourozměrném Margolusově modelu se dvěma stavy na buňku a s počtem živých buněk konzervovaných vývojem modelu. V pravidle „BBM“, které tímto způsobem simuluje model kulečníkové koule, se signály skládají z jednotlivých živých buněk, které se pohybují úhlopříčně. Chcete-li dosáhnout tohoto pohybu, funkce přechodu bloku nahradí blok obsahující jednu živou buňku jiným blokem, ve kterém byla buňka přesunuta do opačného rohu bloku. Podobně lze provést elastické srážky funkcí přechodu bloku, která nahradí dvě úhlopříčně protilehlé živé buňky dalšími dvěma buňkami bloku. Ve všech ostatních konfiguracích bloku funkce přechodu bloku nezmění jeho stav. V tomto modelu 2 × 4 obdélníky živých buněk (pečlivě zarovnané s ohledem na přepážku) zůstávají stabilní a mohou být použity jako zrcadla k vedení cest pohybujících se částic. Například ilustrace sousedství Margolus ukazuje čtyři částice a zrcadlo; pokud další krok používá modrou přepážku, pak se dvě částice pohybují směrem k zrcadlu, zatímco další dvě se chystají srazit, zatímco pokud další krok používá červenou přepážku, pak se dvě částice vzdalují od zrcadla a další dvě mají právě se srazil a bude se pohybovat od sebe.[3][5][12]

Další pravidla

Kluzáky unikají z centrálního náhodného semene, za troskami dřívějších havárií kluzáků, podle pravidla Critters.

Toffoli a Margolus[2] navrhnout další dvě reverzibilní pravidla pro sousedství Margolus s dvoustavovými buňkami, která, i když nejsou motivována fyzickými úvahami, vedou k zajímavé dynamice.

Critters

Hlavní článek: Critters (celulární automat)

V pravidle „Critters“ funkce přechodu obrátí stav každé buňky v bloku, s výjimkou bloku s přesně dvěma živými buňkami, který zůstane nezměněn. Bloky se třemi živými buňkami navíc procházejí rotací o 180 stupňů a obrácením stavu.[2] Toto je reverzibilní pravidlo a řídí se zákony zachování týkající se počtu částic (počítání částice jako živé buňky v sudých fázích a jako mrtvé buňky v lichých fázích) a parity počtu částic podél diagonálních čar.[12] Protože je reverzibilní, počáteční stavy, ve kterých všechny buňky přijímají náhodně vybrané stavy, zůstávají po celou dobu svého vývoje nestrukturované. Když však začalo s menším polem náhodných buněk se středem ve větší oblasti mrtvých buněk, vede toto pravidlo ke komplexní dynamice podobné těm v Conwayova hra o život ve kterém mnoho malých vzorů podobných životu kluzák uniknout z centrální náhodné oblasti a komunikovat mezi sebou navzájem.[2][12] Na rozdíl od kluzáků v životě reverzibilita a zachování částic dohromady znamenají, že když kluzáky havarují společně v Critterech, musí alespoň jeden uniknout a tyto srážky často umožňují oběma příchozím kluzákům rekonstituovat se na různých odchozích tratích. Pomocí takových kolizí může toto pravidlo také simulovat výpočetní model kulečníkové koule, i když složitějším způsobem než pravidlo BBM.[12] Pravidlo Critters může také podporovat složitější kosmické lodě různých rychlostí a také oscilátory s nekonečně mnoha různými obdobími.[13]

Tron

Přímočaré tvary generované pravidlem Tron.

V pravidle „Tron“ přechodová funkce ponechává každý blok beze změny, kromě případů, kdy všechny čtyři jeho buňky mají stejný stav, v takovém případě jsou všechny jejich stavy obrácené. Spuštění tohoto pravidla z počátečních podmínek ve formě obdélníku živých buněk nebo z podobných jednoduchých tvarů s přímými hranami vede ke složitým přímočarým vzorům. Toffoli a Margolus také naznačují, že toto pravidlo lze použít k implementaci pravidla místní synchronizace, které umožňuje simulaci jakéhokoli mobilního automatu bloku sousedství Margolus pomocí asynchronní buněčný automat. V této simulaci ukládá každá buňka asynchronního automatu jak stav simulovaného automatu, tak druhý bit představující parita časového razítka pro tuto buňku; výsledný asynchronní automat má tedy dvakrát tolik stavů než automat, který simuluje. Časová razítka jsou omezena tak, aby se mezi sousedními buňkami lišila nejvýše o jednu, a jakýkoli blok čtyř buněk, jejichž časová razítka mají všechny správnou paritu, může být aktualizován podle simulovaného pravidla bloku. Když je provedena aktualizace tohoto typu, parity časových značek by měly být také aktualizovány podle pravidla Tron, které nutně zachovává omezení na sousedních časových razítkách. Prováděním místních aktualizací tímto způsobem je vývoj každé buňky v asynchronním automatu totožný s vývojem v simulovaném automatu synchronního bloku.[2][14]

První tři kroky sekvence párátka a jeho emulace blokovým celulárním automatem s Margolusovým sousedstvím

Viz také

  • Sekvence párátka, fraktální vzor, ​​který lze emulovat celulárními automaty se sousedstvím Margolus

Reference

  1. ^ A b C d Schiff, Joel L. (2008), „4.2.1 Partitioning Cellular Automata“, Mobilní automaty: diskrétní pohled na svět, Wiley, str. 115–116
  2. ^ A b C d E F G h i Toffoli, Tommaso; Margolus, Norman (1987), „II.12 Sousedství Margolus“, Stroje celulárních automatů: Nové prostředí pro modelování, MIT Press, str. 119–138
  3. ^ A b Margolus, N. (1984), „Fyzikální modely výpočtu“, Physica D, 10: 81–95, Bibcode:1984PhyD ... 10 ... 81M, doi:10.1016/0167-2789(84)90252-5. Přetištěno Wolfram, Stephen, vyd. (1986), Teorie a aplikace celulárních automatůPokročilé řady pro složité systémy, 1, World Scientific, s. 232–246
  4. ^ Morita, K .; Harao, M. (1989), "Výpočetní univerzálnost 1 rozměrných reverzibilních (injektivních) celulárních automatů", Transaction Institute of Electronics, Information and Communication Engineers, E., 72: 758–762
  5. ^ A b Durand-Lose, Jérôme (2002), „Computing inside the billiard ball model“, in Adamatzky, Andrew (vyd.), Kolizní výpočetní technika, Springer-Verlag, str. 135–160
  6. ^ Kari, Jarkko (1990), „Reverzibilita 2D celulárních automatů je nerozhodnutelná“, Physica D, 45: 379–385, Bibcode:1990PhyD ... 45..379K, doi:10.1016 / 0167-2789 (90) 90195-U
  7. ^ Kari, Jarkko (1999), „O hloubce obvodu strukturně reverzibilních celulárních automatů“, Fundamenta Informaticae, 38: 93–107; Durand-Lose, Jérôme (2001), „Reprezentativní reverzibilní celulární automaty s reverzibilními blokovými celulárními automaty“, Diskrétní matematika a teoretická informatika, AA: 145–154, archivovány od originál dne 15. 5. 2011
  8. ^ A b Wolfram, Stephen (2002), Nový druh vědy Wolfram Media, str.459–464, ISBN  1-57955-008-8
  9. ^ A b "5.5.4 Mřížkové plyny", v Schiff (2008), str. 165–169.
  10. ^ A b Chopard, Bastien; Droz, Michael (1998), „2.2.6 Pravidlo hromady písku“, Modelování celulárních automatů fyzických systémů, Cambridge University Press, s. 42–46
  11. ^ Gruau, Frédéric; Tromp, John (2000), "Buněčná gravitace" (PDF), Paralelní zpracování dopisů, 10 (4): 383–393, doi:10,1142 / s0129626400000354, archivovány z originál (PDF) dne 18.7.2011
  12. ^ A b C d Margolus, Norman (1999), „Crystalline Computation“, Hey, Anthony J. G. (ed.), Feynman a výpočet, Perseus Books, s. 267–305, arXiv:comp-gas / 9811002, Bibcode:1998comp.gas.11002M
  13. ^ Marotta, Sebastian M. (2005), „Život ve světě tvorů“, Revista Ciências Exatas e Naturais, 7 (1), archivovány od originál dne 19. 3. 2012
  14. ^ Ojala, Leo; Penttinen, Olli-Matti; Parviainen, Elina (2004), „Modelování a analýza kvantových celulárních automatů Margolus pomocí net-teoretických metod“, Aplikace a teorie Petriho sítí 2004, Přednášky v informatice, 3099, Springer-Verlag, str. 331–350, doi:10.1007/978-3-540-27793-4_19

externí odkazy