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

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

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

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

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

Визначення[ред. | ред. код]

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

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

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

Пошук Едемського саду[ред. | ред. код]

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

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

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

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

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

Існування сиріт[ред. | ред. код]

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

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

Теорема Едемського саду[ред. | ред. код]

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

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

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

У художній літературі[ред. | ред. код]

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

Примітки[ред. | ред. код]

  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 Don Woods had verified Banks' configuration to be a Garden of Eden. See also Помилка скрипту: Функції «harvard_core» не існує..
  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 9783540929093.
  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 9783540888680.
  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 9780813220796.
  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). Shorter Note: The Converse of Moore's Garden-of-Eden Theorem. 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 0313251126. OCLC 39922727.
  15. ↑ 1943-, Hayles, Katherine, (2005). My mother was a computer : digital subjects and literary texts. Chicago: University of Chicago Press. ISBN 9780226321493. OCLC 659564155.

Посилання[ред. | ред. код]

Класи конфігурацій
Конфігурації
Терміни
Інші КА на
двомірній решітці
Одномірні КА
ПЗ і алгоритми
Дослідники КА
Отримано з https://uk.wikipedia.org/w/index.php?title=Едемський_сад_(клітинний_автомат)&oldid=42272315