Эдемский сад (клеточный автомат) - Garden of Eden (cellular automaton)

Райский сад в Игра жизни Конвея, открытый Р. Бэнксом в 1971 г.[1] Все клетки за пределами изображения мертвы (белые).
Сирота в жизни найдена Ахимом Фламменкампом. Черные квадраты - обязательные живые клетки; синие крестики - это мертвые клетки.

В клеточный автомат, а Эдемский сад это конфигурация, не имеющая предшественников. Это может быть начальная конфигурация автомата, но иначе возникнуть не может.Джон Тьюки назвал эти конфигурации в честь Эдемский сад в Авраамические религии, который был создан из ниоткуда.[2]

Райский сад определяется состоянием каждой клетки в автомате (обычно одно- или двумерный бесконечный квадратная решетка ячеек). Однако для любого Эдемского сада существует конечный образец (подмножество ячеек и их состояний, называемое сирота) с тем же свойством не иметь предшественника, независимо от того, как заполняются оставшиеся ячейки. Конфигурация всего автомата является райским садом тогда и только тогда, когда он содержит сироту. для одномерных клеточных автоматов, сирот и садов. Эдема можно найти с помощью эффективного алгоритма, но для более высоких размеры это неразрешимая проблема. Тем не менее компьютерный поиск позволил обнаружить эти закономерности в Игра жизни Конвея.

Теорема Эдемского сада Мур и Myhill утверждает, что клеточный автомат на квадратной сетке или на мозаике любой более высокой размерности Евклидово пространство, имеет Эдемский сад тогда и только тогда, когда в нем есть двойняшки, два конечных шаблона, у которых одни и те же преемники всякий раз, когда один заменяется другим.

Определения

