Garden of Eden (soluautomaattikokoonpano)

The Garden of Eden ( orphan , English  Garden of Eden, orphan ) [2] [3]  on Conwayn Game of Lifen tai muun soluautomaatin konfiguraatio, joka ei voi ilmaantua evoluution seurauksena, koska sillä ei ole edeltäjiä. Termi "Garden of Eden" loi John Tukey jo 1950-luvulla, kauan ennen elämän ilmestymistä.

Quest for the Gardens of Eden

Eedenin puutarhoja voidaan yrittää etsiä järjestelmällisesti solujen lukumäärän nousevassa järjestyksessä, lajittelemalla jokaisen "orpojen" ehdokkaan mukaan kaikki mahdolliset aiemmat kokoonpanot. Tämä menetelmä on kuitenkin epäkäytännöllinen, koska "Elämä"-konfiguraatioiden lukumäärä tietyn alueen N suorakulmiossa on 2 N ja tyhjentävä luettelointi tulee mahdottomaksi edes kohtalaisilla alueilla.

Tehokkaampi laskentamenetelmä perustuu muodollisten kielten teoriaan ; tämän lähestymistavan aikamonimutkaisuus ei riipu eksponentiaalisesti alueesta, vaan rajoituslaatikon leveydestä [4] [5] .

Roger Banks löysi elämän ensimmäisen tunnetun Garden of Edenin vuonna 1971 [1] , joka sijaitsee 9 × 33 suorakulmiossa . Vuosina 1973-74. Eedenin puutarhat rakennettiin suorakulmioihin 6 × 122 ja 6 × 117 [6] [7] [8] . Joulukuussa 2011 löydettiin Eedenin puutarha, joka koostuu 56 elävästä solusta ja sopii 10 × 10 neliöön; todettiin myös, että Eedenin puutarhoja ei ole suorakulmioissa, jotka ovat pienempiä kuin 6 × 6 [9] .

Garden of Eden -lause

Soluautomaatin kahta äärellistä konfiguraatiota kutsutaan kaksosiksi , jos niiden evoluutio seuraavasta sukupolvesta alkaen osuu täysin yhteen. Soluautomaattia kutsutaan injektioksi , jos tässä automaatissa ei ole kaksosia. Soluautomaatin sanotaan olevan surjektiivinen silloin ja vain, jos jokaisella kokoonpanolla on vanhempi, toisin sanoen, jos Eedenin puutarhoja ei ole. Automaattia, joka on sekä injektiivinen että surjektiivinen, kutsutaan reversiibeliksi soluautomaatiksi .  

Eedenin puutarhan lauseessa sanotaan, että soluautomaatti euklidisessa  universumissa on paikallisesti injektiivinen, jos ja vain jos se on surjektiivinen. Toisin sanoen lause sanoo, että Eedenin puutarhat ovat olemassa vain niissä automaateissa, joissa on kaksoset.

Lause pätee "elämään", koska on helppo löytää kaksi erilaista konfiguraatiota, jotka kehittyvät seuraavassa sukupolvessa samaksi konfiguraatioksi. "Kuollut universumi" ja yksinäinen elävä solu "kuolleessa universumissa" kehittyvät samaan muotoon, jonka kaikki solut ovat kuolleita. Siksi "Elämässä" on Eedenin puutarhoja [6] [7] [8] .

Eedenin puutarha -lauseen esitti Edward Moore ja Moore ja John Myhill todistivat [10] [11] [8] .

Aiheeseen liittyviä kysymyksiä

Vielä ei tiedetä, onko olemassa kokoonpanoa, jolla on "isä" mutta ei "isoisä" [12] [13] [14] .

Vaikka missä tahansa Life-kokoonpanossa on vain yksi lapsi, päinvastoin ei pidä paikkaansa. Tietyllä kokoonpanolla voi olla kaksi tai useampi "isä". Siksi Eedenin puutarhojen löytäminen on niin vaikeaa: tietokoneen on tutkittava kaikki mahdolliset isät joka askeleella "menneisyyteen". <...> Muuten, se tosiasia, että Eedenin puutarhan "pojalla" voi olla useampi kuin yksi "isä", sai Conwayn tarjoamaan 50 dollarin palkinnon ensimmäiselle henkilölle, joka löytää kokoonpanon, jolla on "isä", mutta ei "isoisää". Tällaisen kokoonpanon olemassaolo on edelleen avoin kysymys.Martin Gardner [13]

