WikiDer > Жизнеподобный клеточный автомат

Life-like cellular automaton

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

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

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

Обозначение правил

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

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

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

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

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

Есть 218 = 262144 возможных реалистичных правила, лишь небольшая часть из которых была изучена досконально. В описаниях ниже все правила указаны в формате 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] и по Эппштейн (2010), включая некоторые правила с B0, в которых фон поля клеток чередуется между живыми и мертвыми на каждом шаге.[4]

Любой автомат вышеуказанной формы, содержащий элемент B1 (например, B17 / S78 или B145 / S34), всегда будет взрывоопасным для любого конечного паттерна: на любом этапе рассмотрим ячейку (Икс,у), имеющая минимум Икс-координат среди ячеек, которые включены, и среди таких ячеек с минимальным у-координат. Тогда ячейка (Икс-1,у-1) должен иметь ровно одного соседа и на следующем шаге станет включенным. Точно так же узор должен расти на каждом шаге в каждом из четырех диагональных направлений. Таким образом, любой непустой стартовый образец приводит к взрывному росту.[4]

Любой автомат вышеуказанной формы, который не включает ни один из B0, B1, B2 или B3, не может поддерживать перемещение или расширение шаблонов, потому что любая ячейка за пределами прямоугольного строительного блока, содержащего шаблон, имеет не более трех соседей. Большинство конечных паттернов в правилах, обозначение которых начинается с B2, и все конечные паттерны в правилах, начинающихся с B1, растут во всех направлениях, а не остаются ограниченного размера, с фронтом, который движется со скоростью света. Таким образом, оставшиеся «интересные» правила - это те, которые начинаются с B3 (Game of Life, Highlife, Morley, 2x2, Day & Night) или начинаются с B0 (и не включают S8, иначе вместо этого можно изучить дуал).[4]

Обобщения

Существуют и другие клеточные автоматы, вдохновленные Игрой Жизни, но не подходящие под определение «живого», данное в этой статье, потому что их окрестности больше, чем окрестности Мура, или они определены на трехмерных решетках. , или они используют другую топологию решетки. Например:

  • Нетоталистический правила зависят от конфигурации живых клеток по соседству.
    • Не-изотропный правила которые ведут себя по-разному в разных направлениях. Есть 2512≈1.34*10154 правила такого рода, в том числе изотропные правила.
    • Изотропные нетоталистические правила одинаково ведут себя при вращении и отражении. Есть 2102≈5.07*1030 правила такого рода, в том числе внешние тоталистические правила.[22]
  • Больше чем жизнь семейство клеточных автоматов, изученное Келли Мишель Эванс. У них очень большие районы радиуса действия, но они выполняют пороговое значение «рождение / смерть», подобное жизни Конвея. У этих автоматов есть устрашающе органичные структуры «планер» и «поворотник».[23]
  • Реальная жизнь является «континуальным пределом» КА Эвана «Больше, чем жизнь» в пределе, когда радиус окрестности стремится к бесконечности, а шаг решетки стремится к нулю. Технически они вовсе не клеточные автоматы, потому что лежащее в основе "пространство" - это непрерывная евклидова плоскость. р2, а не дискретная решетка Z2. Их изучал Маркус Пивато.[24]
  • Картер Бэйс предложил множество обобщений Игры Жизни для трехмерного КА, определенного на Z3 (3D жизнь).[25] Бэйс также изучал двумерные, похожие на жизнь КА с треугольными или шестиугольными окрестностями.[26][27]

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

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

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