Grădina Edenului (configurație automată celulară)

Grădina Edenului ( orfan , English  Garden of Eden , orfan ) [2] [3]  este o configurație din Conway’s Game of Life sau alt automat celular care nu poate apărea ca urmare a evoluției deoarece nu are predecesori. Termenul „Grădina Edenului” a fost inventat de John Tukey în anii 1950, cu mult înainte ca Viața să apară.

În căutarea grădinilor Edenului

Se poate încerca să efectueze o căutare sistematică a grădinilor Edenului în ordinea crescătoare a numărului de celule, sortând pentru fiecare candidat pentru „orfani” toate configurațiile anterioare posibile. Cu toate acestea, această metodă este nepractică deoarece numărul de configurații „Life” într-un dreptunghi dintr-o zonă dată N este 2 N , iar enumerarea exhaustivă devine inacceptabilă chiar și pentru zonele moderate.

O metodă mai eficientă de calcul se bazează pe teoria limbajelor formale ; complexitatea în timp a acestei abordări depinde exponențial nu de zonă, ci de lățimea casetei de delimitare [4] [5] .

Prima Grădină a Edenului cunoscută în viață, situată într-un dreptunghi de 9 × 33, a fost găsită de Roger Banks în 1971 [1] . În 1973-74. Grădinile Edenului au fost construite în dreptunghiuri 6 × 122 și 6 × 117 [6] [7] [8] . În decembrie 2011, a fost găsită grădina Edenului, formată din 56 de celule vii și încadrate într-un pătrat de 10 × 10; s-a mai constatat că nu există Grădinile Edenului în dreptunghiuri mai mici de 6 × 6 [9] .

Teorema Grădinii Edenului

Două configurații finite ale unui automat celular sunt numite gemeni dacă evoluțiile lor , începând de la generația următoare, coincid complet. Un automat celular se numește injectiv dacă nu există gemeni în acest automat. Se spune că un automat celular este surjectiv dacă și numai dacă fiecare configurație are un părinte, adică dacă nu există Grădinile Edenului. Un automat care este atât injectiv cât și surjectiv se numește automat celular reversibil .  

Teorema Grădinii Edenului afirmă că un automat celular dintr-un univers euclidian  este local injectiv dacă și numai dacă este surjectiv. Cu alte cuvinte, teorema afirmă că Grădinile Edenului există doar în acele automate în care există gemeni.

Teorema se aplică la „Viață”, deoarece este ușor să găsești două configurații diferite care evoluează în generația următoare în aceeași configurație. Un „univers mort” și o celulă vie singură într-un „univers mort” evoluează în aceeași configurație, toate celulele fiind moarte. Prin urmare, în „Viața” există grădini ale Edenului [6] [7] [8] .

Teorema Grădinii Edenului a fost propusă de Edward Moore și demonstrată de Moore și John Myhill [10] [11] [8] .

Probleme conexe

Încă nu se știe dacă există o configurație care are un „tată” dar nu „bunic” [12] [13] [14] .

Deși orice configurație de viață are un singur copil, invers nu este adevărat. O configurație dată poate avea doi sau mai mulți „părinți”. De aceea, găsirea grădinilor Edenului este atât de dificilă: computerul trebuie să exploreze toți părinții posibili la fiecare pas „în trecut”. <...> De altfel, faptul că un „fiu” al Grădinii Edenului poate avea mai mult de un „tată” l-a determinat pe Conway să ofere un premiu de 50 USD primei persoane care poate găsi o configurație care are un „tată” dar nici un „bunic”. Existența unei astfel de configurații este încă o întrebare deschisă.Martin Gardner [13]

Note

1. ↑ 1 2 în Lifeline Vol. 3 Arhivat 19 martie 2012 la Wayback Machine (septembrie 1971) a fost făcut un anunț că Roger Banks și Steve Ward au dovedit existența unui dreptunghi de 9x33 Garden of Eden și au prezentat un exemplar despre care Banks credea că este Grădina Edenului . În Lifeline Vol. 4 Arhivat la 19 martie 2012 la Wayback Machine (decembrie 1971) Editorul Robert Wainwright a raportat că un grup de la Honeywell a testat independent eșantionul Banks și a confirmat rezultatul. Vezi, de asemenea , Gardner, Martin, Wheels, Life, and Other Mathematical Amusements , p. 248 , < http://maa.org/pubs/focus/Gardner_GameofLife10-1970.pdf > . Preluat la 11 august 2013. Arhivat la 17 iunie 2011 la Wayback Machine .  
2. ↑ Orfan . Dicţionar al vieţii. Preluat la 11 august 2013. Arhivat din original la 10 octombrie 2012. (nedefinit)
3. ↑ Orfan . lexicon de viață. Arhivat din original pe 15 octombrie 2014. (nedefinit)
4. ↑ Hardouin-Duparc, J. (1972/73), À la recherche du paradis perdu, Publ. Matematică. Univ. Bordeaux Année T. 4: 51–89 
5. ↑ Hardouin-Duparc, J. (1974), Paradis terrestre dans l'automate cellulaire de Conway, Rev. Franceza Automat. informa. Recherche Operationnelle Ser. Rouge T. 8 (R-3): 64–71 
6. ↑ 1 2 Grădina Edenului . Dicţionar al vieţii. Preluat la 11 august 2013. Arhivat din original la 10 octombrie 2012. (nedefinit)
7. ↑ 12 Grădina Edenului . lexicon de viață. Arhivat din original pe 18 aprilie 2009. (nedefinit)
8. ↑ 1 2 3 Grădina Edenului . conwaylife.com. Preluat la 11 august 2013. Arhivat din original la 1 august 2013. (nedefinit)
9. ↑ Grădinile Edenului (downlink) . Cea mai mică grădină a Edenului (14 ianuarie 2012). Preluat la 20 ianuarie 2022. Arhivat din original la 24 noiembrie 2012. (nedefinit) 
10. ↑ Moore, E.F. (1962), Modele de mașini de auto-reproducție, Proc. Symp. Matematică aplicată vol . 14:17–33 
11. ↑ Myhill, J. (1963), The converse of Moore's Garden-of-Eden theorema , Proceedings of the American Mathematical Society vol. 14: 685–686 , DOI 10.2307/2034301  . Retipărit în Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, p. 204–205 
12. ↑ Eric Weisstein. Grădina Edenului (link indisponibil) . Comoara din Jocul Vieții. Preluat la 11 august 2013. Arhivat din original la 6 ianuarie 2009. (nedefinit) 
13. ↑ 12 Martin Gardner . 22. Jocul vieții, partea a III-a // Roți, viață și alte distracții matematice  (engleză) . - W. H. Freeman and Company, 1983.
14. ↑ Lifeline Volumul 6 . conwaylife.com. Data accesului: 16 octombrie 2015. Arhivat din original pe 10 decembrie 2015. (nedefinit)

Literatură

• Margenstern, Maurice (2009), Despre teoremele Grădinii Edenului pentru automatele celulare în planul hiperbolic , al 15-lea Atelier internațional de automate celulare și sisteme complexe discrete , voi. 252, Note electronice în informatică teoretică, p. 93–102 , DOI 10.1016/j.entcs.2009.09.016 
• Moore, E. F. (1962), Modele de mașini de auto-reproducție, Proc. Symp. Matematică aplicată T. 14:17–33  . Retipărit în Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, p. 187–203