Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Про інші значення див Едемський сад значення У клітинному автоматі Едемський сад це конфігурація яка не має попередника

Едемський сад (клітинний автомат)

Едемський сад (клітинний автомат)
Про інші значення див. Едемський сад (значення).

У клітинному автоматі Едемський сад — це конфігурація, яка не має попередника. Це може бути тільки [en] автомата, бо вона не може виникнути іншим способом. Джон Тьюкі назвав ці конфігурації на честь Едемського саду в Авраамічних релігіях, який був створений нізвідки.

image
Едемський сад в грі «Життя» Конвея, відкритий Р. Банком в 1971 році. Клітини поза зображенням всі мертві (білі).
image
Сирота в «Житті», знайдена Ахімом Фламенкампом. Чорні квадрати потребують живих клітин; Сині «Х» — мертвих.

Едемський сад визначається станом кожної клітини автомата (зазвичай одно- або двовимірної нескінченної квадратної решітки клітин). Проте, для будь-якого Едемського саду існує скінченний шаблон (підмножина клітин і їх станів, звана сиротою) з тією ж властивістю, що не має попередника, незалежно від того, як розміщені клітини, що залишилися. Конфігурація всього автомата являється Едемським садом тоді і тільки тоді, коли він містить сироту. Для одновимірних клітинних автоматів, сиріт і Едемських садів можна знайти ефективний алгоритм, але для вищих вимірів це нерозв'язна задача. Однак, комп'ютерні пошуки досягли успіху в пошуку цих моделей в грі «Життя», вигаданій Конвеєм.

Теорема Едемсього саду сформульована Муром і [en] стверджує, що клітинний автомат на квадратній сітці, або на замощенні будь-якого багатовимірного евклідового простору, має Едемський сад тоді, і тільки тоді, коли він має близнюків, дві кінцеві моделі, які мають однакових наступників, коли один замінюється іншим.

Визначення

Клітинний автомат визначається сіткою комірок, кінцевим набором станів, які можуть бути призначені кожній клітині, і правилом оновлення. Часто сітка клітин — це одно- або двовимірна нескінченна квадратна решітка. Правило оновлення визначає наступний стан кожної клітинки як функцію поточного стану та поточних станів деяких інших сусідніх комірок (сусіди клітини). Сусіди — це довільний кінцевий набір клітин, але кожні дві клітини повинні мати сусідів у однакових позиціях і всі клітини повинні використовувати одне і те ж правило оновлення. Конфігурація автомата — це присвоювання стану кожній клітині.

Наступником конфігурації є інша конфігурація, яка формується одночасно з використанням правила оновлення для кожної комірки.Перехідною функцією автомата є функція, яка перетворює кожну конфігурацію на її наступника. Якщо наступник конфігурації X є конфігурацією Y, то X є попередником Y. Конфігурація може мати нуль, один або більше попередників, але завжди має рівно одного наступника. Едемський сад визначається як конфігурація з нулем попередників.

Шаблони для даного клітинного автомата складаються з кінцевого набору клітин разом зі станом для кожної з цих клітин. Конфігурація містить шаблон, коли стани комірок у шаблоні такі ж, як стани тих самих комірок в конфігурації. Визначення попередників конфігурацій може бути розширено до попередників шаблонів: попередник шаблону — це лише конфігурація, чий наступник містить шаблон. Отже, сирота є шаблоном без попередника.

Пошук Едемського саду

Для одновимірних клітинних автоматів, сади Едему можна знайти ефективним алгоритмом, час роботи якого поліноміальний відносно розмірів таблиці автомата. Для вищих розмірностей, визначення того, чи існує Едемський сад, є нерозв'язною проблемою, а це означає, що не існує алгоритму, який би гарантував скінченність пошуків і правильну відповідь. Однак, у багатьох випадках можна використовувати теорему Едемського саду (наведену нижче), щоб зробити висновок, що рішення існує, а потім використовувати алгоритм пошуку, щоб знайти його.

