Криттеры

«Криттеры» (англ. Critters) — блочный клеточный автомат, проявляющий поведение, схожее с игрой «Жизнь» Конвея; в частности, полон по Тьюрингу^[1][2]. Впервые описан Томмазо Тоффоли (итал. Tommaso Toffoli) и Норманом Марголусом (англ. Norman Margolus) в 1987 году, как и некоторые другие обратимые клеточные автоматы^[3].

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

Функция перехода «Криттеров» зависит от числа живых ячеек в блоке: если их две, блок не изменяется; если их нуль, одна или четыре, то состояние каждой ячейки блока меняется на противоположное. В случае трёх живых ячеек преобразование происходит в два этапа: состояние каждой ячейки меняется на противоположное, а блок целиком вращается на 180°. Поскольку число живых ячеек в любом случае меняется на число мёртвых, а операции для каждого из чисел ячеек обратимы по отдельности, эти правила задают обратимый клеточный автомат^[3].

Альтернативная версия функции перехода меняет состояния на противоположные только в блоках с двумя живыми ячейками, а также вращает на нечётных шагах все блоки с тремя живыми ячейками, а на чётных — с одной. Такая версия отличается от стандартной тем, что она не меняет число живых ячеек, и при этом имеет схожее^[как?] динамическое поведение^[2].

Как и для любого обратимого клеточного аппарата, если в качестве начального состояния «Криттеров» выбрать случайное, то состояние останется неупорядоченным в процессе эволюции^[1][3]. Но если начать с небольшого количества случайных ячеек внутри бо́льшего региона мёртвых ячеек, то из центрального региона распространится много маленьких шаблонов, подобных планеру из игры «Жизнь», которые будут сложным образом взаимодействововать^[1][2][3]. Вообще говоря, «Криттеры» допускают сложные космические корабли и осцилляторы с бесконечным числом различных периодов^[2].

Существует недоказанная гипотеза, согласно которой при выборе периодических граничных условий (то есть при склейке краёв прямоугольного поля, в результате чего получается тор) начальные положения с количеством живых ячеек, достаточно малым по сравнению с размером поля, имеют высокую вероятность привести к состоянию, в котором один планер случайно блуждает по полю из осциллирующих неупорядоченных ячеек^[4].

В игре «Жизнь» столкновения космических кораблей могут привести к взаимоуничтожению, стабильной конфигурации или осциллятору, что невозможно для обратимого клеточного автомата. Вместо этого любое столкновение должно привести к появлению хотя бы одного космического корабля^[1][4], а при симметричном столкновении двух космических кораблей появляется симметричный набор из двух или более космических кораблей^[1]. Если рассчитать начальное состояние так, чтобы места столкновений были правильными, в «Криттерах» можно симулировать бильярдный компьютер на планерах и, подобно игре «Жизнь», доказать полноту по Тьюрингу^[1].

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