Жизнь без смерти - Life without Death

Шаблон «Жизнь без смерти», который создает три лестницы и показывает смерть двух лестниц при столкновении с одной ячейкой (двумя разными способами), поворот лестницы и смерть лестницы при столкновении с другой лестницей.
Число живых клеток на поколение в образце, показанном выше, демонстрирующем монотонную природу Жизни без Смерти.

Жизнь без смерти это клеточный автомат, похожий на Игра жизни Конвея и другие Жизнеподобный клеточный автомат правила. В этом клеточном автомате начальный образец семени растет по тому же правилу, что и в «Игре жизни» Конвея; однако, в отличие от Жизни, шаблоны никогда не сжимаются. Правило изначально рассматривалось Тоффоли и Марголус (1987), который назвал это «Инкспот»;[1] его также называли «хлопьями».[2] В отличие от более сложных паттернов, существующих в «Игре жизни» Конвея, в «Жизнь без смерти» обычно натюрморт паттерны, в которых не происходит никаких изменений, и лестница узоры, растущие по прямой линии.

Правила

Клеточный автомат - это тип модели, изучаемый в математика и теоретическая биология состоящий из регулярной сетки ячеек, каждая из которых находится в одном из конечного числа состояний, таких как «включено» и «выключено». Паттерн клеточного автомата «Жизнь без смерти» состоит из бесконечной двумерной сетки ячеек, каждая из которых может находиться в одном из двух состояний: мертвая или живая. Точно так же его можно рассматривать как массив пиксели, каждый из которых может быть черно-белым; на рисунках белые пиксели представляют живые клетки, а черные пиксели представляют мертвые клетки. Две из этих ячеек считаются соседи если они смежны по вертикали, горизонтали или диагонали.[3]

Любой такой шаблон изменяется в течение последовательности временных шагов путем применения следующих простых правил одновременно ко всем ячейкам шаблона: каждая ячейка, которая была жива в предыдущем шаблоне, остается живой, каждая мертвая ячейка, имеющая ровно 3 живых соседей, становится живой сама, и каждая вторая мертвая клетка остается мертвой. То есть в обозначениях, описывающих Жизнеподобный клеточный автомат rules, это правило B3 / S012345678: живая ячейка рождается, когда есть 3 живых соседа, и живая ячейка выживает с любым количеством соседей.

Побеги и лестницы

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

Пример быстрого паразитического побега, бегущего по более медленной лестнице. Когда кончики ствола и лестницы встречаются, они оба разрушаются, создавая хаотический беспорядок и отправляя два выстрела обратно вниз по первоначальной лестнице в противоположном направлении.

Напротив, общей чертой паттернов «Жизнь без смерти» является наличие лестницы, узоры, растущие по прямой линии. Лестница будет расти вечно, если она не упирается в какую-либо другую часть модели и не блокируется, или если ее не догоняет какой-то более быстрорастущий образец. Наиболее распространенная схема лестницы показана на рисунке; каждые двенадцать ступеней такая же фигура появляется на вершине лестницы, на четыре клетки дальше от начальной позиции лестницы.[4] Таким образом, скорость роста лестницы составляет четыре клетки на двенадцать ступеней, или, в обозначении Жизни, 4c/12 = c/ 3; Вот c представляет одну единицу расстояния за временной шаг.[5] Другой распространенный паттерн (названный Гравнером и Гриффит «паразитическим побегом»)[4]) продвигается вдвое быстрее, со скоростью 2c/ 3, вдоль лестницы, в конечном итоге блокируя лестницу и вызывая хаотический взрыв.[4][6]

Варианты лестниц с другими скоростями были обнаружены в 2000 году Дином Хикерсоном, наряду с некоторыми паразитическими побегами, которые действуют медленнее, чем наиболее распространенные 2.c/ 3 один. Лестницы Хикерсона растут со скоростью 4c/9, 4c/ 10 и 4c/13.[7]

Моделирование схем

Лестницы в «Жизнь без смерти» можно использовать для имитации произвольных Булевы схемы:[6] наличие или отсутствие лестницы в определенной позиции может использоваться для представления логического сигнала, а различные взаимодействия между парами лестниц или между лестницами и образцами натюрморта могут использоваться для имитации «и», «или», и «не» вентили логической логики, а также точки пересечения двух сигналов. Следовательно, это P-полный имитировать закономерности в правиле «Жизнь без смерти», то есть маловероятно, что параллельный алгоритм существует для моделирования значительно быстрее, чем полученное с помощью простого параллельного алгоритма с одним процессором на ячейку клеточного автомата и одним временным шагом на генерацию шаблона.[6]

Бесконечный рост

Узоры семян в виде шариков радиусом до десяти обычно приводят к натюрморт шаблон;[4] однако Гравнер[8] предполагает, что правило является сверхкритическим, что означает, что более крупные или менее симметричные семена обычно постоянно расширяются хаотично. Лестницы - частое явление на границах областей хаотичного роста.

Считается, что паттерн в «Жизни без смерти» заполняет плоскость положительной плотностью, если есть некоторый радиус. р так что каждая ячейка плоскости в конечном итоге оказывается на расстоянии р живой клетки. Вопрос о том, существуют ли такие модели бесконечного роста, был поставлен Гравнером, Гриффитом и Муром как открытая проблема.[4][6] Хаотические узоры, общие для этого правила, могут заполнять плоскость, но они могут также оставлять большие пустые прямоугольные области, обрамленные лестницами, что приводит к нарушению условия плотности. Однако в 2009 году Дин Хикерсон обнаружил диагонально расширяющиеся закономерности, которые в конечном итоге перерастают в высокопериодный бесконечный рост, решая открытую проблему.[7]

Примечания

  1. ^ Тоффоли, Томмазо; Марголус, Норман (1987), "1.2 Анимация по номерам", Машины с клеточными автоматами: новая среда для моделирования, MIT Press, стр. 6–7..
  2. ^ Лексикон MCell правил клеточных автоматов.
  3. ^ Это определение соседей известно как Окрестности Мура.
  4. ^ а б c d е Гравнер, Янко; Дэвид, Гриффит (1998), "Рост клеточного автомата на Z2: Теоремы, примеры и проблемы », Успехи в прикладной математике, 21: 241–304, Дои:10.1006 / aama.1998.0599.
  5. ^ Обозначение c используется, и c называется скорость света, потому что это самая быстрая скорость, с которой информация может распространяться по клеточному автомату, который использует окрестность Мура.
  6. ^ а б c d Гриффит, Дэвид; Мур, Кристофер (1996), «Жизнь без смерти - П-завершена», Сложные системы, 10: 437–447.
  7. ^ а б Эппштейн, Дэвид (2009), Более быстрые лестницы в жизни без смерти.
  8. ^ Гравнер, Янко (2003), "Явления роста в клеточных автоматах", Новые конструкции в клеточных автоматах, Исследования Института Санта-Фе в науках о сложности, Oxford University Press, стр. 161–182, заархивировано оригинал на 2010-06-26

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