Комп'ютерна програма могла б шукати шаблони сиріт, систематично вивчаючи всі кінцеві моделі, у порядку збільшення розмірів, і перевіряючи всі можливі попередники для кожного шаблону, щоб визначити, чи є він насправді сиротою. Однак, кількість шаблонів, які повинні бути створені, щоб знайти Едемський сад таким чином, є експоненціальним відносно площі шаблона. Ця величезна кількість шаблонів зробить цей тип пошуку грубої сили надто дорогим, навіть для відносно невеликих розмірів шаблонів.

Жан Хардуїн-Дупарк (1972—1973, 1974) вперше створив більш ефективний обчислювальний підхід до пошуку сиріт. Його метод ґрунтується на теорії формальних мов і займає кількість часу, експоненційну ширині шаблону, а не його площі. Ключова ідея полягає в тому, що для будь-якої фіксованої ширини можна побудувати недетермінований скінченний автомат, який розпізнає шаблони заданої ширини, які мають попередника. Вхідні символи цієї машини описують кожен рядок шаблону, а стани машини описують найближчі рядки можливих попередників для частини шаблону, яка була введена раніше. З цієї машини можна побудувати інший кінцевий автомат, який розпізнає комплементарний набір (шаблони, які не мають попередників), шляхом перетворення недетермінованого скінченного автомата в детермінований, використовуючи детермінізацію, а потім доповнюючи його набір приймальних станів. Як тільки машина, що розпізнає комплементарний набір, буде побудована, можна перевірити, чи мова, яку вона розпізнає, порожня, шукаючи шлях від початкового стану до стану приймання. Цей шлях, якщо він існує, дає опис рядка за рядком.

Мартін Гарднер посилається на Алві Рея Сміта із зауваженням, що теорема Едемського саду стосується гри «Життя» Конвея, доводить існування Едемських садів для цього правила. Перший явний Едемський сад в «Житті», з його живими клітинами в прямокутнику 9 × 33, був ідентифікований як кандидат Едемського саду Роджером Бенксом в 1971 році, а потім перевірений пошуком попередників з вертанням. Згодом, Хардуїн-Дюпарк використовував свій формальний мовний підхід, щоб знайти найменш вузькі Едемські сади в грі «Життя», причому обмежувальне поле для їхніх живих клітин було всього шість клітин.

Найменша відома сирота в грі «Життя» (за площею її обмежувальної рамки) була знайдена Стівеном Екером у квітні 2016 року. Вона має 57 живих клітин і вміщується в прямокутник 8х12.

Існування сиріт

За визначенням, кожна сирота належить до Едемського саду: розширюючи сироту на конфігурацію всього автомата, вибираючи стан для кожної комірки, що залишилась, довільно, завжди отримаємо Едемський сад. Але зворотне також вірно: кожен Едемський сад містить принаймні одну сироту. Щоб довести це, Карі використовує топологічний аргумент, заснований на теоремі Кертіса — Хедлунда — Ліндона, згідно з якою перехідні функції клітинних автоматів є точно трансляційно-інваріантними неперервними функціями на просторі конфігурацій. Тут неперервність визначається присвоєнням дискретної топології кінцевому набору станів автомата, а потім, використовуючи добуток топологічних просторів з одним членом у добутку для кожної клітини автомата для побудови топологічного простору, точки якого є конфігураціями автомата. За теоремою Тихонова — це компактний простір.

Для кожного кінцевого шаблону, набір конфігурацій, що містять шаблон, є відкритою множиною у цій топології, званий циліндром. Циліндри є базою топології. Як зауважує Карі, множина конфігурацій, які не є садами Едему, є лише зображенням перехідної функції, тому за допомогою [en] для компактних просторів вона є замкнутою множиною. Набір садів Едему, відповідно, є відкритим набором. Оскільки він відкритий і циліндри утворюють основу, набір садів Едему можна представити як об'єднання циліндрів. Кожен з циліндрів у цьому об'єднанні складається тільки з садів Едему, тому шаблон, який визначає кожен циліндр, повинен бути сиротою. Якщо набір садів Едему не є порожнім, у цьому союзі має бути принаймні один циліндр, тому має бути принаймні один сирота. І будь-який конкретний Едемський сад повинен належати одному з цих циліндрів, і тому повинен містити сироту для цього циліндра.