Muistiinpanot

1. ↑ 1 2 Lifeline Vol . 3 Arkistoitu 19. maaliskuuta 2012 Wayback Machinessa (syyskuu 1971) ilmoitettiin, että Roger Banks ja Steve Ward olivat todistaneet 9x33 suorakaiteen Garden of Edenin olemassaolon ja esitelleet näytteen, jonka Banks uskoi olevan Eedenin puutarha . Julkaisussa Lifeline Vol. 4 Arkistoitu 19. maaliskuuta 2012 Wayback Machinessa (joulukuu 1971) Toimittaja Robert Wainwright raportoi, että Honeywellin ryhmä testasi itsenäisesti Banksin näytteen ja vahvisti tuloksen. Katso myös Gardner, Martin, Wheels, Life and Other Mathematical Amusements , s. 248 , < http://maa.org/pubs/focus/Gardner_GameofLife10-1970.pdf > . Haettu 11. elokuuta 2013. Arkistoitu 17. kesäkuuta 2011 Wayback Machinessa .  
2. ↑ Orpo . Elämän sanakirja. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 10. lokakuuta 2012. (määrätön)
3. ↑ Orpo . elämän sanakirja. Arkistoitu alkuperäisestä 15. lokakuuta 2014. (määrätön)
4. ↑ Hardouin-Duparc, J. (1972/73), À la recherche du paradis perdu, Publ. Matematiikka. Univ. Bordeaux Année T. 4: 51–89 
5. ↑ Hardouin-Duparc, J. (1974), Paradis terrestre dans l'automate cellulaire de Conway, Rev. Ranskan automaatti. informat. Recherche Operationnelle Ser. Rouge T. 8 (R-3): 64–71 
6. ↑ 1 2 Eedenin puutarha . Elämän sanakirja. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 10. lokakuuta 2012. (määrätön)
7. ↑ 12 Eedenin puutarha . elämän sanakirja. Arkistoitu alkuperäisestä 18. huhtikuuta 2009. (määrätön)
8. ↑ 1 2 3 Eedenin puutarha . conwaylife.com. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 1. elokuuta 2013. (määrätön)
9. ↑ Gardens of Eden (downlink) . Eedenin pienin puutarha (14. tammikuuta 2012). Haettu 20. tammikuuta 2022. Arkistoitu alkuperäisestä 24. marraskuuta 2012. (määrätön) 
10. ↑ Moore, E.F. (1962), Itsetoiston konemallit, Proc. Symp. Applied Mathematics, osa 14:17–33 
11. ↑ Myhill, J. (1963), Mooren Garden-of-Eden -lauseen käänteinen versio , Proceedings of the American Mathematical Society , osa 14: 685–686 , DOI 10.2307/2034301  . Uudelleenpainotettu julkaisussa Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, s. 204-205 
12. ↑ Eric Weisstein. Garden of Eden (linkki ei saatavilla) . Elämänpelin aarreaitta. Haettu 11. elokuuta 2013. Arkistoitu alkuperäisestä 6. tammikuuta 2009. (määrätön) 
13. ↑ 12 Martin Gardner . 22. The Game of Life, Osa III // Pyörät, elämä ja muut matemaattiset huvitukset  (englanniksi) . - W. H. Freeman and Company, 1983.
14. ↑ Lifeline Volume 6 . conwaylife.com. Käyttöpäivä: 16. lokakuuta 2015. Arkistoitu alkuperäisestä 10. joulukuuta 2015. (määrätön)

Kirjallisuus

• Margenstern, Maurice (2009), Tietoja Eedenin puutarhan teoreemoista soluautomaateille hyperbolisessa tasossa , 15. kansainvälinen työpaja soluautomaateista ja diskreetistä kompleksisista järjestelmistä , voi. 252, Electronic Notes in Theoretical Computer Science, s. 93–102 , DOI 10.1016/j.entcs.2009.09.016 
• Moore, E. F. (1962), Itsetoiston konemallit, Proc. Symp. Soveltava matematiikka T. 14:17–33  . Uudelleenpainotettu julkaisussa Burks, Arthur W. (1970), Essays on Cellular Automata , University of Illinois Press, s. 187-203