Rajská zahrada (buněčný automat) - Garden of Eden (cellular automaton)

Zahrada Eden v Conwayova hra o život, objevený R. Banksem v roce 1971.[1] Buňky mimo obrázek jsou všechny mrtvé (bílé).
Sirotek v životě, který našel Achim Flammenkamp. Černé čtverečky jsou povinné živé buňky; modré x jsou vyžadovány mrtvé buňky.

V buněčný automat, a Rajská zahrada je konfigurace, která nemá žádného předchůdce. Může to být počáteční konfigurace automatu, ale nemůže vzniknout jiným způsobem.John Tukey pojmenoval tyto konfigurace po Rajská zahrada v Abrahamská náboženství, který byl vytvořen z ničeho.[2]

Zahrada Eden je určena stavem každé buňky v automatu (obvykle jednorozměrný nebo dvourozměrný nekonečný čtvercová mříž buněk). Pro každou rajskou zahradu však existuje konečný vzor (podmnožina buněk a jejich stavů, zvaná an sirotek) se stejnou vlastností, že nemá žádného předchůdce, bez ohledu na to, jak jsou vyplněny zbývající buňky. Konfigurace celého automatu je rajská zahrada, pouze pokud obsahuje sirotek. Pro jednorozměrné celulární automaty, sirotky a zahrady Eden lze najít pomocí efektivního algoritmu, ale pro vyšší rozměry tohle je nerozhodnutelný problém. Přesto se počítačovým vyhledáváním podařilo tyto vzorce najít Conwayova hra o život.

Věta o rajské zahradě Moore a Myhill tvrdí, že buněčný automat na čtvercové mřížce nebo na dlaždici jakékoli vyšší dimenze Euklidovský prostor, má rajskou zahradu právě tehdy, pokud má dvojčata, dva konečné vzory, které mají stejné nástupce, kdykoli je jeden nahrazen druhým.

Definice