Теорема Едемського саду

У клітинному автоматі дві кінцеві моделі є близнюками, якщо можна замінити іншу, де б вона не з'явилася, без зміни майбутніх конфігурацій. Стільниковий автомат є ін'єктивним, якщо кожна пара різних конфігурацій автомата залишається різною після кроку автомата, а локально ін'єктивним, якщо він не має близнюків. Він є сюр'ективним тоді і тільки тоді, коли кожна конфігурація має попередника; тобто, тоді і тільки тоді, коли у нього немає конфігурації Саду Едему. Автомат, що є одночасно ін'єктивним і сюр'ективним, називається [en].

Теорема Едемського саду, завдяки Едварду Ф. Муру (1962) і [en] (1963), стверджує, що клітинний автомат в евклідовому просторі локально ін'єктивний тоді і тільки тоді, коли він є сюр'ективним. Іншими словами, він стверджує, що клітинний автомат має Едемський сад, тоді і тільки тоді, коли він має близнюків. Більш сильно, кожен нелокально-ін'єкційний клітинний автомат має шаблон-сироту. Негайним наслідком є ​​те, що ін'єктивний клітинний автомат повинен бути сюр'ективним. Мур довів один напрямок теореми, що автомати з близнюками мають сиріт; Майхілл довів зворотне, що автомат з сиротою також має близнюків.

У випадку гри Конвея, близнят набагато легше знайти, ніж сиріт. Наприклад, блок з п'ять на п'ять мертвих клітин і блок з п'ять на п'ять з живою центральною клітиною, а інші мертві — близнюки: стан центральної клітини не може впливати на більш пізні конфігурації шаблону. Таким чином, в даному випадку теорема Едемського саду дозволяє продемонструвати існування Едемського саду набагато легше, ніж знайти явний шаблон-сироту.

У художній літературі

У романі Грега Ігена «Місто перестановок» головний герой використовує конфігурацію Едемського саду, щоб створити ситуацію, в якій копія самого себе може довести, що він живе в рамках моделювання. Раніше всі його симульовані копії опинилися в якомусь варіанті «реального світу»; хоча у них були спогади про моделювання копій, що живуть у симуляції, завжди було простіше пояснення того, як ці спогади з'явилися. Конфігурація Едемського саду, однак, не може відбутися, за винятком інтелектуального моделювання. Релігійні паралелі є навмисними.

