Garden of Eden (cellulär automatkonfiguration)

The Garden of Eden ( föräldralös , engelska  Garden of Eden , föräldralös ) [2] [3]  är en konfiguration i Conways Game of Life eller annan cellulär automat som inte kan dyka upp som ett resultat av evolutionen eftersom den inte har några föregångare. Termen "Garden of Eden" myntades av John Tukey redan på 1950-talet, långt innan Life dök upp.

Quest for the Gardens of Eden

Man kan försöka genomföra en systematisk sökning efter Edens trädgårdar i stigande ordning efter antalet celler, genom att sortera för varje kandidat för "föräldralösa barn" alla möjliga tidigare konfigurationer. Emellertid är denna metod opraktisk eftersom antalet "Life"-konfigurationer i en rektangel av ett givet område N är 2N , och en uttömmande uppräkning blir oacceptabel även för måttliga områden.

En mer effektiv beräkningsmetod är baserad på teorin om formella språk ; tidskomplexiteten för detta tillvägagångssätt beror exponentiellt inte på området, utan på bredden av begränsningsramen [4] [5] .

Den första kända Edens trädgård i livet, som ligger i en 9 × 33 rektangel, hittades av Roger Banks 1971 [1] . Åren 1973-74. Edens trädgårdar byggdes i rektanglar 6 × 122 och 6 × 117 [6] [7] [8] . I december 2011 hittades Edens trädgård, bestående av 56 levande celler och passande i en 10 × 10 kvadrat; man fann också att det inte finns några Edens trädgårdar i rektanglar som är mindre än 6 × 6 [9] .

Edens trädgård teorem

Två ändliga konfigurationer av en cellulär automat kallas tvillingar om deras utveckling , från och med nästa generation, helt sammanfaller. En cellulär automat kallas injektiv om det inte finns tvillingar i denna automat. En cellulär automat sägs vara surjektiv om och bara om varje konfiguration har en förälder, det vill säga om det inte finns några Edens trädgårdar. En automat som är både injektiv och surjektiv kallas en reversibel cellulär automat .  

The Garden of Eden-satsen säger att en cellulär automat i ett euklidiskt  universum är lokalt injektiv om och bara om den är surjektiv. Med andra ord, satsen säger att Edens trädgårdar endast existerar i de automater där tvillingar existerar.

Teoremet gäller "Life" eftersom det är lätt att hitta två olika konfigurationer som utvecklas i nästa generation till samma konfiguration. Ett "dött universum" och en ensam levande cell i ett "dött universum" utvecklas till samma konfiguration, där alla celler är döda. Därför finns det i "Livet" Edens trädgårdar [6] [7] [8] .

The Garden of Eden theorem lades fram av Edward Moore och bevisades av Moore och John Myhill [10] [11] [8] .

Relaterade frågor

Det är fortfarande okänt om det finns en konfiguration som har en "far" men ingen "farfar" [12] [13] [14] .

Även om varje Life-konfiguration bara har ett barn, är det omvända inte sant. En given konfiguration kan ha två eller flera "fäder". Det är därför det är så svårt att hitta Edens trädgårdar: datorn måste utforska alla möjliga fäder vid varje steg "in i det förflutna". <...> För övrigt, det faktum att en "son" i Edens lustgård kan ha mer än en "far" ledde till att Conway erbjöd ett pris på $50 till den första personen som kan hitta en konfiguration som har en "far" men ingen "farfar". Förekomsten av en sådan konfiguration är fortfarande en öppen fråga.Martin Gardner [13]

Anteckningar

1. ↑ 1 2 i Lifeline Vol. 3 Arkiverad 19 mars 2012 på Wayback Machine (september 1971) gjordes ett tillkännagivande om att Roger Banks och Steve Ward hade bevisat existensen av en 9x33 rektangel Garden of Eden och presenterade ett exemplar som Banks trodde var Edens trädgård . I Lifeline Vol. 4 Arkiverad 19 mars 2012 på Wayback Machine (december 1971) Redaktör Robert Wainwright rapporterade att en grupp på Honeywell oberoende testade Banks prov och bekräftade resultatet. Se även Gardner, Martin, Wheels, Life, and Other Mathematical Amusements , sid. 248 , < http://maa.org/pubs/focus/Gardner_GameofLife10-1970.pdf > . Hämtad 11 augusti 2013. Arkiverad 17 juni 2011 på Wayback Machine .  
2. ↑ Föräldralös . Livets ordbok. Hämtad 11 augusti 2013. Arkiverad från originalet 10 oktober 2012. (obestämd)
3. ↑ Föräldralös . livslexikon. Arkiverad från originalet den 15 oktober 2014. (obestämd)
4. ↑ Hardouin-Duparc, J. (1972/73), À la recherche du paradis perdu, Publ. Matematik. Univ. Bordeaux Année T. 4: 51–89 
5. ↑ Hardouin-Duparc, J. (1974), Paradis terrestre dans l'automate cellulaire de Conway, Rev. Francaise Automat. information. Recherche Operationnelle Ser. Rouge T. 8 (R-3): 64–71 
6. ↑ 1 2 Edens trädgård . Livets ordbok. Hämtad 11 augusti 2013. Arkiverad från originalet 10 oktober 2012. (obestämd)
7. ↑ 12 Edens trädgård . livslexikon. Arkiverad från originalet den 18 april 2009. (obestämd)
8. ↑ 1 2 3 Edens trädgård . conwaylife.com. Hämtad 11 augusti 2013. Arkiverad från original 1 augusti 2013. (obestämd)
9. ↑ Edens trädgårdar (nedlänk) . Edens minsta trädgård (14 januari 2012). Hämtad 20 januari 2022. Arkiverad från originalet 24 november 2012. (obestämd) 
10. ↑ Moore, E.F. (1962), Machine models of self-reproduction, Proc. Symp. Tillämpad matematik vol 14:17–33 
11. ↑ Myhill, J. (1963), The converse of Moore's Garden-of-Eden theorem , Proceedings of the American Mathematical Society vol. 14: 685–686 , DOI 10.2307/2034301  . Omtryckt i Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, sid. 204–205 
12. ↑ Eric Weisstein. Edens trädgård (inte tillgänglig länk) . Treasure Trove i The Game of Life. Hämtad 11 augusti 2013. Arkiverad från originalet 6 januari 2009. (obestämd) 
13. ↑ 12 Martin Gardner . 22. The Game of Life, del III // Wheels, life och andra matematiska nöjen  (engelska) . — W. H. Freeman and Company, 1983.
14. ↑ Lifeline Volym 6 . conwaylife.com. Datum för åtkomst: 16 oktober 2015. Arkiverad från originalet den 10 december 2015. (obestämd)

Litteratur

• Margenstern, Maurice (2009), Om Edens lustgårds satser för cellulära automater i det hyperboliska planet , 15:e internationella workshopen om cellulära automater och diskreta komplexa system , vol. 252, Electronic Notes in Theoretical Computer Science, sid. 93–102 , DOI 10.1016/j.entcs.2009.09.016 
• Moore, E. F. (1962), Maskinmodeller för självreproduktion, Proc. Symp. Tillämpad matematik T. 14:17–33  . Omtryckt i Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, sid. 187–203