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