Примітки

  1. In Lifeline Vol. 3 [ 19 березня 2012 у Wayback Machine.] (September 1971), editor Robert T. Wainwright announced that Roger Banks and Steve Ward had proven the existence of a Garden of Eden whose live cells fit into a 9 × 33 rectangle, and presented a configuration believed by Banks to be a Garden of Eden. In Lifeline Vol. 4 [ 19 березня 2012 у Wayback Machine.] (December 1971), Wainwright reported that a group at Honeywell using software by had verified Banks' configuration to be a Garden of Eden. See also Gardner, (1983).
  2. Moore, Edward F. (1962). Machines models of self-reproduction. Mathematical Problems in the Biological Sciences. с. 17—33. doi:10.1090/psapm/014/9961. ISSN 2324-7088. Процитовано 25 березня 2019.
  3. Kari, Jarkko J. (2012). Rozenberg, Grzegorz; Bäck, Thomas; Kok, Joost N. (ред.). Basic Concepts of Cellular Automata. Handbook of Natural Computing (англ.). Berlin, Heidelberg: Springer Berlin Heidelberg. с. 3—24. doi:10.1007/978-3-540-92910-9_1. ISBN .
  4. Toffoli, Tommaso; Margolus, Norman (1990), «Invertible cellular automata: a review», Physica D: Nonlinear Phenomena, 45 (1–3): 229—253, doi:10.1016/0167-2789(90)90185-R, MR 1094877
  5. Kari, Jarkko; Lukkarila, Ville (2009). Some Undecidable Dynamical Properties for One-Dimensional Reversible Cellular Automata. Algorithmic Bioprocesses. Berlin, Heidelberg: Springer Berlin Heidelberg. с. 639—660. ISBN .
  6. Figure A.1.2. Large families even with two breadwinners would not necessary escape poverty. dx.doi.org. Процитовано 25 березня 2019.
  7. Wax, Murray (1957). Les Pawnees à la recherche du Paradis Perdu. Archives de sciences sociales des religions. Т. 4, № 1. с. 113—122. doi:10.3406/assr.1957.1681. ISSN 0003-9659. Процитовано 25 березня 2019.
  8. Hardouin-Duparc, J. (1974). Paradis terrestre dans l'automate cellulaire de Conway. Revue française d'automatique informatique recherche opérationnelle. Informatique théorique. Т. 8, № R3. с. 63—71. doi:10.1051/ita/197408r300631. ISSN 0397-9326. Процитовано 25 березня 2019.
  9. Flammenkamp, Achim (1 травня 1991). New sociable numbers. Mathematics of Computation. Т. 56, № 194. с. 871—871. doi:10.1090/s0025-5718-1991-1052094-3. ISSN 0025-5718. Процитовано 25 березня 2019.
  10. DID IT WORK?. The Orphans of Byzantium. Catholic University of America Press. с. 247—282. ISBN .
  11. Hedlund, G. A. (1969-12). Endomorphisms and automorphisms of the shift dynamical system. Mathematical Systems Theory (англ.). Т. 3, № 4. с. 320—375. doi:10.1007/BF01691062. ISSN 0025-5661. Процитовано 25 березня 2019.
  12. Myhill, John (1963-8). . Proceedings of the American Mathematical Society. Т. 14, № 4. с. 685. doi:10.2307/2034301. Архів оригіналу за 27 березня 2019. Процитовано 25 березня 2019.
  13. Klarner, David A.; Gardner, Martin (1986-04). Wheels, Life and Other Mathematical Amusements. The American Mathematical Monthly. Т. 93, № 4. с. 321. doi:10.2307/2323703. ISSN 0002-9890. Процитовано 25 березня 2019.
  14. 1954-, Blackford, Russell,; 1948-, McMullen, Sean, (1999). Strange constellations : a history of Australian science fiction. Westport, Conn.: Greenwood Press. ISBN . OCLC 39922727.
  15. 1943-, Hayles, Katherine, (2005). My mother was a computer : digital subjects and literary texts. Chicago: University of Chicago Press. ISBN . OCLC 659564155.