А клеточный автомат определяется сеткой ячеек, конечным набором состояний, которые могут быть назначены каждой ячейке, и правилом обновления. Часто сетка ячеек является одно- или двумерной бесконечной квадратная решетка. Правило обновления определяет следующее состояние каждой ячейки в зависимости от ее текущего состояния и текущих состояний некоторых других соседних ячеек ( район Соседство может быть произвольным конечным набором ячеек, но каждые две ячейки должны иметь соседей в одинаковых относительных положениях, и все ячейки должны использовать одно и то же правило обновления. конфигурация автомата - это присвоение состояния каждой ячейке.[3]

В преемник конфигурации - это другая конфигурация, сформированная путем применения правила обновления одновременно к каждой ячейке.[4]В функция перехода автомата - это функция, которая отображает каждую конфигурацию на ее преемника.[3]Если наследник конфигурации Икс это конфигурация Y, тогда Икс это предшественник из Y.Конфигурация может иметь ноль, один или несколько предшественников, но всегда имеет только один преемник.[4]Эдемский сад определяется как конфигурация без предшественников.[5]

А шаблондля данного клеточного автомата состоит из конечного набора ячеек вместе с состоянием каждой из этих ячеек.[6] Конфигурация содержит шаблон, когда состояния ячеек в шаблоне такие же, как состояния тех же ячеек в конфигурации (без преобразования ячеек перед их сопоставлением). Определение предшественников конфигураций может быть расширено до предшественников шаблонов: предшественник шаблона - это просто конфигурация, преемник которой содержит шаблон. Таким образом, сирота - это шаблон, у которого нет предшественника.[6]

В поисках Эдемского сада

Для одномерных клеточных автоматов райские сады можно найти с помощью эффективного алгоритм время работы которой полиномиально от размера таблицы правил автомата. Для высших измерений определение того, существует ли Эдемский сад, является неразрешимая проблема, что означает, что не существует алгоритма, который гарантированно завершит работу и выдаст правильный ответ.[7] Тем не менее, во многих случаях можно использовать теорему Эдемского сада (ниже), чтобы сделать вывод о существовании решения, а затем использовать алгоритм поиска, чтобы найти его.

Компьютерная программа могла бы искать сиротские паттерны, систематически исследуя все конечные паттерны в порядке увеличения размера и проверяя всех возможных предшественников для каждого паттерна, чтобы определить, действительно ли это сиротский паттерн. Однако количество паттернов, которые необходимо было бы создать, чтобы найти райский сад таким образом, экспоненциально в области паттерна. Такое огромное количество шаблонов сделало бы этот тип перебор непомерно дорого даже для выкроек сравнительно небольших размеров.[8]

Жан Ардуэн-Дюпарк (1972–73, 1974 ) впервые применил более эффективный вычислительный подход для поиска шаблонов-сирот. Его метод основан на теории формальные языки, и занимает время, которое экспоненциально зависит от ширины узора, а не от его площади. Ключевая идея заключается в том, что для любой фиксированной ширины можно построить недетерминированный конечный автомат который распознает шаблоны заданной ширины, у которых есть предшественники. Входные символы в эту машину описывают каждую строку шаблона, а состояния машины описывают соседние строки возможных предшественников для той части шаблона, которая была введена до сих пор. Из этой машины можно построить другой конечный автомат, который распознает дополнительный набор, шаблоны, не имеющие предшественников, путем преобразования недетерминированного конечного автомата в детерминированный конечный автомат используя конструкция электростанции, а затем дополняя свой набор принимающих состояний. После того, как машина, распознающая дополнительный набор, создана, можно проверить, является ли распознаваемый ею язык пустым, путем поиска пути от начального состояния к принимающему состоянию. Этот путь, если он существует, дает построчное описание паттерна-сироты.[9]

Мартин Гарднер кредиты Элви Рэй Смит с замечанием, что теорема Эдемского сада применима к Игра жизни Конвея, и доказывает существование Эдемских садов для этого правила. Первый явный райский сад в жизни, с его живыми клетками, подходящими для 9 × 33 прямоугольник, был определен Роджером Бэнксом в качестве кандидата на роль Эдемского сада в 1971 году, а затем подтвержден исчерпывающим поиск с возвратом для предшественников.[1]Впоследствии Хардуэн-Дюпарк использовал свой формальный языковой подход, чтобы найти как можно более узкие сады Эдема в «Игре жизни» Конвея. Ограничительная рамка поскольку их живые клетки имеют ширину всего шесть клеток.[10]

Самый маленький из известных паттернов-сирот в «Игре жизни» Конвея (по площади ограничивающего прямоугольника) был обнаружен Стивеном Экером в апреле 2016 года. Он состоит из 57 живых клеток и умещается в прямоугольник 8 × 12.[11]

Наличие детей-сирот

По определению, каждый сирота принадлежит Эдемскому саду: расширение сироты до конфигурации всего автомата путем произвольного выбора состояния для каждой оставшейся ячейки всегда приведет к Эдемскому саду. Но верно и обратное: в каждом Эдемском саду есть хотя бы одна сирота.[12][13]Чтобы доказать это, Кари[12] использует топологический аргумент, основанный на Теорема Кертиса – Хедлунда – Линдона. согласно которому переходные функции клеточных автоматов являются в точности трансляционно-инвариантными. непрерывные функции на пространстве конфигураций.[14] Здесь непрерывность определяется назначением дискретная топология в конечный набор состояний автомата, а затем с помощью топология продукта с одним членом в произведении для каждой ячейки в автомате, чтобы построить топологическое пространство точками которых являются конфигурации автомата. К Теорема Тихонова это компактное пространство.[12]

Для каждого конечного шаблона набор конфигураций, содержащих шаблон, является открытый набор в этой топологии, называемой цилиндр.[6] Цилиндры образуют основа Как замечает Кари, совокупность конфигураций, не являющихся Садами Эдема, - это просто образ функции перехода, поэтому лемма о замкнутом отображении для компактных пространств это закрытый набор. Набор "Садов Эдема", соответственно, является открытым. Поскольку он открыт и цилиндры образуют основу, набор Эдемских садов можно представить как объединение цилиндров, каждый из которых состоит только из Эдемских садов, поэтому образец, определяющий каждый цилиндр, должен быть сирота. Если набор "Садов Эдема" не пустой, в этом союзе должен быть хотя бы один цилиндр, поэтому должен быть хотя бы один сирота. И любой конкретный Эдемский сад должен принадлежать одному из этих цилиндров и, следовательно, содержать сироту для этого цилиндра.[12]

Теорема Эдемского сада

В клеточном автомате есть два конечных паттерна. двойняшки если один может быть заменен другим, где бы он ни появился, без изменения будущих конфигураций. Клеточный автомат - это инъективный если все пары различных конфигураций автомата остаются разными после шага автомата, и локально инъективными, если у него нет двойников. это сюръективный тогда и только тогда, когда у каждой конфигурации есть предшественник; то есть, если и только если он не имеет конфигурации Garden of Eden. Автомат, одновременно инъективный и сюръективный, называется обратимый клеточный автомат.[3]

В Теорема Эдемского сада, из-за Эдвард Ф. Мур  (1962 ) и Джон Майхилл  (1963 ), утверждает, что клеточный автомат в Евклидово пространство локально инъективен тогда и только тогда, когда он сюръективен. Другими словами, он утверждает, что у клеточного автомата есть райский сад, если и только если у него есть близнецы. Более того, каждый нелокально-инъективный клеточный автомат имеет паттерн-сироту. Непосредственное следствие состоит в том, что инъективный клеточный автомат должен быть сюръективным. Мур доказал одно направление теоремы, что у автоматов с близнецами есть сироты;[2] Майхилл доказал обратное: у автомата с сиротой тоже есть близнецы.[15]

В случае с «Игрой жизни» Конвея найти близнецов намного легче, чем сирот. Например, блок мертвых клеток пять на пять и блок пять на пять с его центральной живой клеткой и оставшимися мертвыми клетками являются близнецами: состояние центральной клетки не может влиять на более поздние конфигурации паттерна. Таким образом, в этом случае теорема Эдемского сада позволяет продемонстрировать существование Эдемского сада гораздо легче, чем обнаружение явного сиротского паттерна.[16]

Доказательство эскиза

Основная идея доказательства теоремы заключается в использовании подсчет аргумента, чтобы показать, что любой отказ локальной инъективности (двойные модели) приводит к сиротской модели, и наоборот. Более подробно, предположим для конкретности, что основная решетка автомата представляет собой двумерную квадратную сетку, имеющую s различные состояния клетки, что двойные узоры п и Q оба вписываются в п × п квадрат, и что радиус окрестности любой ячейки не более п. Затем, чтобы определить, подходит ли шаблон млн × млн квадрат - это сирота, достаточно посмотреть на те части потенциальных предшественников, которые вписываются в (м + 2)п × (м + 2)п квадрат и не содержат шаблон Q. Но есть только(sп × п − 1)(м + 2) × (м + 2) этих потенциальных предшественников. При достаточно больших значениях м это число меньше числа sмлн × млн потенциальных сирот. Следовательно, один из потенциальных сирот не имеет предшественника и действительно является сиротой; то есть неинъективность подразумевает несюръективность. Наоборот (позволяя п быть размером с Ограничительная рамка сироты) очень похожий аргумент подсчета показывает, что количество шаблонов, которые соответствуют (м + 2)п × (м + 2)п квадрат и не содержат сирот, слишком малы, чтобы обеспечить четкого преемника каждому начальному шаблону в пределах млн × млн квадрат, из которого следует, что некоторые два возможных стартовых паттерна - близнецы. Следовательно, несюръективность подразумевает локальную неинъективность.[15]

Приемлемость против местной приемистости

Пространственно-временная диаграмма Правило 90, в котором нет Эдемского сада, несмотря на то, что он не является инъекционным. Каждая строка отображает конфигурацию с течением времени вниз.

Различие между инъективностью и локальной инъективностью в теореме необходимо, поскольку существуют клеточные автоматы, которые являются локально инъективными, но не инъективными. Одним из примеров является Правило 90, одномерный бинарный автомат, правило обновления которого заменяет состояние каждой ячейки Эксклюзивный или двух своих соседей. В этом автомате у каждого состояния есть четыре предшественника, поэтому оно не является инъективным, но также не имеет Эдемского сада.[17]

С состояниями покоя

В таких автоматах, как Игра жизни Конвея, существует особое состояние "покоя", при котором покоящаяся ячейка, окрестности которой полностью неподвижны, остается неподвижной. В этом случае можно определить «конечную конфигурацию» как конфигурацию только с конечным числом нестационарных ячеек. У любого нелокально-инъективного клеточного автомата в состоянии покоя есть райские сады, которые сами по себе являются конечными конфигурациями, например, любая конечная конфигурация, содержащая сироту. Автомат также может иметь конечную конфигурацию, единственные предшественники которой не конечны (например, в Правиле 90 этим свойством обладает конфигурация с единственной живой клеткой). Однако теорема Эдемского сада не характеризует существование таких закономерностей.[18]

В неевклидовых геометриях

В клеточных автоматах, определенных над мозаикой гиперболическая плоскость, или для многомерных гиперболических пространств, счетный аргумент в доказательстве теоремы Эдемского сада не работает, поскольку он неявно зависит от свойства евклидовых пространств, что граница области растет медленнее, чем ее объем как функция радиуса. Существуют гиперболические клеточные автоматы, у которых есть близнецы, но у которых нет Эдемского сада, и другие гиперболические клеточные автоматы, у которых есть Эдемский сад, но нет близнецов; эти автоматы могут быть определены, например, инвариантно относительно вращения на равномерные гиперболические мозаики в котором три семиугольники встречаются в каждой вершине, или в которой четыре пятиугольники встречаются в каждой вершине.[19]

Однако теорема Эдемского сада может быть обобщена за пределы евклидовых пространств на клеточные автоматы, определенные на элементах податливая группа.[20] Более слабая форма теоремы Эдемского сада утверждает, что каждый инъективный клеточный автомат сюръективен. Это может быть доказано для софические группы с использованием Теорема Акс-Гротендика, аналогичное соотношение между инъективностью и биективностью в алгебраической геометрии.[21] В более общем смысле группы, для которых выполняется эта более слабая форма, называются суръюнктивные группы.[22] Нет известных примеров групп, которые не являются суръюнктивными.[23]

В художественной литературе

В Грег Иган роман Город перестановки, главный герой использует конфигурацию Эдемского сада, чтобы создать ситуацию, в которой его копия может доказать, что он живет в симуляции. Раньше все его смоделированные копии оказывались в каком-то варианте «реального мира»; хотя у них были воспоминания о том, что они были смоделированными копиями, живущими в симуляции, всегда было более простое объяснение того, как эти воспоминания появились. Однако конфигурация Эдемского сада не может возникнуть, кроме как в разумно спроектированной симуляции. Религиозные параллели сделаны намеренно.[24]

Примечания

  1. ^ а б В Мост жизни Vol. 3 (Сентябрь 1971 г.) редактор Роберт Т. Уэйнрайт объявил, что Роджер Бэнкс и Стив Уорд доказали существование райского сада, живые клетки которого вписываются в 9 × 33 прямоугольник, и представлял конфигурацию, которую Бэнкс считал райским садом. В Мост жизни Vol. 4 (Декабрь 1971 г.) Уэйнрайт сообщил, что группа в Honeywell используя программное обеспечение Дон Вудс проверил конфигурацию Бэнкса как райский сад. Смотрите также Гарднер (1983).
  2. ^ а б Мур (1962).
  3. ^ а б c Кари (2012), Раздел 2.1, «Основные определения», стр. 5–6.
  4. ^ а б Тоффоли и Марголус (1990). Обратите внимание, однако, что Тоффоли и Марголус называют функцию перехода глобальной картой.
  5. ^ Кари (2012), п. 10.
  6. ^ а б c Кари (2012), п. 11.
  7. ^ Кари (1990); Кари (1994). Главный результат Кари состоит в том, что невозможно проверить, обратим ли клеточный автомат, но он также показывает неразрешимость проверки, существует ли райский сад.
  8. ^ Тоффоли и Марголус (1990): «Даже если бы кто-то был готов вернуться к поиску методом перебора, долгое время поиска привело бы к появлению только нескольких элементов, и даже они были бы по большей части совершенно неинтересными».
  9. ^ Хардуэн-Дюпарк (1972–73).
  10. ^ Хардуэн-Дюпарк (1974).
  11. ^ Фламменкамп (2016).
  12. ^ а б c d Кари (2012), Предложение 2, с. 11.
  13. ^ Одномерный случай этого результата - теорема 5.1 из Хедлунд (1969). Как и в приведенном здесь более простом доказательстве, здесь используется компактность конфигурационного пространства. В своей более ранней работе Мур и Майхилл не отделяли сирот от райских садов и доказали свои результаты только на примере детей-сирот.
  14. ^ Хедлунд (1969), Теорема 3.4.
  15. ^ а б Майхилл (1963).
  16. ^ Гарднер (1983).
  17. ^ Сатнер (1991).
  18. ^ Аморосо и Купер (1970); Скайум (1975).
  19. ^ Маргенштерн (2009). Маргенштерн приписывает результат себе и Яркко Кари.
  20. ^ Чекерини-Зильберштейн, Мачи и Скаработти (1999); Капобианко, Гийон и Кари (2013); Бартольди и Келак (2016).
  21. ^ Громов (1999).
  22. ^ Готшальк (1973).
  23. ^ Чеккерини-Зильберштейн и Корнарт (2010).
  24. ^ Блэкфорд, Икин и МакМаллен (1999); Хейлс (2005).

Рекомендации

внешняя ссылка