Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

Клеточный автомат (КА) Жизнь, как (в том смысле, что похожа на игры Конвея жизни ) , если он удовлетворяет следующим критериям:

  • Массив ячеек автомата имеет два измерения.
  • Каждая ячейка автомата имеет два состояния (условно называемые «живым» и «мертвым» или, альтернативно, «включенным» и «выключенным»).
  • Окрестность каждой ячейки - это окрестность Мура ; он состоит из восьми соседних с рассматриваемой ячейкой и (возможно) самой ячейки.
  • На каждом временном шаге автомата новое состояние ячейки может быть выражено как функция количества соседних ячеек, которые находятся в активном состоянии, и от собственного состояния ячейки; то есть правило является внешним тоталистическим (иногда называемым полутоталистическим ).

Этот класс клеточных автоматов назван в честь Игры Жизни (B3 / S23), самого известного клеточного автомата, который отвечает всем этим критериям. Для описания этого класса используется много разных терминов. Его принято называть «Жизненной семьей» или просто использовать такие фразы, как «подобный жизни».

Обозначение правил [ править ]

Есть три стандартных обозначения для описания этих правил, которые похожи друг на друга, но несовместимы. Вольфрам и Паккард (1985) используют код Вольфрама , десятичное число, двоичное представление которого имеет биты, соответствующие каждому возможному количеству соседей и состоянию ячейки; биты этого числа равны нулю или единице соответственно, поскольку ячейка с этим соседством мертва или жива в следующем поколении. [1] Две другие нотации распаковывают одну и ту же последовательность битов в строку символов, которая легче читается человеком.

В обозначениях, используемых Mirek's Cellebration, правило записывается в виде строки x / y, где каждый из x и y представляет собой последовательность различных цифр от 0 до 8 в числовом порядке. Наличие цифры d в строке x означает, что живая ячейка с d живыми соседями выживает в следующем поколении шаблона, а присутствие d в строке y означает, что мертвая ячейка с d живыми соседями становится живой в следующее поколение. Например, в этих обозначениях «Игра жизни» Конвея обозначена как 23/3. [2] [3]

В нотации, используемой пакетом клеточного автомата с открытым исходным кодом Golly и в формате RLE для хранения паттернов клеточного автомата, правило записывается в форме By / Sx, где x и y такие же, как в нотации MCell. Таким образом, в этих обозначениях «Игра жизни» Конвея обозначается B3 / S23. Буква «B» в этом формате означает «рождение», а «S» - «выживание». [4]

Подборка жизненных правил [ править ]

Хаотические бриллианты в правиле Diamoeba (B35678 / S5678)
Взрыв хаоса в правиле Seeds (B2 / S)
Игра жизни Конвея (B3 / S23)
Отжиг (B4678 / S35678)

Существует 2 18  = 262 144 возможных жизненных правила, лишь небольшая часть из которых изучена досконально. В описаниях ниже все правила указаны в формате Golly / RLE.

Известные жизненные правила
ПравилоИмяОписание и источники
B1357 / S1357РепликаторРеплицирующий автомат Эдварда Фредкина : каждый паттерн в конечном итоге заменяется множеством своих копий. [2] [3] [4]
B2 / SСеменаВсе паттерны - это фениксы, а это означает, что каждая живая клетка немедленно умирает, а многие паттерны приводят к взрывному хаотическому росту. Однако известны некоторые спроектированные шаблоны со сложным поведением. [2] [5] [6]
B25 / S4Это правило поддерживает небольшой самовоспроизводящийся шаблон, который в сочетании с небольшим шаблоном планера заставляет планер подпрыгивать назад и вперед в псевдослучайном движении. [4] [7]
B3 / S012345678Жизнь без смертиТакже известен как Inkspot или Flakes. Ожившие клетки никогда не умирают. Он сочетает в себе хаотический рост с более структурированными схемами, похожими на лестницу, которые можно использовать для моделирования произвольных логических схем. [2] [4] [8] [9]
B3 / S23ЖизньОчень сложное поведение. [10] [11]
B34 / S3434 ЖизньПервоначально считалось стабильной альтернативой Жизни , пока компьютерное моделирование не обнаружило, что более крупные структуры имеют тенденцию к взрыву. Имеет множество небольших генераторов и космических кораблей. [2] [12] [13]
B35678 / S5678DiamoebaОбразует крупные ромбы с хаотично колеблющимися границами. Впервые изучил Дин Хикерсон, который в 1993 году предложил приз в 50 долларов за поиск рисунка, заполняющего пространство живыми клетками; приз выиграл в 1999 году Дэвид Белл. [2] [4] [14]
B36 / S1252x2Если паттерн состоит из блоков 2x2, он будет продолжать развиваться в той же форме; группирование этих блоков в большие степени двойки приводит к тому же поведению, но медленнее. Имеет сложные генераторы с высокими периодами, а также небольшой планер. [2] [15]
B36 / S23HighLifeПодобно Life, но с небольшой самовоспроизводящейся структурой. [2] [4] [16]
B3678 / S34678День НочьСимметричный по реверсированию включения-выключения. Разработал шаблоны с очень сложным поведением. [2] [4] [17]
B368 / S245МорлиНазванный в честь Стивена Морли; также называется Move. Поддерживает очень высокопериодические и медленные космические корабли. [2] [4] [18]
B4678 / S35678ОтжигТакже называется правилом скрученного большинства. Симметричный по реверсированию включения-выключения. Аппроксимирует укороченную кривую потока на границах между живыми и мертвыми клетками. [19] [20] [21]