Посилання

  • Garden of Eden [ 13 вересня 2014 у Wayback Machine.], LifeWiki
  • Garden of Eden (Eric Weisstein's Treasure Trove of The Game of Life) [ 6 січня 2009 у Wayback Machine.]

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Pro inshi znachennya div Edemskij sad znachennya U klitinnomu avtomati Edemskij sad ce konfiguraciya yaka ne maye poperednika Ce mozhe buti tilki en avtomata bo vona ne mozhe viniknuti inshim sposobom Dzhon Tyuki nazvav ci konfiguraciyi na chest Edemskogo sadu v Avraamichnih religiyah yakij buv stvorenij nizvidki Edemskij sad v gri Zhittya Konveya vidkritij R Bankom v 1971 roci Klitini poza zobrazhennyam vsi mertvi bili Sirota v Zhitti znajdena Ahimom Flamenkampom Chorni kvadrati potrebuyut zhivih klitin Sini H mertvih Edemskij sad viznachayetsya stanom kozhnoyi klitini avtomata zazvichaj odno abo dvovimirnoyi neskinchennoyi kvadratnoyi reshitki klitin Prote dlya bud yakogo Edemskogo sadu isnuye skinchennij shablon pidmnozhina klitin i yih staniv zvana sirotoyu z tiyeyu zh vlastivistyu sho ne maye poperednika nezalezhno vid togo yak rozmisheni klitini sho zalishilisya Konfiguraciya vsogo avtomata yavlyayetsya Edemskim sadom todi i tilki todi koli vin mistit sirotu Dlya odnovimirnih klitinnih avtomativ sirit i Edemskih sadiv mozhna znajti efektivnij algoritm ale dlya vishih vimiriv ce nerozv yazna zadacha Odnak komp yuterni poshuki dosyagli uspihu v poshuku cih modelej v gri Zhittya vigadanij Konveyem Teorema Edemsogo sadu sformulovana Murom i en stverdzhuye sho klitinnij avtomat na kvadratnij sitci abo na zamoshenni bud yakogo bagatovimirnogo evklidovogo prostoru maye Edemskij sad todi i tilki todi koli vin maye bliznyukiv dvi kincevi modeli yaki mayut odnakovih nastupnikiv koli odin zaminyuyetsya inshim ViznachennyaKlitinnij avtomat viznachayetsya sitkoyu komirok kincevim naborom staniv yaki mozhut buti priznacheni kozhnij klitini i pravilom onovlennya Chasto sitka klitin ce odno abo dvovimirna neskinchenna kvadratna reshitka Pravilo onovlennya viznachaye nastupnij stan kozhnoyi klitinki yak funkciyu potochnogo stanu ta potochnih staniv deyakih inshih susidnih komirok susidi klitini Susidi ce dovilnij kincevij nabir klitin ale kozhni dvi klitini povinni mati susidiv u odnakovih poziciyah i vsi klitini povinni vikoristovuvati odne i te zh pravilo onovlennya Konfiguraciya avtomata ce prisvoyuvannya stanu kozhnij klitini Nastupnikom konfiguraciyi ye insha konfiguraciya yaka formuyetsya odnochasno z vikoristannyam pravila onovlennya dlya kozhnoyi komirki Perehidnoyu funkciyeyu avtomata ye funkciya yaka peretvoryuye kozhnu konfiguraciyu na yiyi nastupnika Yaksho nastupnik konfiguraciyi X ye konfiguraciyeyu Y to X ye poperednikom Y Konfiguraciya mozhe mati nul odin abo bilshe poperednikiv ale zavzhdi maye rivno odnogo nastupnika Edemskij sad viznachayetsya yak konfiguraciya z nulem poperednikiv Shabloni dlya danogo klitinnogo avtomata skladayutsya z kincevogo naboru klitin razom zi stanom dlya kozhnoyi z cih klitin Konfiguraciya mistit shablon koli stani komirok u shabloni taki zh yak stani tih samih komirok v konfiguraciyi Viznachennya poperednikiv konfiguracij mozhe buti rozshireno do poperednikiv shabloniv poperednik shablonu ce lishe konfiguraciya chij nastupnik mistit shablon Otzhe sirota ye shablonom bez poperednika Poshuk Edemskogo saduDlya odnovimirnih klitinnih avtomativ sadi Edemu mozhna znajti efektivnim algoritmom chas roboti yakogo polinomialnij vidnosno rozmiriv tablici avtomata Dlya vishih rozmirnostej viznachennya togo chi isnuye Edemskij sad ye nerozv yaznoyu problemoyu a ce oznachaye sho ne isnuye algoritmu yakij bi garantuvav skinchennist poshukiv i pravilnu vidpovid Odnak u bagatoh vipadkah mozhna vikoristovuvati teoremu Edemskogo sadu navedenu nizhche shob zrobiti visnovok sho rishennya isnuye a potim vikoristovuvati algoritm poshuku shob znajti jogo Komp yuterna programa mogla b shukati shabloni sirit sistematichno vivchayuchi vsi kincevi modeli u poryadku zbilshennya rozmiriv i pereviryayuchi vsi mozhlivi poperedniki dlya kozhnogo shablonu shob viznachiti chi ye vin naspravdi sirotoyu Odnak kilkist shabloniv yaki povinni buti stvoreni shob znajti Edemskij sad takim chinom ye eksponencialnim vidnosno ploshi shablona Cya velichezna kilkist shabloniv zrobit cej tip poshuku gruboyi sili nadto dorogim navit dlya vidnosno nevelikih rozmiriv shabloniv Zhan Harduyin Dupark 1972 1973 1974 vpershe stvoriv bilsh efektivnij obchislyuvalnij pidhid do poshuku sirit Jogo metod gruntuyetsya na teoriyi formalnih mov i zajmaye kilkist chasu eksponencijnu shirini shablonu a ne jogo ploshi Klyuchova ideya polyagaye v tomu sho dlya bud yakoyi fiksovanoyi shirini mozhna pobuduvati nedeterminovanij skinchennij avtomat yakij rozpiznaye shabloni zadanoyi shirini yaki mayut poperednika Vhidni simvoli ciyeyi mashini opisuyut kozhen ryadok shablonu a stani mashini opisuyut najblizhchi ryadki mozhlivih poperednikiv dlya chastini shablonu yaka bula vvedena ranishe Z ciyeyi mashini mozhna pobuduvati inshij kincevij avtomat yakij rozpiznaye komplementarnij nabir shabloni yaki ne mayut poperednikiv shlyahom peretvorennya nedeterminovanogo skinchennogo avtomata v determinovanij vikoristovuyuchi determinizaciyu a potim dopovnyuyuchi jogo nabir prijmalnih staniv Yak tilki mashina sho rozpiznaye komplementarnij nabir bude pobudovana mozhna pereviriti chi mova yaku vona rozpiznaye porozhnya shukayuchi shlyah vid pochatkovogo stanu do stanu prijmannya Cej shlyah yaksho vin isnuye daye opis ryadka za ryadkom Martin Gardner posilayetsya na Alvi Reya Smita iz zauvazhennyam sho teorema Edemskogo sadu stosuyetsya gri Zhittya Konveya dovodit isnuvannya Edemskih sadiv dlya cogo pravila Pershij yavnij Edemskij sad v Zhitti z jogo zhivimi klitinami v pryamokutniku 9 33 buv identifikovanij yak kandidat Edemskogo sadu Rodzherom Benksom v 1971 roci a potim perevirenij poshukom poperednikiv z vertannyam Zgodom Harduyin Dyupark vikoristovuvav svij formalnij movnij pidhid shob znajti najmensh vuzki Edemski sadi v gri Zhittya prichomu obmezhuvalne pole dlya yihnih zhivih klitin bulo vsogo shist klitin Najmensha vidoma sirota v gri Zhittya za plosheyu yiyi obmezhuvalnoyi ramki bula znajdena Stivenom Ekerom u kvitni 2016 roku Vona maye 57 zhivih klitin i vmishuyetsya v pryamokutnik 8h12 Isnuvannya siritZa viznachennyam kozhna sirota nalezhit do Edemskogo sadu rozshiryuyuchi sirotu na konfiguraciyu vsogo avtomata vibirayuchi stan dlya kozhnoyi komirki sho zalishilas dovilno zavzhdi otrimayemo Edemskij sad Ale zvorotne takozh virno kozhen Edemskij sad mistit prinajmni odnu sirotu Shob dovesti ce Kari vikoristovuye topologichnij argument zasnovanij na teoremi Kertisa Hedlunda Lindona zgidno z yakoyu perehidni funkciyi klitinnih avtomativ ye tochno translyacijno invariantnimi neperervnimi funkciyami na prostori konfiguracij Tut neperervnist viznachayetsya prisvoyennyam diskretnoyi topologiyi kincevomu naboru staniv avtomata a potim vikoristovuyuchi dobutok topologichnih prostoriv z odnim chlenom u dobutku dlya kozhnoyi klitini avtomata dlya pobudovi topologichnogo prostoru tochki yakogo ye konfiguraciyami avtomata Za teoremoyu Tihonova ce kompaktnij prostir Dlya kozhnogo kincevogo shablonu nabir konfiguracij sho mistyat shablon ye vidkritoyu mnozhinoyu u cij topologiyi zvanij cilindrom Cilindri ye bazoyu topologiyi Yak zauvazhuye Kari mnozhina konfiguracij yaki ne ye sadami Edemu ye lishe zobrazhennyam perehidnoyi funkciyi tomu za dopomogoyu en dlya kompaktnih prostoriv vona ye zamknutoyu mnozhinoyu Nabir sadiv Edemu vidpovidno ye vidkritim naborom Oskilki vin vidkritij i cilindri utvoryuyut osnovu nabir sadiv Edemu mozhna predstaviti yak ob yednannya cilindriv Kozhen z cilindriv u comu ob yednanni skladayetsya tilki z sadiv Edemu tomu shablon yakij viznachaye kozhen cilindr povinen buti sirotoyu Yaksho nabir sadiv Edemu ne ye porozhnim u comu soyuzi maye buti prinajmni odin cilindr tomu maye buti prinajmni odin sirota I bud yakij konkretnij Edemskij sad povinen nalezhati odnomu z cih cilindriv i tomu povinen mistiti sirotu dlya cogo cilindra Teorema Edemskogo saduU klitinnomu avtomati dvi kincevi modeli ye bliznyukami yaksho mozhna zaminiti inshu de b vona ne z yavilasya bez zmini majbutnih konfiguracij Stilnikovij avtomat ye in yektivnim yaksho kozhna para riznih konfiguracij avtomata zalishayetsya riznoyu pislya kroku avtomata a lokalno in yektivnim yaksho vin ne maye bliznyukiv Vin ye syur ektivnim todi i tilki todi koli kozhna konfiguraciya maye poperednika tobto todi i tilki todi koli u nogo nemaye konfiguraciyi Sadu Edemu Avtomat sho ye odnochasno in yektivnim i syur ektivnim nazivayetsya en Teorema Edemskogo sadu zavdyaki Edvardu F Muru 1962 i en 1963 stverdzhuye sho klitinnij avtomat v evklidovomu prostori lokalno in yektivnij todi i tilki todi koli vin ye syur ektivnim Inshimi slovami vin stverdzhuye sho klitinnij avtomat maye Edemskij sad todi i tilki todi koli vin maye bliznyukiv Bilsh silno kozhen nelokalno in yekcijnij klitinnij avtomat maye shablon sirotu Negajnim naslidkom ye te sho in yektivnij klitinnij avtomat povinen buti syur ektivnim Mur doviv odin napryamok teoremi sho avtomati z bliznyukami mayut sirit Majhill doviv zvorotne sho avtomat z sirotoyu takozh maye bliznyukiv U vipadku gri Konveya bliznyat nabagato legshe znajti nizh sirit Napriklad blok z p yat na p yat mertvih klitin i blok z p yat na p yat z zhivoyu centralnoyu klitinoyu a inshi mertvi bliznyuki stan centralnoyi klitini ne mozhe vplivati na bilsh pizni konfiguraciyi shablonu Takim chinom v danomu vipadku teorema Edemskogo sadu dozvolyaye prodemonstruvati isnuvannya Edemskogo sadu nabagato legshe nizh znajti yavnij shablon sirotu U hudozhnij literaturiU romani Grega Igena Misto perestanovok golovnij geroj vikoristovuye konfiguraciyu Edemskogo sadu shob stvoriti situaciyu v yakij kopiya samogo sebe mozhe dovesti sho vin zhive v ramkah modelyuvannya Ranishe vsi jogo simulovani kopiyi opinilisya v yakomus varianti realnogo svitu hocha u nih buli spogadi pro modelyuvannya kopij sho zhivut u simulyaciyi zavzhdi bulo prostishe poyasnennya togo yak ci spogadi z yavilisya Konfiguraciya Edemskogo sadu odnak ne mozhe vidbutisya za vinyatkom intelektualnogo modelyuvannya Religijni paraleli ye navmisnimi PrimitkiIn Lifeline Vol 3 19 bereznya 2012 u Wayback Machine September 1971 editor Robert T Wainwright announced that Roger Banks and Steve Ward had proven the existence of a Garden of Eden whose live cells fit into a 9 33 rectangle and presented a configuration believed by Banks to be a Garden of Eden In Lifeline Vol 4 19 bereznya 2012 u Wayback Machine December 1971 Wainwright reported that a group at Honeywell using software by had verified Banks configuration to be a Garden of Eden See also Gardner 1983 Moore Edward F 1962 Machines models of self reproduction Mathematical Problems in the Biological Sciences s 17 33 doi 10 1090 psapm 014 9961 ISSN 2324 7088 Procitovano 25 bereznya 2019 Kari Jarkko J 2012 Rozenberg Grzegorz Back Thomas Kok Joost N red Basic Concepts of Cellular Automata Handbook of Natural Computing angl Berlin Heidelberg Springer Berlin Heidelberg s 3 24 doi 10 1007 978 3 540 92910 9 1 ISBN 9783540929093 Toffoli Tommaso Margolus Norman 1990 Invertible cellular automata a review Physica D Nonlinear Phenomena 45 1 3 229 253 doi 10 1016 0167 2789 90 90185 R MR 1094877 Kari Jarkko Lukkarila Ville 2009 Some Undecidable Dynamical Properties for One Dimensional Reversible Cellular Automata Algorithmic Bioprocesses Berlin Heidelberg Springer Berlin Heidelberg s 639 660 ISBN 9783540888680 Figure A 1 2 Large families even with two breadwinners would not necessary escape poverty dx doi org Procitovano 25 bereznya 2019 Wax Murray 1957 Les Pawnees a la recherche du Paradis Perdu Archives de sciences sociales des religions T 4 1 s 113 122 doi 10 3406 assr 1957 1681 ISSN 0003 9659 Procitovano 25 bereznya 2019 Hardouin Duparc J 1974 Paradis terrestre dans l automate cellulaire de Conway Revue francaise d automatique informatique recherche operationnelle Informatique theorique T 8 R3 s 63 71 doi 10 1051 ita 197408r300631 ISSN 0397 9326 Procitovano 25 bereznya 2019 Flammenkamp Achim 1 travnya 1991 New sociable numbers Mathematics of Computation T 56 194 s 871 871 doi 10 1090 s0025 5718 1991 1052094 3 ISSN 0025 5718 Procitovano 25 bereznya 2019 DID IT WORK The Orphans of Byzantium Catholic University of America Press s 247 282 ISBN 9780813220796 Hedlund G A 1969 12 Endomorphisms and automorphisms of the shift dynamical system Mathematical Systems Theory angl T 3 4 s 320 375 doi 10 1007 BF01691062 ISSN 0025 5661 Procitovano 25 bereznya 2019 Myhill John 1963 8 Proceedings of the American Mathematical Society T 14 4 s 685 doi 10 2307 2034301 Arhiv originalu za 27 bereznya 2019 Procitovano 25 bereznya 2019 Klarner David A Gardner Martin 1986 04 Wheels Life and Other Mathematical Amusements The American Mathematical Monthly T 93 4 s 321 doi 10 2307 2323703 ISSN 0002 9890 Procitovano 25 bereznya 2019 1954 Blackford Russell 1948 McMullen Sean 1999 Strange constellations a history of Australian science fiction Westport Conn Greenwood Press ISBN 0313251126 OCLC 39922727 1943 Hayles Katherine 2005 My mother was a computer digital subjects and literary texts Chicago University of Chicago Press ISBN 9780226321493 OCLC 659564155 PosilannyaGarden of Eden 13 veresnya 2014 u Wayback Machine LifeWiki Garden of Eden Eric Weisstein s Treasure Trove of The Game of Life 6 sichnya 2009 u Wayback Machine

Дата публікації:
Топ