Garden of Eden (celluláris automata konfiguráció)

Az Édenkert ( orphan , angol  Garden of Eden, orphan ) [2] [3] Conway Game of Life vagy más sejtautomata  konfigurációja, amely az evolúció eredményeként nem tud megjelenni, mert nincsenek elődei. A "Garden of Eden" kifejezést John Tukey találta ki még az 1950-es években, jóval az élet megjelenése előtt.

Quest for the Gardens of Eden

Megpróbálhatjuk szisztematikusan felkutatni az édenkerteket a cellák számának növekvő sorrendjében, az „árvák” jelöltek között minden lehetséges korábbi konfigurációt átválogatva. Ez a módszer azonban nem praktikus, mert egy adott N terület téglalapjában az "Élet" konfigurációk száma 2 N , és a kimerítő felsorolás még a mérsékelt területek esetében is elfogadhatatlan.

Egy hatékonyabb számítási módszer a formális nyelvek elméletén alapul ; ennek a megközelítésnek az időbonyolultsága exponenciálisan nem a területtől, hanem a határolókeret szélességétől függ [4] [5] .

Az élet első ismert Édenkertjét, amely egy 9 × 33-as téglalapban található, Roger Banks találta meg 1971-ben [1] . 1973-74-ben. az Édenkertek 6 × 122 és 6 × 117 téglalapokban épültek [6] [7] [8] . 2011 decemberében megtalálták az Éden kertjét, amely 56 élő sejtből áll, és egy 10 × 10-es négyzetbe illeszkedik; azt is megállapították, hogy 6 × 6-nál kisebb téglalapokban nincsenek Édenkertek [9] .

Édenkert tétel

A sejtautomaták két véges konfigurációját ikreknek nevezzük , ha fejlődésük a következő generációtól kezdve teljesen egybeesik. Egy sejtautomatát injektívnek nevezünk , ha ebben az automatában nincsenek ikrek. Egy cellás automatát akkor és csak akkor mondunk szürjektívnek , ha minden konfigurációnak van szülője, vagyis ha nincsenek Édenkertek. Az injektív és szurjektív automatát reverzibilis cellás automatának nevezzük .  

Az Édenkert tétele kimondja , hogy egy sejtautomata egy euklideszi  univerzumban akkor és csak akkor lokálisan injektív, ha szürjektív. Más szavakkal, a tétel kimondja, hogy az Édenkertek csak azokban az automatákban léteznek, amelyekben ikrek léteznek.

A tétel az "Élet"-re vonatkozik, mert könnyű találni két különböző konfigurációt, amelyek a következő generációban azonos konfigurációvá fejlődnek. Egy „halott univerzum” és egy „halott univerzum” magányos élő sejtje ugyanabba a konfigurációba fejlődik, amelynek minden sejtje halott. Ezért az "Életben" az Éden kertjei [6] [7] [8] vannak .

Az édenkert tételt Edward Moore terjesztette elő, és Moore és John Myhill [10] [11] [8] bebizonyította .

Kapcsolódó kérdések

Még mindig nem ismert, hogy létezik-e olyan konfiguráció, amelynek van "apja", de nincs "nagyapja" [12] [13] [14] .

Bár minden életkonfigurációnak csak egy gyermeke van, ennek az ellenkezője nem igaz. Egy adott konfigurációnak két vagy több "atyja" lehet. Ezért olyan nehéz megtalálni az édenkerteket: a számítógépnek minden lehetséges apát fel kell tárnia minden lépésnél a „múltba”. <...> Egyébként az a tény, hogy az Édenkert "fiának" több "apja" is lehet, arra késztette Conwayt, hogy 50 dolláros díjat ajánlott fel annak, aki először talál olyan konfigurációt, amelynek van "apja", de nincs "nagyapa". Egy ilyen konfiguráció megléte még nyitott kérdés.Martin Gardner [13]

Jegyzetek

1. ↑ 1 2 in Lifeline Vol. 3 Archivált 2012. március 19-én a Wayback Machine -nél (1971. szeptember) bejelentést tettek arról, hogy Roger Banks és Steve Ward bebizonyították egy 9x33-as téglalap méretű Garden of Eden létezését, és bemutattak egy példányt, amelyről Banks úgy gondolta, hogy az Édenkert . In Lifeline Vol. 4 Archiválva : 2012. március 19., a Wayback Machine (1971. december) Robert Wainwright szerkesztő arról számolt be, hogy a Honeywell egyik csoportja függetlenül tesztelte a Banks-mintát, és megerősítette az eredményt. Lásd még Gardner, Martin, Wheels, Life, and Other Mathematical Amusements , p. 248 , < http://maa.org/pubs/focus/Gardner_GameofLife10-1970.pdf > . Letöltve: 2013. augusztus 11. Archiválva : 2011. június 17. a Wayback Machine -nél .  
2. ↑ Árva . Életszótár. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2012. október 10.. (határozatlan)
3. ↑ Árva . életlexikon. Az eredetiből archiválva: 2014. október 15. (határozatlan)
4. ↑ Hardouin-Duparc, J. (1972/73), À la recherche du paradis perdu, Publ. Math. Univ. Bordeaux Année T. 4: 51–89 
5. ↑ Hardouin-Duparc, J. (1974), Paradis terrestre dans l'automate cellulaire de Conway, Rev. Francaise Automata. informat. Recherche Operationnelle Ser. Rouge T. 8 (R-3): 64–71 
6. ↑ 1 2 Édenkert . Életszótár. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2012. október 10.. (határozatlan)
7. ↑ 12 Édenkert . _ életlexikon. Archiválva az eredetiből 2009. április 18-án. (határozatlan)
8. ↑ 1 2 3 Édenkert . conwaylife.com. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2013. augusztus 1.. (határozatlan)
9. ↑ Gardens of Eden (downlink) . Legkisebb Édenkert (2012. január 14.). Letöltve: 2022. január 20. Az eredetiből archiválva : 2012. november 24.. (határozatlan) 
10. ↑ Moore, E.F. (1962), Az önreprodukció gépi modelljei, Proc. Symp. Alkalmazott matematika 14:17–33 
11. ↑ Myhill, J. (1963), Moore Garden-of-Eden tételének megfordítása , Proceedings of the American Mathematical Society , 14. kötet: 685–686 , DOI 10.2307/2034301  . Újranyomva: Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, p. 204–205 
12. ↑ Eric Weisstein. Édenkert (nem elérhető link) . Az életjáték kincsesbánya. Letöltve: 2013. augusztus 11. Az eredetiből archiválva : 2009. január 6.. (határozatlan) 
13. ↑ 12 Martin Gardner . 22. Az élet játéka, III. rész // Kerekek, élet és egyéb matematikai mulatságok  (angol) . - W. H. Freeman és Társaság, 1983.
14. ↑ Életvonal 6. kötet . conwaylife.com. Hozzáférés időpontja: 2015. október 16. Az eredetiből archiválva : 2015. december 10. (határozatlan)

Irodalom

• Margenstern, Maurice (2009), About the Garden of Eden tételek celluláris automatákra a hiperbolikus síkban , 15. Nemzetközi Workshop on Cellular Automata and Discrete Complex Systems , vol. 252, Electronic Notes in Theoretical Computer Science, p. 93–102 , DOI 10.1016/j.entcs.2009.09.016 
• Moore, E. F. (1962), Machine Models of self-reproduction, Proc. Symp. Alkalmazott matematika T. 14:17–33  . Újranyomva: Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, p. 187–203