Жизнь без Смерти
Жизнь без Смерти — это клеточный автомат , похожий на «Игру жизни» Конвея и другие жизнеподобные правила клеточного автомата. В этом клеточном автомате исходный образец семян растет по тому же правилу, что и в «Игре жизни» Конвея; однако, в отличие от Жизни, шаблоны никогда не уменьшаются. Первоначально это правило рассматривалось Тоффоли и Марголусом (1987) , которые назвали его «Чернильное пятно»; [1] его также называли «Хлопьями». [2] В отличие от более сложных узоров, существующих в «Игре жизни» Конвея, «Жизнь без смерти» обычно включает в себя натюрморты , в которых не происходит никаких изменений, и лестничные узоры, которые растут по прямой линии.
Правила
[ редактировать ]Клеточный автомат — это тип модели, изучаемой в математике и теоретической биологии, состоящий из регулярной сетки ячеек, каждая из которых находится в одном из конечного числа состояний, таких как «включено» и «выключено». Паттерн в клеточном автомате «Жизнь без Смерти» состоит из бесконечной двумерной сетки ячеек, каждая из которых может находиться в одном из двух состояний: мертвом или живом. Эквивалентно, его можно рассматривать как массив пикселей , каждый из которых может быть чёрным и белым; на рисунках белые пиксели представляют собой живые клетки, а черные пиксели — мертвые клетки. Две из этих ячеек считаются соседними, если они смежны по вертикали, горизонтали или диагонали. [3]
Любой такой шаблон изменяется в течение последовательности временных шагов путем применения следующих простых правил одновременно ко всем ячейкам шаблона: каждая клетка, которая была живой в предыдущем шаблоне, остается живой, каждая мертвая клетка, имеющая ровно 3 живых соседа, сама становится живой, и каждая вторая мертвая клетка остается мертвой. То есть в обозначениях, описывающих правила клеточного автомата Life-like , это правило 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, ISBN 9780262291019 .
- ^ Лексикон правил клеточных автоматов , 15 сентября 2001 г., заархивировано из оригинала 10 февраля 2009 г. , получено 1 июня 2009 г.
- ^ Это определение соседей известно как район Мура .
- ^ Jump up to: Перейти обратно: а б с д и Гравнер, Янко; Дэвид, Гриффит (1998), «Рост клеточных автоматов на Z 2 : Теоремы, примеры и проблемы», «Достижения прикладной математики» , 21 : 241–304, doi : 10.1006/aama.1998.0599 .
- ^ обозначение c Используется , а c называется скоростью света , поскольку это самая высокая скорость, с которой информация может распространяться по клеточному автомату, использующему окрестность Мура.
- ^ Jump up to: Перейти обратно: а б с д Гриффит, Дэвид; Мур, Кристофер (1996), «Жизнь без смерти P-полна» , Complex Systems , 10 : 437–447 .
- ^ Jump up to: Перейти обратно: а б Эппштейн, Дэвид (2009), Быстрые лестницы в жизни без смерти .
- ^ Гравнер, Янко (2003), «Явление роста в клеточных автоматах», Новые конструкции в клеточных автоматах , Исследования Института Санта-Фе в области наук о сложности, Oxford University Press, стр. 161–182, заархивировано из оригинала 06.2010 г. 26
Внешние ссылки
[ редактировать ]- Крутой CyberFlake и жизнь без смерти (пересмотренный) с веб-сайта сотового автомата Primordial Soup Kitchen.
- Жизнь без смерти на LifeWiki.