Еще несколько правил перечислены и описаны в списке правил MCell [2] и Eppstein (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]
  • Больше, чем жизнь - это семейство клеточных автоматов, изученное Келли Мишель Эванс. У них есть районы с очень большим радиусом, но они выполняют пороговое значение «рождение / смерть», подобное жизни Конвея. У этих автоматов есть устрашающе органичные структуры «планер» и «поворотник». [23]
  • RealLife - это «предел континуума» CA Larger Than Life Эвана, в пределе, когда радиус окрестности стремится к бесконечности, а шаг решетки стремится к нулю. Технически они вовсе не клеточные автоматы, потому что лежащее в основе «пространство» - это непрерывная евклидова плоскость R 2 , а не дискретная решетка Z 2 . Их изучал Маркус Пивато. [24]
  • Картер Бэйс предложил множество обобщений Игры Жизни для трехмерного СА, определенного на Z 3 ( 3D Life ). [25] Бэйс также изучал двумерные реалистичные КА с треугольными или гексагональными окрестностями. [26] [27]

Ссылки [ править ]

  1. ^ Вольфрам, Стивен ; Паккард, Н.Х. (1985), «Двумерные клеточные автоматы», журнал статистической физики , 38 (5–6): 901–946, Bibcode : 1985JSP .... 38..901P , doi : 10.1007 / BF01010423Перепечатано в Wolfram, Stephen (1994), Cellular Automata and Complexity , Westview Press, стр. 211–249, ISBN 978-0-201-62664-3.
  2. ^ a b c d e f g h i j k Войтович, Мирек, Лексика правил сотового автомата - Семья: Жизнь , Праздник Мирека.
  3. ^ a b Wuensche, Эндрю (2011), «16.10 Игра жизни и другие подобные жизни правила - rcode», Исследование дискретной динамики: руководство DDLAB, Luniver Press, стр. 145–146, ISBN 978-1-905986-31-6.
  4. ^ a b c d e f g h i j k Эппштейн, Дэвид (2010), «Рост и распад жизнеподобных клеточных автоматов», в Adamatzky, Andrew (ed.), Game of Life Cellular Automata , Springer, стр. 71–98, arXiv : 0911.2890 , doi : 10.1007 / 978-1-84996-217-9_6 , ISBN 978-1-84996-216-2.
  5. ^ Сильверман, Брайан, «Изменение правил», Виртуальный компьютер , Математическая ассоциация Америки.
  6. ^ Образцы для семян, собранные Джейсоном Саммерсом.
  7. ^ Nivasch, Габриэль (2007), Фотон система / XOR.
  8. ^ Тоффоли, Томмазо ; Марголус, Норман (1987), «1.2 Анимация по числам», Машины сотовых автоматов: новая среда для моделирования , MIT Press, стр. 6–7.
  9. ^ Гриффит, Дэвид; Мур, Кристофер (1996), "Жизнь без смерти полна" , " Сложные системы" , 10 : 437–447..
  10. ↑ Гарднер, Мартин (октябрь 1970 г.), «Математические игры - фантастические комбинации нового пасьянса Джона Конвея« жизнь » », Scientific American , 223 : 120–123.
  11. ^ Берлекамп, ER ; Конвей, Джон Хортон ; Гай, РК (2004), Winning Ways for your Mathematical Plays (2-е изд.), AK Peters Ltd.
  12. ^ Паундстон, Уильям (1985), Рекурсивная Вселенная: космическая сложность и пределы научного знания , Современные книги, стр. 134, ISBN 978-0-8092-5202-2.
  13. ^ Eisenmann, Джек, 34 LIFE.
  14. ^ Гравнер, Янко; Griffeath, Дэвид (1998), "автомат клеточного роста на Z 2 : теоремы, примеры и проблемы", Успехи в области прикладной математики , 21 (2): 241-304, DOI : 10,1006 / aama.1998.0599 , МР 1634709 .
  15. ↑ Johnston, Nathaniel (2010), «The B36 / S125» 2x2 «Life-Like Cellular Automaton», в Adamatzky, Andrew (ed.), Game of Life Cellular Automata , Springer, pp. 99–114, arXiv : 1203.1644 , Bibcode : 2010golc.book ... 99J , doi : 10.1007 / 978-1-84996-217-9_7 , ISBN 978-1-84996-216-2.
  16. ^ Белл, Дэвид, HighLife - Интересный вариант жизни.
  17. ↑ Белл, Дэвид, День и ночь - Интересный вариант жизни.
  18. ^ Morley, Стивен (2005), b368s245 оружие , архивируются с оригинала на 2006-03-11.
  19. ^ Vichniac, Gérard Y. (1986), "Клеточные автоматные модели беспорядка и организации", в Bienenstock, Е .; Fogelman Soulié, F .; Weisbuch, G. (eds.), Disordered Systems and Biological Organization , NATO ASI Series, 20 , Springer-Verlag, pp. 3–20, doi : 10.1007 / 978-3-642-82657-3_1..
  20. ^ Пиковер, Clifford A. (1993), "лампы Лава в 21 - м веке", Визуальный Компьютер , 10 (3): 173-177, DOI : 10.1007 / bf01900906.
  21. ↑ Chopard, Bastien; Дроз, Мишель (1998), «2.2.4 Правило отжига», Моделирование физических систем клеточными автоматами , Сборник Алеа-Сакле: Монографии и тексты по статистической физике, Cambridge University Press, Кембридж, стр. 37–38, DOI : 10.1017 / CBO9780511549755 , ISBN 0-521-46168-5, Руководство по ремонту  1669736.
  22. ^ Сапин, Эммануэль (2010), «Больше, чем жизнь: масштабирование порогового диапазона когерентных структур жизни», в Adamatzky, Andrew (ed.), Game of Life Cellular Automata , стр. 135–165, doi : 10.1007 / 978- 1-84996-217-9_9
  23. ^ Эванс, Келли Мишель (2003), «Больше, чем жизнь: масштабирование порогового диапазона когерентных структур жизни», Physica D , 183 (1-2): 45-67, Bibcode : 2003PhyD..183 ... 45E , doi : 10.1016 / S0167-2789 (03) 00155-6.
  24. ^ Пивато, Маркус (2007), «RealLife: континуальный предел клеточных автоматов большего размера, чем жизнь», « Теоретическая информатика» , 372 (1): 46–68, arXiv : math.DS / 0503504 , doi : 10.1016 / j.tcs .2006.11.019.
  25. ^ Отсеки Картер (2006), «Замечание об открытии многих новых правил игры в трехмерной жизни», сложных систем , 16 (4): 381-386.
  26. Перейти ↑ Bays, Carter (2007), «Открытие планерных пушек в игре о жизни для треугольной мозаики», Journal of Cellular Automata , 2 (4): 345–350.
  27. ^ Отсеки Картер (2005), «Записка о игре жизни в гексагональной и пятиугольной мозаик», сложных систем , 15 (3): 245-252.

Внешние ссылки [ править ]

  • Гриффит, Дэвид, «Тотальные правила роста с соседством Мура» , The Primordial Soup Kitchen , Департамент математики, Университет Висконсина.
  • Game of Life - Conway and Variants - Онлайн-программный инструмент