Грабли (клеточный автомат) - Rake (cellular automaton)

А грабли, в лексиконе клеточные автоматы, это тип шлейф-пуховик, который представляет собой автомат, оставляющий за собой след из мусора. Однако в случае граблей оставшийся мусор представляет собой поток космические корабли,[1] которые представляют собой автоматы, которые «путешествуют», проходя цикл через короткую серию итераций, и оказываются в новом месте после того, как каждый цикл возвращается к исходной конфигурации.

Подборка граблей в Игра жизни Конвея

В Игра жизни Конвея, открытие граблей было одним из ключевых компонентов, необходимых для формирования заводчик, первый известный образец в жизни, в котором количество живых клеток показывает квадратичный рост. Заводчик формируется путем расстановки нескольких граблей так, чтобы планеры - наименьшие возможные космические корабли - они взаимодействуют друг с другом, образуя последовательность планерные пушки, паттерны, которые испускают планеры. Вылетевшие планеры заполняют растущий треугольник плоскости игры.[2] В более общем плане, когда существует грабля для правила клеточного автомата (математическая функция, определяющая следующую итерацию, которая должна быть получена из конкретной конфигурации живых и мертвых клеток), часто можно построить пуфы, которые оставляют следы многих других видов объектов, с помощью столкновение с потоками космических кораблей, выброшенными несколькими параллельными граблями.[3] Как пишет Дэвид Белл:

Они чрезвычайно важны в Life, потому что выходные данные могут использоваться для создания других объектов и могут передавать сигналы для выполнения логических операций. Всякий раз, когда обнаруживается какой-либо новый двигатель, важно «приручить» его, чтобы его бесполезный «грязный» выхлоп превратился в «чистый» выхлоп, особенно у планеров.[4]

«Космические грабли», которые движутся ортогонально десять единиц через двадцать шагов цикла, испуская один планер за цикл

Первыми граблями, обнаруженными в начале 1970-х годов, были «космические грабли», которые перемещаются со скоростью. c/2 (или один блок каждые два шага), испуская планер каждые двадцать шагов.[5] На всю жизнь теперь известны грабли, которые ходят ортогонально со скоростью c/2, c/3, c/4, c/5, 2c/5, 2c/7, c/10[6][нужен лучший источник ] и 17c/ 45, а по диагонали со скоростями c/ 4 и c/ 12, с множеством разных периодов.[7] Известны и другие грабли. живые клеточные автоматы, включая Highlife,[8] День Ночь,[9] и Семена.[10]

Готтс (1980) показывает, что космические грабли в «Жизни» могут быть сформированы «стандартной последовательностью столкновений», в которой один планер взаимодействует с широко разделенным набором исходных семян из трех ячеек (шоры и блоки ). Как следствие, он находит нижнюю границу вероятности того, что эти паттерны образуются при любом достаточно редком и достаточно большом случайном начальном условии для Жизни. Этот результат приводит к стандартным последовательностям коллизий для многих других паттернов, таких как селекционеры.[11]

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

  1. ^ Рейк, Лексикон Life В архиве 2008-12-21 на Wayback Machine. Рейк, Э. Вайсштейн.
  2. ^ Гарднер, М. (1983). «Игра в жизнь, часть III». Колеса, жизнь и другие математические развлечения. W.H. Фримен. С. 241–257.
  3. ^ По этой причине, Страница статуса жизни Джейсона Саммерса описывает грабли как «универсальный пуффер» и собирает данные о существовании граблей для различных скоростей и периодов использования.
  4. ^ Дэвид И. Белл, Технология Speed ​​c / 3 в жизни Конвея, 1999.
  5. ^ Космические грабли, Лексикон жизни В архиве 2009-02-20 в Wayback Machine. Космические грабли, Э. Вайсштейн. Первое опубликованное описание космических граблей было в Lifeline, информационном бюллетене, опубликованном Р. Уэйнрайтом в начале 1970-х годов, выпуск 3.6 (индекс ).
  6. ^ http://www.conwaylife.com/forums/viewtopic.php?f=2&t=2057&start=175#p28969
  7. ^ Страница статуса жизни Джейсона Саммерса.
  8. ^ Дэвид И. Белл, HighLife - интересный вариант жизни, 1994.
  9. ^ Дэвид И. Белл, День и ночь - интересный вариант жизни, 1997.
  10. ^ Шаблоны для правила Семена, собранный Джейсоном Саммерсом.
  11. ^ Готтс, Н. М. (2000). "Эмерджентные явления в больших разреженных случайных массивах" Игры жизни "Конвея'". Международный журнал системной науки. 31 (7): 873–894. Дои:10.1080/002077200406598.