Тип клеточного автомата, схожий с игрой Конвея «Жизнь»
Клеточный автомат (КА) подобен жизни (в том смысле, что он похож на игру Конвея «Жизнь »), если он соответствует следующим критериям:
Массив ячеек автомата имеет два измерения.
Каждая ячейка автомата имеет два состояния (условно называемые «живой» и «мертвый», или альтернативно «включенный» и «выключенный»).
Окрестность каждой ячейки называется окрестностью Мура ; она состоит из восьми ячеек, смежных с рассматриваемой, и (возможно) самой ячейки.
На каждом временном шаге автомата новое состояние клетки может быть выражено как функция количества соседних клеток, находящихся в живом состоянии, и собственного состояния клетки; то есть правило является внешним тоталистическим (иногда называемым полутоталистическим ).
Этот класс клеточных автоматов назван в честь Игры Жизни (B3/S23), самого известного клеточного автомата, который соответствует всем этим критериям. Для описания этого класса используется множество различных терминов. Обычно его называют «семейством Жизни» или просто используют фразы вроде «похож на Жизнь».
Обозначения правил
Существуют три стандартных обозначения для описания этих правил, которые похожи друг на друга, но несовместимы. Вольфрам и Паккард (1985) используют код Вольфрама , десятичное число, двоичное представление которого имеет биты, которые соответствуют каждому возможному числу соседей и состоянию клетки; биты этого числа равны нулю или единице соответственно, поскольку клетка с этим соседством мертва или жива в следующем поколении. [1] Два других обозначения распаковывают ту же последовательность битов в строку символов, которую легче прочитать человеку.
В нотации, используемой в Cellebration Мирека, правило записывается как строка x/y, где каждая из x и y представляет собой последовательность различных цифр от 0 до 8 в числовом порядке. Наличие цифры d в строке x означает, что живая клетка с d живыми соседями выживает в следующем поколении шаблона, а наличие d в строке y означает, что мертвая клетка с d живыми соседями становится живой в следующем поколении. Например, в этой нотации игра жизни Конвея обозначается как 23/3. [2] [3]
В нотации, используемой в пакете Golly с открытым исходным кодом для клеточных автоматов, и в формате RLE для хранения шаблонов клеточных автоматов правило записывается в виде By/Sx, где x и y такие же, как в нотации MCell. Таким образом, в этой нотации игра Conway's Game of Life обозначается как B3/S23. «B» в этом формате означает «рождение», а «S» — «выживание». [4]
Подборка правил, похожих на жизненные
Хаотические ромбы в правиле Diamoeba (B35678/S5678)Взрывной хаос в правиле Seeds (B2/S)Игра жизни Конвея (B3/S23)Отжиг (B4678/S35678)
Существует 2 18 = 262 144 возможных правил Life-like, только небольшая часть из которых была изучена в деталях. В описаниях ниже все правила указаны в формате Golly/RLE.
Еще несколько правил перечислены и описаны в списке правил MCell [2] и Эппштейном (2010), включая некоторые правила с B0, в которых фон поля клеток чередуется между живыми и мертвыми на каждом шаге. [4]
Любой автомат вышеуказанной формы, содержащий элемент B1 (например, B17/S78 или B145/S34), всегда будет взрывным для любого конечного шаблона: на любом шаге рассмотрим ячейку ( x , y ), которая имеет минимальную x -координату среди включенных ячеек, и среди таких ячеек ячейку с минимальной y -координатой. Тогда ячейка ( x -1, y -1) должна иметь ровно одного соседа и станет включенной на следующем шаге. Аналогично, шаблон должен расти на каждом шаге в каждом из четырех диагональных направлений. Таким образом, любой непустой начальный шаблон приводит к взрывному росту. [4]
Любой автомат вышеуказанной формы, который не включает ни один из B0, B1, B2 или B3, не может поддерживать движение или расширение шаблонов, поскольку любая ячейка за пределами прямоугольного блока здания, содержащего шаблон, имеет не более трех соседей. Большинство конечных шаблонов в правилах, обозначение которых начинается с B2, и все конечные шаблоны в правилах, начинающихся с B1, растут во всех направлениях, а не остаются ограниченными по размеру, с фронтом, который движется со скоростью света. Таким образом, оставшиеся «интересные» правила — это те, которые начинаются с B3 (Game of Life, Highlife, Morley, 2x2, Day&Night) или начинаются с B0 (и не включают S8, так как в противном случае вместо этого можно изучать двойственное правило). [4]
Обобщения
Существуют и другие клеточные автоматы, вдохновленные Игрой Жизни, но которые не соответствуют определению «подобных жизни», данному в этой статье, поскольку их окрестности больше, чем окрестности Мура, или они определены на трехмерных решетках, или они используют другую топологию решетки. Например:
Нетоталистические правила зависят от конфигурации живых клеток в районе.
Неизотропные правила , которые ведут себя по-разному в разных направлениях. Существует 2 512 ≈1,34*10 154 правил такого рода, включая изотропные правила. [ необходима цитата ]
Изотропные нетоталистические правила ведут себя одинаково при вращении и отражении. Существует 2 102 ≈5.07*10 30 правил такого рода, включая внешнетоталистические правила. [22]
Правила поколений включают одно или несколько состояний «умирания», в которые клетки переключаются вместо мгновенной смерти. Наиболее известными примерами в этой категории являются правила «Мозг Брайана» (B2/S/3) и «Звездные войны» (B2/S345/4). Случайные закономерности в этих двух правилах включают большое разнообразие космических кораблей и граблей со скоростью c, часто сталкивающихся и объединяющихся в еще большее количество объектов.
Larger than Life — семейство клеточных автоматов, изученное Келли Мишель Эванс. Они имеют очень большие радиусы окрестностей, но выполняют пороговую оценку «рождения/смерти», похожую на жизнь Конвея. Эти автоматы имеют жутко органические структуры «планера» и «мигалки». [23]
RealLife — это континуальный предел Evan's Larger Than Life CA, в пределе, когда радиус соседства стремится к бесконечности, а шаг решетки стремится к нулю. Технически, они вообще не являются клеточными автоматами, поскольку лежащее в основе «пространство» — это непрерывная евклидова плоскость R 2 , а не дискретная решетка Z 2 . Их изучал Маркус Пивато. [24]
Lenia — это семейство непрерывных клеточных автоматов, созданное Бертом Ван-Чаком Чаном. Пространство, время и состояния Игры Жизни обобщены до непрерывных доменов, используя большие соседства, дробные обновления и состояния действительных чисел соответственно.
Картер Бэйс предложил ряд обобщений Игры Жизни для трехмерных КА, определенных на Z 3 ( 3D Life ). [25] Бэйс также изучал двумерные КА, подобные жизни, с треугольными или шестиугольными окрестностями. [26] [27]
Ссылки
^ Вольфрам, Стивен ; Паккард, Нью-Гэмпшир (1985), «Двумерные клеточные автоматы», Журнал статистической физики , 38 (5–6): 901–946, Bibcode : 1985JSP....38..901P, doi : 10.1007/BF01010423Перепечатано в книге Вольфрама, Стивена (1994), Клеточные автоматы и сложность , Westview Press, стр. 211–249, ISBN 978-0-201-62664-3.
^ abcdefghijk Войтович, Мирек, Лексикон правил клеточных автоматов - Семья: Жизнь, Cellebration Мирека.
^ ab Wuensche, Andrew (2011), "16.10 Игра-Жизнь и другие правила, подобные жизненным – rcode", Exploring Discrete Dynamics: The DDLAB manual, Luniver Press, стр. 145–146, ISBN978-1-905986-31-6.
^ abcdefghijk Эппштейн, Дэвид (2010), «Рост и распад живых клеточных автоматов», в Адамацки, Эндрю (редактор), Game of Life Cellular Automata , Springer, стр. 71–98, arXiv : 0911.2890 , doi : 10.1007/978-1-84996-217-9_6, ISBN978-1-84996-216-2.
^ Сильверман, Брайан, «Изменение правил», Виртуальный компьютер, Математическая ассоциация Америки.
^ Шаблоны для семян, собранные Джейсоном Саммерсом.
^ Ниваш, Габриэль (2007), Фотонная/XOR-система.
^ Тоффоли, Томмазо ; Марголус, Норман (1987), «1.2 Анимация по числам», Клеточные автоматы: новая среда для моделирования , MIT Press, стр. 6–7.
^ Гриффит, Дэвид; Мур, Кристофер (1996), «Жизнь без смерти P-полна», Complex Systems , 10 : 437–447.
↑ Гарднер, Мартин (октябрь 1970 г.), «Математические игры — Фантастические комбинации новой игры-пасьянса Джона Конвея «Жизнь»", Scientific American , 223 : 120–123.
^ Паундстоун, Уильям (1985), Рекурсивная Вселенная: космическая сложность и пределы научного знания , Contemporary Books, стр. 134, ISBN978-0-8092-5202-2.
^ Эйзенманн, Джек, 34 ЖИЗНИ.
^ Гравнер, Янко; Гриффит, Дэвид (1998), «Рост клеточного автомата на Z2 : теоремы, примеры и проблемы», Успехи в прикладной математике , 21 (2): 241–304, doi : 10.1006/aama.1998.0599 , MR 1634709.
^ Белл, Дэвид, HighLife - Интересный вариант жизни.
^ Белл, Дэвид, День и ночь — интересный вариант жизни.
↑ Морли, Стивен (2005), b368s245 Guns, архивировано из оригинала 2006-03-11.
^ Vichniac, Gérard Y. (1986), «Модели беспорядка и организации на основе клеточных автоматов», в Bienenstock, E.; Fogelman Soulie, F.; Weisbuch, G. (ред.), Disordered Systems and Biological Organization , NATO ASI Series, т. 20, Springer-Verlag, стр. 3–20, doi :10.1007/978-3-642-82657-3_1.
^ Пиковер, Клиффорд А. (1993), «Лавовые лампы в 21 веке», The Visual Computer , 10 (3): 173–177, doi :10.1007/bf01900906.
^ Chopard, Bastien; Droz, Michel (1998), "2.2.4 Правило отжига", Моделирование физических систем с помощью клеточных автоматов , Коллекция Aléa-Saclay: Монографии и тексты по статистической физике, Cambridge University Press, Кембридж, стр. 37–38, doi :10.1017/CBO9780511549755, ISBN0-521-46168-5, г-н 1669736.
^ Сапин, Эммануэль (2010), «Больше, чем жизнь: масштабирование порогового диапазона когерентных структур жизни», в Адамацки, Эндрю (ред.), Игра «Жизнь. Клеточные автоматы» , стр. 135–165, doi :10.1007/978-1-84996-217-9_9
^ Эванс, Келли Мишель (2003), «Больше, чем жизнь: масштабирование порогового диапазона когерентных структур жизни», Physica D , 183 (1–2): 45–67, Bibcode : 2003PhyD..183...45E, doi : 10.1016/S0167-2789(03)00155-6.