A buněčný automat je definována mřížkou buněk, konečnou sadou stavů, které lze přiřadit každé buňce, a aktualizačním pravidlem. Mřížka buněk je často jednorozměrný nebo dvourozměrný nekonečný čtvercová mříž. Pravidlo aktualizace určuje další stav každé buňky jako funkci jejího aktuálního stavu a aktuálních stavů některých dalších blízkých buněk ( sousedství Sousedství může být libovolná konečná sada buněk, ale každé dvě buňky by měly mít sousedy ve stejných relativních pozicích a všechny buňky musí používat stejné pravidlo aktualizace. konfigurace automatu je přiřazení stavu každé buňce.[3]

The nástupce konfigurace je další konfigurace, vytvořená současným použitím pravidla aktualizace na každou buňku.[4]The přechodová funkce automatu je funkce, která mapuje každou konfiguraci na její nástupce.[3]Pokud je nástupcem konfigurace X je konfigurace Y, pak X je předchůdce z YKonfigurace může mít nulu, jednoho nebo více předchůdců, ale vždy má přesně jednoho následníka.[4]Zahrada Eden je definována jako konfigurace s nulovými předchůdci.[5]

A vzor, pro daný buněčný automat, se skládá z konečné sady buněk spolu se stavem pro každou z těchto buněk.[6] Konfigurace obsahuje vzor, ​​když jsou stavy buněk ve vzoru stejné jako stavy stejných buněk v konfiguraci (bez překladu buněk před jejich porovnáním). Definici předchůdců konfigurací lze rozšířit na předchůdce vzorů: předchůdce vzoru je pouze konfigurace, jejíž následník obsahuje vzor. Sirotek je tedy vzor bez předchůdce.[6]

Hledání rajské zahrady

U jednorozměrných celulárních automatů lze Garden of Eden najít jako efektivní algoritmus jehož doba běhu je polynomická ve velikosti tabulky pravidel automatu. U vyšších dimenzí je určení, zda zahrada Eden existuje nerozhodnutelný problém, což znamená, že neexistuje žádný algoritmus, který by zaručil ukončení a vytvoření správné odpovědi.[7] V mnoha případech je však možné pomocí věty Garden of Eden (níže) odvodit, že řešení existuje, a poté jej vyhledat pomocí vyhledávacího algoritmu.

Bylo by možné, aby počítačový program vyhledával osiřelé vzory systematickým zkoumáním všech konečných vzorů, aby se zvětšila velikost, a testováním všech možných předchůdců každého vzoru, aby se zjistilo, zda ve skutečnosti jde o osiřelé. Počet vzorů, které by bylo potřeba vygenerovat, aby bylo možné najít rajskou zahradu tímto způsobem, je však v oblasti vzoru exponenciální. Tento enormní počet vzorů by tento typ vytvořil vyhledávání hrubou silou neúnosně drahé, dokonce i pro relativně malé velikosti vzorů.[8]

Jean Hardouin-Duparc (1972–73, 1974 ) propagoval efektivnější výpočetní přístup k hledání osiřelých vzorů. Jeho metoda je založena na teorii formální jazyky, a trvá určitou dobu, která je exponenciální v šířce vzoru, nikoli v jeho oblasti. Klíčovou myšlenkou je, že pro jakoukoli pevnou šířku je možné postavit a nedeterministický konečný automat který rozpoznává vzory dané šířky, které mají předchůdce. Vstupní symboly do tohoto stroje popisují každou řadu vzoru a stavy stroje popisují blízké řady možných předchůdců pro část vzoru, která byla dosud zadána. Z tohoto stroje lze sestavit další stroj s konečným stavem, který rozpoznává doplňková sada, vzory, které nemají předchůdce, převedením nedeterministického stroje s konečným stavem na a deterministický konečný automat pomocí konstrukce výkonové sady, a pak doplnění jeho souboru přijímajících států. Jakmile je stroj rozpoznávající doplňkovou sadu zkonstruován, lze otestovat, zda je jazyk, který rozpoznává, prázdný, hledáním cesty ze počátečního stavu do přijímajícího stavu. Tato cesta, pokud existuje, poskytuje popis osamoceného vzoru po řádcích.[9]

Martin Gardner úvěry Alvy Ray Smith s pozorováním, na které se vztahuje věta o rajské zahradě Conwayova hra o život, a dokazuje existenci rajských zahrad pro toto pravidlo. První explicitní rajská zahrada v životě s živými buňkami zapadajícími do 9 × 33 obdélník, byl identifikován jako kandidát na zahradu Eden Roger Banks v roce 1971, a poté ověřen vyčerpávajícím zpětné vyhledávání pro předchůdce.[1]Následně Hardouin-Duparc použil svůj formální jazykový přístup k nalezení nejužší možné zahrady Eden v Conwayově hře o život s ohraničující rámeček protože jejich živé buňky byly široké pouze šest buněk.[10]

Nejmenší známý osiřelý vzor v Conwayově hře o život (podle oblasti jeho ohraničující krabice) našel Steven Eker v dubnu 2016. Má 57 živých buněk a vejde se do obdélníku 8 × 12.[11]

Existence sirotků

Podle definice každý sirotek patří do rajské zahrady: rozšíření sirotka na konfiguraci celého automatu, výběrem stavu pro každou zbývající buňku libovolně, vždy vytvoří rajskou zahradu. Ale platí to i naopak: každá rajská zahrada obsahuje alespoň jednoho sirotka.[12][13]Dokázat to, Kari[12] používá topologický argument založený na Curtis – Hedlund – Lyndonova věta podle kterého jsou přechodové funkce celulárních automatů přesně překladově invariantní spojité funkce na prostoru konfigurací.[14] Kontinuita je zde definována přiřazením a diskrétní topologie do konečné sady stavů automatu a poté pomocí a topologie produktu s jedním členem v produktu pro každou buňku v automatu a postavit a topologický prostor jejichž body jsou konfiguracemi automatu. Podle Tychonoffova věta to je kompaktní prostor.[12]

Pro každý konečný vzor je sada konfigurací, které obsahují vzor, otevřená sada v této topologii se nazývá a válec.[6] Válce tvoří a základ pro topologii. Jak poznamenává Kari, soubor konfigurací, které nejsou zahradami Eden, je pouze obrazem přechodové funkce, takže lemma uzavřené mapy pro kompaktní prostory je to uzavřená sada. Soubor zahrad Eden je tedy otevřeným souborem. Vzhledem k tomu, že je otevřená a válce tvoří základ, lze sadu zahrad Eden představovat jako spojení válců. Každý z válců v tomto spojení se skládá pouze ze zahrad Eden, takže vzor, ​​který určuje každý válec, musí být sirotek. Pokud sada zahrad Eden není prázdná, musí být v tomto svazku alespoň jeden válec, takže musí existovat alespoň jeden sirotek. A každá konkrétní zahrada Eden musí patřit k jednomu z těchto válců, a proto musí obsahovat sirotek pro tento válec.[12]

Věta o zahradě Eden

V celulárním automatu jsou dva konečné vzory dvojčata pokud lze jeden nahradit druhým, ať se objeví kdekoli, beze změny budoucích konfigurací. Mobilní automat je injekční pokud každá dvojice odlišných konfigurací automatu zůstane po kroku automatu odlišná, a lokálně injektivní, pokud nemá dvojčata. to je surjektivní právě když má každá konfigurace předchůdce; to znamená, že a pouze v případě, že nemá konfiguraci Garden of Eden. Automat, který je injektivní i surjektivní, se nazývá a reverzibilní buněčný automat.[3]

The Veta o zahradě Eden, kvůli Edward F. Moore  (1962 ) a John Myhill  (1963 ), tvrdí, že mobilní automat v a Euklidovský prostor je lokálně injektivní právě tehdy, je-li surjektivní. Jinými slovy tvrdí, že buněčný automat má rajskou zahradu, jen když má dvojčata. Silnější je, že každý lokálně injektivní buněčný automat má osamocený vzor. Okamžitým důsledkem je, že injektivní buněčný automat musí být surjektivní. Moore dokázal jeden směr věty, že automaty s dvojčaty mají sirotky;[2] Myhill dokázal konverzaci, že automat se sirotkem má také dvojčata.[15]

V případě hry Conway's of Life jsou dvojčata mnohem snáze dostupná než sirotci. Například blok mrtvých buněk pět na pět a blok pět na pět se střední buňkou živou a zbývající mrtvé buňky jsou dvojčata: stav centrální buňky nemůže ovlivnit pozdější konfigurace vzoru. V tomto případě tedy věta o rajské zahradě umožňuje, aby byla existence rajské zahrady prokázána mnohem snadněji než nalezením výslovného vzoru osiřelých.[16]

Důkazní skica

Hlavní myšlenkou důkazu věty je použít a argument počítání, ukázat, že jakékoli selhání lokální injektivity (dvojčata) vede k osamocenému vzoru a naopak. Podrobněji předpokládejme, že základní mřížkou automatu je dvourozměrná čtvercová mřížka, kterou má s různé buněčné stavy, že dvojčata P a Q oba zapadají do n × n čtverec a že poloměr sousedství jakékoli buňky je nanejvýš n. Poté, abychom zjistili, zda vzor, ​​který zapadá do mn × mn čtverec je sirotek, stačí se podívat na části potenciálních předchůdců, které se vejdou do (m + 2)n × (m + 2)n čtverec a které neobsahují vzor Q. Ale existují pouze(sn × n − 1)(m + 2) × (m + 2) těchto potenciálních předchůdců. Pro dostatečně velké hodnoty m toto číslo je menší než číslo smn × mn potenciálních sirotků. Jeden z potenciálních sirotků proto nemá předchůdce a je skutečně sirotkem; to znamená, že neinjekčnost znamená ne-surjektivitu. Naopak (nechat n být velikost a ohraničující rámeček sirotka) velmi podobný argument počítání ukazuje, že počet vzorů, které se vejdou do (m + 2)n × (m + 2)n čtverec a neobsahují sirotek je příliš malý na to, aby poskytl zřetelného nástupce každého výchozího vzoru v rámci mn × mn čtverec, ze kterého vyplývá, že některé dva z možných počátečních vzorů jsou dvojčata. Non-surjectivity proto znamená místní non-injectivity.[15]

Injektivita versus lokální injekce

Časoprostorový diagram Pravidlo 90, který nemá žádnou rajskou zahradu, přestože není injektivní. Každý řádek zobrazuje konfiguraci s časem postupujícím dolů.

Rozdíl mezi injektivitou a lokální injektivitou ve větě je nezbytný, protože existují buněčné automaty, které jsou lokálně injektivní, ale ne injektivní. Jedním z příkladů je Pravidlo 90, jednorozměrný binární automat, jehož pravidlo aktualizace nahradí stav každé buňky znakem exkluzivní nebo jejích dvou sousedů. V tomto automatu má každý stát čtyři předchůdce, takže není injektivní, ale také nemá rajskou zahradu.[17]

S klidovými stavy

V automatech, jako je Conwayova hra o život, existuje speciální "klidový" stav, kdy klidová buňka, jejíž okolí je zcela v klidovém stavu, zůstává klidová. V tomto případě lze definovat „konečnou konfiguraci“ jako konfiguraci pouze s konečně mnoha neklidnými buňkami. Jakýkoli buněčný automat bez lokálního vstřikování s klidovým stavem má Gardens of Eden, které jsou samy konečnými konfiguracemi, například jakoukoli konečnou konfigurací, která obsahuje sirotek. Je také možné, aby automat měl konečnou konfiguraci, jejíž jediní předchůdci nejsou koneční (například v pravidle 90 má tuto vlastnost konfigurace s jedinou živou buňkou). Věta o zahradě Eden však necharakterizuje existenci takových vzorů.[18]

V neeuklidovských geometriích

V celulárních automatech definovaných přes mozaiky hyperbolická rovina, nebo hyperbolických prostorů vyšších dimenzí, argument počítání v důkazu věty o zahradě Eden nefunguje, protože implicitně závisí na vlastnosti euklidovských prostorů, že hranice oblasti roste méně rychle než její objem jako funkce poloměru. Existují hyperbolické buněčné automaty, které mají dvojčata, ale nemají zahradu Eden, a další hyperbolické celulární automaty, které mají zahradu Eden, ale nemají dvojčata; tyto automaty lze definovat například rotačně invariantním způsobem na jednotné hyperbolické obklady ve kterém tři sedmiúhelníky setkat se u každého vrcholu, nebo ve kterém čtyři pětiúhelníky setkat se na každém vrcholu.[19]

Věta Garden of Eden však může být zobecněna mimo euklidovské prostory, na buněčné automaty definované na prvcích přístupná skupina.[20] Slabší forma věty o zahradě Eden tvrdí, že každý injekční buněčný automat je surjektivní. To lze prokázat společenské skupiny za použití Věta Ax – Grothendieck, analogický vztah mezi injektivitou a bijektivitou v algebraické geometrii.[21] Obecněji se nazývají skupiny, pro které platí tato slabší forma surjunktivní skupiny.[22] Nejsou známy žádné příklady skupin, které nejsou surjunktivní.[23]

V beletrii

v Greg Egan román Permutační město, protagonista používá konfiguraci Garden of Eden k vytvoření situace, ve které jeho kopie může dokázat, že žije v simulaci. Dříve se všechny jeho simulované kopie ocitly v nějaké variantě „skutečného světa“; ačkoli měli vzpomínky na simulované kopie žijící v simulaci, vždy existovalo jednodušší vysvětlení toho, jak tyto vzpomínky vznikly. Konfigurace Garden of Eden však nemůže nastat, kromě inteligentně navržené simulace. Náboženské paralely jsou úmyslné.[24]

Poznámky

  1. ^ A b v Záchranné lano Sv. 3 (Září 1971), redaktor Robert T. Wainwright oznámil, že Roger Banks a Steve Ward prokázali existenci rajské zahrady, jejíž živé buňky zapadají do 9 × 33 obdélník a představil konfiguraci, kterou Banks považoval za rajskou zahradu. v Záchranné lano Sv. 4 (Prosinec 1971), Wainwright uvedl, že skupina v Honeywell pomocí softwaru Don Woods ověřil Banksovu konfiguraci jako rajskou zahradu. Viz také Gardner (1983).
  2. ^ A b Moore (1962).
  3. ^ A b C Kari (2012), Sekce 2.1, „Základní definice“, s. 5–6.
  4. ^ A b Toffoli & Margolus (1990). Všimněte si však, že Toffoli a Margolus označují přechodovou funkci jako globální mapu.
  5. ^ Kari (2012), str. 10.
  6. ^ A b C Kari (2012), str. 11.
  7. ^ Kari (1990); Kari (1994). Kari je hlavním výsledkem je, že je nerozhodnutelné testovat, zda je buněčný automat reverzibilní, ale také ukazuje nerozhodnost testování, zda existuje rajská zahrada.
  8. ^ Toffoli & Margolus (1990): "I kdyby byl člověk ochoten upustit od hledání hrubou silou, dlouhá doba hledání by vygenerovala jen několik položek, a dokonce i ty by byly z velké části docela nezajímavé."
  9. ^ Hardouin-Duparc (1972–1973).
  10. ^ Hardouin-Duparc (1974).
  11. ^ Flammenkamp (2016).
  12. ^ A b C d Kari (2012), Tvrzení 2, s. 11.
  13. ^ Jednorozměrným případem tohoto výsledku je Věta 5.1 z Hedlund (1969). Stejně jako v jednodušším důkazu, který je zde uveden, využívá kompaktnost konfiguračního prostoru. Ve své dřívější práci Moore a Myhill nerozlišovali sirotky od rajských zahrad a své výsledky prokázali pouze ve vztahu k sirotkům.
  14. ^ Hedlund (1969), Věta 3.4.
  15. ^ A b Myhill (1963).
  16. ^ Gardner (1983).
  17. ^ Sutner (1991).
  18. ^ Amoroso & Cooper (1970); Skyum (1975).
  19. ^ Margenstern (2009). Margenstern připisuje výsledek společně sobě a Jarkko Kari.
  20. ^ Ceccherini-Silberstein, Machì & Scarabotti (1999); Capobianco, Guillon & Kari (2013); Bartholdi & Kielak (2016).
  21. ^ Gromov (1999).
  22. ^ Gottschalk (1973).
  23. ^ Ceccherini-Silberstein & Coornaert (2010).
  24. ^ Blackford, Ikin & McMullen (1999); Hayles (2005).

Reference

  • Amoroso, S .; Cooper, G. (1970), „The-Edenova věta pro konečné konfigurace“, Proceedings of the American Mathematical Society, 26 (1): 158–164, doi:10.1090 / S0002-9939-1970-0276007-5
  • Bartholdi, Laurent; Kielak, Dawid (2016), Amenabilitu skupin charakterizuje Myhillova věta, arXiv:1605.09133
  • Blackford, Russell; Ikin, Van; McMullen, Sean (1999), „Greg Egan“, Podivná konstelace: historie australské sci-fiPříspěvky ke studiu science fiction a fantasy 80, Greenwood Publishing Group, str.190–200, ISBN  978-0-313-25112-2
  • Capobianco, Silvio; Guillon, Pierre; Kari, Jarkko (2013), „Surjective cellular automata far from the Garden of Eden“, Diskrétní matematika a teoretická informatika, 15 (3): 41–60, PAN  3141826
  • Ceccherini-Silberstein, Tullio; Coornaert, Michel (2010), „Surjunctive groups“, Mobilní automaty a skupinySpringer Monografie z matematiky, Springer-Verlag, str. 57–75, doi:10.1007/978-3-642-14034-1_3, ISBN  978-3-642-14033-4, PAN  2683112
  • Ceccherini-Silberstein, T. G .; Machì, A .; Scarabotti, F. (1999), „Upravitelné skupiny a mobilní automaty“, Annales de l'Institut Fourier, 49 (2): 673–685, doi:10,5802 / aif.1686, PAN  1697376
  • Flammenkamp, ​​Achim (duben 2016), „Rajská zahrada / sirotek“, Stránka Achimovy hry o život
  • Gardner, Martin (1983), „Kapitoly 20 a 21: Hra o život, část I a II“ (PDF), Kola, život a další matematické zábavy, W. H. Freeman, str. 214–258; viz zejména s. 230 a 248
  • Gottschalk, Walter (1973), „Některé obecné dynamické pojmy“, Nedávné pokroky v topologické dynamice (Proc. Conf. Topological Dynamics, Yale Univ., New Haven, Connecticut, 1972; na počest Gustava Arnolda Hedlunda), Poznámky k přednášce v matematice., 318, Springer-Verlag, str. 120–125, doi:10.1007 / BFb0061728, PAN  0407821
  • Gromov, M. (1999), „Endomorfismy symbolických algebraických variet“, Věstník Evropské matematické společnosti, 1 (2): 109–197, doi:10.1007 / PL00011162, PAN  1694588, Zbl  0998.14001
  • Hardouin-Duparc, J. (1972–1973), „À la recherche du paradis perdu“, Publ. Matematika. Univ. Bordeaux Année, 4: 51–89
  • Hardouin-Duparc, J. (1974), „Paradis terrestre dans l'automate cellulaire de Conway“, Rev. Française Automat. Informat. Recherche Operationnelle Ser. Rouge, 8 (R-3): 64–71
  • Hartman, Christiaan; Heule, Marijn J. H .; Kwekkeboom, Kees; Noels, Alain (2013), „Symetrie v zahradách Eden“, Electronic Journal of Combinatorics, 20 (3): P16, doi:10.37236/2611, PAN  3104514
  • Hayles, N. Katherine (2005), „Subjektivní kosmologie a režim výpočtu: zprostředkování ve fikci Grega Egana“, Moje matka byla počítač: digitální předměty a literární texty, University of Chicago Press, s. 214–240, ISBN  978-0-226-32147-9
  • Hedlund, G. A. (1969), „Endomorfismy a automorfismy dynamických systémů řazení“, Teorie matematického systému, 3 (4): 320–375, doi:10.1007 / BF01691062
  • Kari, Jarkko (1990), „Reverzibilita 2D celulárních automatů je nerozhodnutelná“, Physica D, 45 (1–3): 379–385, doi:10.1016 / 0167-2789 (90) 90195-U
  • Kari, Jarkko (1994), "Problémy reverzibility a surjektivity celulárních automatů", Journal of Computer and System Sciences, 48 (1): 149–182, doi:10.1016 / S0022-0000 (05) 80025-X, PAN  1259654
  • Kari, Jarkko J. (2012), „Basic Concepts of Cellular Automata“, Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (eds.), Příručka přírodních výpočtů, Springer, str. 3–24, doi:10.1007/978-3-540-92910-9_1
  • Margenstern, Maurice (2009), „O větách Edenovy zahrady pro buněčné automaty v hyperbolické rovině“, 15. mezinárodní seminář o celulárních automatech a diskrétních komplexních systémech, Elektronické poznámky v teoretické informatice, 252, str. 93–102, doi:10.1016 / j.entcs.2009.09.016
  • Moore, E. F. (1962), „Strojové modely vlastní reprodukce“, Proc. Symp. Aplikovaná matematikaSborník sympozií z aplikované matematiky, 14: 17–33, doi:10.1090 / psapm / 014/9961, ISBN  9780821813140; dotisk dovnitř Burks, Arthur W. (1970), Eseje o celulárních automatech, University of Illinois Press, s. 187–203.
  • Myhill, J. (1963), „Konverzace Moorovy věty o zahradě Eden“, Proceedings of the American Mathematical Society, 14: 685–686, doi:10.2307/2034301, JSTOR  2034301; dotisk dovnitř Burks, Arthur W. (1970), Eseje o celulárních automatech„University of Illinois Press, s. 204–205.
  • Skyum, Sven (1975), „Zmatek v zahradě Eden“, Proceedings of the American Mathematical Society, 50 (1): 332–336, doi:10.1090 / S0002-9939-1975-0386350-1
  • Sutner, Klaus (1991), „De Bruijnovy grafy a lineární celulární automaty“ (PDF), Složité systémy, 5: 19–30, PAN  1116419
  • Toffoli, Tommaso; Margolus, Norman (1990), "Invertible cellular automata: a review", Physica D: Nelineární jevy, 45 (1–3): 229–253, doi:10.1016 / 0167-2789 (90) 90185-R, PAN  1094877

externí odkazy