Существа (клеточный автомат) - Critters (cellular automaton)
Critters это обратимый блокировать клеточный автомат с аналогичной динамикой Игра жизни Конвея,[1][2] впервые описан Томмазо Тоффоли и Норман Марголус в 1987 г.[3]
Определение
Критеры задаются на двумерной бесконечной сетке ячеек, которые можно отождествить с целочисленная решетка. Как и в «Игре жизни» Конвея, в любой момент времени каждая клетка может находиться в одном из двух состояний: живая или мертвая. Правило Critters - это блочный клеточный автомат используя район Марголус. Это означает, что на каждом шаге ячейки автомата делятся на блоки 2 × 2, и каждый блок обновляется независимо от других блоков. Центр блока на одном временном шаге становится углом четырех блоков на следующем временном шаге, и наоборот; таким образом, четыре ячейки в каждом блоке принадлежат четырем различным блокам 2 × 2 предыдущего раздела.[3]
Функция перехода для Critters подсчитывает количество живых ячеек в блоке, и если это число равно двум, она оставляет блок без изменений. Если количество живых ячеек равно нулю, одной или четырем, функция перехода меняет состояние каждой ячейки в блоке. И наконец, если количество живых клеток равно трем, переход переворачивает каждое состояние, а затем поворачивает весь блок на 180 °. Поскольку функция, объединяющая эти операции, обратима, автомат, определяемый этими правилами, является обратимый клеточный автомат.[3]
Альтернативный вариант функции перехода переворачивает состояния только в блоках с ровно двумя живыми ячейками и с чередующимися временными шагами вращает либо блоки с тремя живыми ячейками, либо блоки с одной живой ячейкой. В отличие от исходной функции перехода, это сохраняет количество живых ячеек на каждом шаге, но приводит к динамическому поведению, эквивалентному исходной версии функции.[2]
Динамика
В правиле Криттера, как и в любом обратимом клеточном автомате, начальные состояния, в которых все клетки принимают случайно выбранные состояния, остаются неструктурированными на протяжении всей своей эволюции.[1][3] Однако, если начать с меньшего поля случайных клеток, сосредоточенных в более крупной области мертвых клеток, многие мелкие паттерны, подобные жизненным планер сбежать из центральной случайной области и взаимодействовать друг с другом.[1][2][3] Было высказано предположение, но не доказано, что для периодические граничные условия (так что все пространство клеточного автомата конечно) начальные поля случайных ячеек, которые значительно меньше всего пространства, с большой вероятностью приведут к состояниям, в которых одиночный глайдер следует за случайная прогулка через поле колеблющихся обломков.[4]
В жизни Конвея столкновения планеров могут привести к полностью мертвому состоянию, устойчивой модели или осциллятору, но это невозможно в Криттерах. Вместо этого, из-за обратимости правила, каждое столкновение двух или более планеров должно приводить к паттерну, из которого выходит по крайней мере один планер,[1][4] и когда два планера сталкиваются симметрично, результатом также должна быть симметричная совокупность двух или более планеров, покидающих место столкновения.[1] С начальным состоянием, которое тщательно упорядочивает места этих столкновений, правило Critters может быть выполнено для имитации бильярдный компьютер и поэтому, как и Жизнь, он может поддерживать универсальные вычисления.[1] Правило Critters может также поддерживать более сложные космические корабли различной скорости, а также генераторы с бесконечным множеством разных периодов.[2]
Несмотря на сложность своего поведения, Криттеры подчиняются определенным законы сохранения и симметрия правила. Например, паритет Количество живых ячеек вдоль определенных диагоналей сетки не изменяется правилом обновления и остается неизменным на протяжении всей эволюции любого паттерна Critters. Кроме того, если паттерн начинается с конечного числа живых клеток, то после любого четного числа шагов в нем будет такое же конечное число живых клеток. (После нечетного числа шагов это число будет вместо этого подсчитывать мертвые клетки шаблона.)[1] В отличие от многих других обратимых блочных клеточных правил, изученных Тоффоли и Марголусом, правило Криттера не является обратным самому себе, поэтому паттерны Криттера не подчиняются симметрии обращения времени; однако вместо этого он симметричен относительно комбинации обращения времени и дополнения состояний.[3]
Рекомендации
- ^ а б c d е ж грамм Марголус, Норман (1999), «Кристаллические вычисления», в Hey, Энтони Дж. Г. (ред.), Фейнман и вычисления, Perseus Books, стр. 267–305, arXiv:комп-газ / 9811002, Bibcode:1998comp.gas.11002M.
- ^ а б c d Маротта, Себастьян М. (2005), «Жизнь в мире зверей», Revista Ciências Exatas e Naturais, 7 (1), заархивировано из оригинал 19 марта 2012 г..
- ^ а б c d е ж Тоффоли, Томмазо; Марголус, Норман (1987), «12.8.2 Critters», Машины с клеточными автоматами: новая среда для моделирования, MIT Press, стр. 132–134..
- ^ а б Дева, Натаниэль; Икегами, Такаши (июль 2014 г.), «Может быть только один: обратимые клеточные автоматы и сохранение генки», Искусственная жизнь 14: Материалы четырнадцатой Международной конференции по синтезу и моделированию живых систем, MIT Press, Дои:10.7551 / 978-0-262-32621-6-ch084.