Жизнь без смерти - это клеточный автомат , похожий на «Игру жизни» Конвея и другиеправила клеточного автомата , подобные жизни . В этом клеточном автомате начальная семенная структура растет по тому же правилу, что и в «Игре жизни» Конвея; однако, в отличие от Жизни, шаблоны никогда не сокращаются. Правило первоначально рассматривалось Тоффоли и Марголусом (1987) , которые назвали его «Чернильной точкой»; [1] его также называли «хлопьями». [2] В отличие от более сложных паттернов, которые существуют в «Игре жизни» Конвея, «Жизнь без смерти» обычно представляет собой натюрморты , в которых не происходит никаких изменений, и лестницу. узоры, растущие по прямой линии.
Правила
Клеточный автомат - это тип модели, изучаемый в математике и теоретической биологии, состоящий из регулярной сетки ячеек, каждая из которых находится в одном из конечного числа состояний, таких как «включено» и «выключено». Паттерн клеточного автомата «Жизнь без смерти» состоит из бесконечной двумерной сетки ячеек, каждая из которых может находиться в одном из двух состояний: мертвая или живая. Точно так же его можно представить как массив пикселей , каждый из которых может быть черным и белым; на рисунках белые пиксели представляют живые клетки, а черные пиксели представляют мертвые клетки. Две из этих ячеек считаются соседними, если они смежны по вертикали, горизонтали или диагонали. [3]
Любой такой шаблон изменяется в течение последовательности временных шагов, применяя следующие простые правила одновременно ко всем ячейкам шаблона: каждая ячейка, которая была жива в предыдущем шаблоне, остается живой, каждая мертвая ячейка, у которой есть ровно 3 живых соседа, становится живой сама, и каждая вторая мертвая клетка остается мертвой. То есть в обозначении, описывающем правила жизнеподобного клеточного автомата , это правило B3 / S012345678: живая клетка рождается, когда есть 3 живых соседа, и живая клетка выживает с любым количеством соседей.
Побеги и лестницы
Образцы натюрморта обычны в «Жизни без смерти»: если нет мертвой клетки с тремя живыми соседями, образец останется неизменным для всех будущих временных шагов. Однако, поскольку клетка, будучи однажды живая, остается живой, набор живых клеток монотонно растет на протяжении всей эволюции паттерна, и не может быть никаких осцилляторов (паттернов, которые циклически повторяются через повторяющуюся последовательность форм), космических кораблей (паттернов, которые сохраняют та же форма, но с изменением положения), или другие более сложные модели, существующие в «Игре жизни» Конвея.
Напротив, общая черта паттернов «Жизнь без смерти» - это наличие лестниц , паттернов, растущих по прямой линии. Лестница будет расти вечно, если она не наткнется на какую-либо другую часть модели и не будет заблокирована, или если ее не настигнет какой-то более быстрорастущий образец. Наиболее распространенная схема лестницы показана на рисунке; каждые двенадцать ступенек такая же форма появляется на вершине лестницы, на четыре клетки дальше от начальной позиции лестницы. [4] Таким образом, скорость роста лестницы составляет четыре клетки на двенадцать ступеней, или, в обозначении Жизни, 4 c / 12 = c / 3; здесь c представляет собой одну единицу расстояния за временной шаг. [5] Другой распространенный паттерн (названный Гравнером и Гриффисом «паразитическим выстрелом» [4] ) продвигается вдвое быстрее, со скоростью 2 c / 3, вдоль лестницы, в конечном итоге блокируя лестницу и вызывая хаотический взрыв. [4] [6]
Варианты лестниц с другими скоростями были обнаружены в 2000 году Дином Хикерсоном, наряду с некоторыми паразитическими побегами, которые медленнее, чем наиболее распространенные 2 c / 3. Лестницы Хикерсона растут со скоростью 4 c / 9, 4 c / 10 и 4 c / 13. [7]
Моделирование схем
Лестницы в «Жизни без смерти» можно использовать для моделирования произвольных логических схем : [6] наличие или отсутствие лестницы в определенной позиции может использоваться для представления логического сигнала и различных взаимодействий между парами лестниц или между лестницами и шаблоны натюрморта, могут использоваться для моделирования логических элементов «и», «или» и «не», а также точек пересечения двух сигналов. Следовательно, моделирование закономерностей в правиле «Жизнь без смерти» является P-полным , а это означает, что маловероятно, что параллельный алгоритм существует для моделирования значительно быстрее, чем алгоритм, полученный наивным параллельным алгоритмом с одним процессором на ячейку клеточного автомата и одним временным шагом. за поколение шаблона. [6]
Бесконечный рост
Узоры из семян в виде шариков радиусом до десяти обычно приводят к узору натюрморта ; [4], однако, Гравнер [8] предполагает, что правило является сверхкритическим, что означает, что более крупные или менее симметричные семена обычно постоянно расширяются хаотично. Лестницы - частое явление на границах областей хаотичного роста.
Считается, что паттерн в «Жизни без смерти» заполняет плоскость положительной плотностью, если существует некоторый радиус r, такой, что каждая клетка плоскости в конечном итоге оказывается на расстоянии r от живой клетки. Вопрос о том, существуют ли такие модели бесконечного роста, был поставлен Гравнером, Гриффитом и Муром как открытая проблема. [4] [6] Хаотические узоры, общие для этого правила, могут заполнять плоскость, но они также могут оставлять большие пустые прямоугольные области, обрамленные лестницами, что приводит к нарушению условия плотности. Однако в 2009 году Дин Хикерсон обнаружил диагонально расширяющиеся закономерности, которые в конечном итоге перерастают в высокопериодный бесконечный рост, решая открытую проблему. [7]
Заметки
- ^ Тоффоли, Томмазо ; Марголус, Норман (1987), «1.2 Анимация по числам», Машины сотовых автоматов: новая среда для моделирования , MIT Press, стр. 6–7.
- ^ Лексикон MCell правил клеточных автоматов .
- ^ Это определение соседей известно как окрестности Мура .
- ^ а б в г д Гравнер, Янко; Дэвид, Griffeath (1998), "Cellular Automaton рост на Z 2 : теоремы, примеры и проблемы", Успехи прикладной математики , 21 : 241-304, DOI : 10,1006 / aama.1998.0599.
- ^ Используется обозначение c , а c называется скоростью света , потому что это самая высокая скорость, с которой информация может распространяться через клеточный автомат, использующий окрестность Мура.
- ^ а б в г Гриффит, Дэвид; Мур, Кристофер (1996), "Жизнь без смерти полна" , " Сложные системы" , 10 : 437–447..
- ^ а б Эпштейн, Дэвид (2009), Более быстрые лестницы в жизни без смерти.
- ^ Гравнер, Янко (2003), «Явления роста в клеточных автоматах», Новые конструкции в клеточных автоматах , Исследования Института Санта-Фе в области наук о сложности, Oxford University Press, стр. 161–182, архивировано с оригинала на 2010-06- 26 год
Внешние ссылки
- Прохладный CyberFlake и Life Without Death (Revisited) , с веб-сайта клеточных автоматов Primordial Soup Kitchen.
- Жизнь без смерти на LifeWiki.