Тоталистичные клеточные автоматы

Существует специальный класс клеточный автоматов, называемых тоталистичными. На каждом шаге эволюции клеточного автомата значение ячейки равно какому-либо целому числу(обычно выбираемого из конечного множества <https://ru.wikipedia.org/wiki/%D0%9A%D0%BE%D0%BD%D0%B5%D1%87%D0%BD%D0%BE%D0%B5_%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE>), а новое состояние клетки определяется суммой значений клеток-соседей и, возможно, предыдущим состоянием клетки. Если состояние клетки на новом шаге зависит от её предыдущего состояния, то такой клеточный автомат называется внешним тоталистичным. Игра Жизнь <https://ru.wikipedia.org/wiki/%D0%98%D0%B3%D1%80%D0%B0_%D0%96%D0%B8%D0%B7%D0%BD%D1%8C>является примером внешнего тоталистического клеточного автомата с набором значений ячеек .

Связанные определения клеточных автоматов

Существует множество возможных обобщений концепций клеточных автоматов.

Один из них - использование сетки не с квадратами(гиперкубами <https://ru.wikipedia.org/wiki/%D0%93%D0%B8%D0%BF%D0%B5%D1%80%D0%BA%D1%83%D0%B1> в многомерном случае), а с другими геометрическими фигурами в её основе. Например, если поле представлено шестиугольным паркетом <https://ru.wikipedia.org/wiki/%D0%A8%D0%B5%D1%81%D1%82%D0%B8%D1%83%D0%B3%D0%BE%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%BF%D0%B0%D1%80%D0%BA%D0%B5%D1%82>, то шестиугольники будут клетками. Однако иногда такие клеточные автоматы оказывались идентичными клеточным автоматам на сетке с квадратными клетками, только при этом было необходимо вместе специальные правила отношений с клетками-соседями. Другой способ обобщения - использование нерегулярной сетки(например, в виде Мозаики Пенроуза <https://ru.wikipedia.org/wiki/%D0%9C%D0%BE%D0%B7%D0%B0%D0%B8%D0%BA%D0%B0_%D0%9F%D0%B5%D0%BD%D1%80%D0%BE%D1%83%D0%B7%D0%B0>).

Ещё один способ - использование вероятностных правил. Такие клеточные автоматы называются стохастическими <https://ru.wikipedia.org/w/index.php?title=%D0%A1%D1%82%D0%BE%D1%85%D0%B0%D1%81%D1%82%D0%B8%D1%87%D0%B5%D1%81%D0%BA%D0%B8%D0%B9_%D0%BA%D0%BB%D0%B5%D1%82%D0%BE%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&redlink=1>. В таких системах задается вероятность, что на следующем шаге клетка сменит свой цвет на другой. Или, например, в игре «Жизнь» <https://ru.wikipedia.org/wiki/%D0%98%D0%B3%D1%80%D0%B0_%D0%96%D0%B8%D0%B7%D0%BD%D1%8C>добавляется правило, что клетка с определенной вероятностью может изменить свой цвет на противоположный, а другие правила этого клеточного автомата остаются без изменений.

Определение соседства клетки может меняться с течением времени и\или пространства. Например, на первом шаге соседями будут горизонтально смежные клетки, а на другом - вертикально смежные.

Существуют непрерывные клеточные автоматы <https://ru.wikipedia.org/w/index.php?title=%D0%9D%D0%B5%D0%BF%D1%80%D0%B5%D1%80%D1%8B%D0%B2%D0%BD%D1%8B%D0%B9_%D0%BA%D0%BB%D0%B5%D1%82%D0%BE%D1%87%D0%BD%D1%8B%D0%B9_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82&action=edit&redlink=1>. В таких системах вместо дискретного набора состояний используются непрерывные функции (обычно определяемые на промежутке ).

Свойство обратимости

Клеточный автомат называется обратимым, если для каждой текущей конфигурации существует только одна предшествующая конфигурация. Если рассматривать клеточный автомат как функцию, отображающую одну конфигурацию в другую, то обратимость предполагает биективность <https://ru.wikipedia.org/wiki/%D0%91%D0%B8%D0%B5%D0%BA%D1%86%D0%B8%D1%8F> этой функции. Если клеточный автомат обратим, то его обратная эволюция также может быть описана клеточным автоматом. Конфигурации, не имеющие предшествующих, то есть недостижимые в данном клеточном автомате, носят название «Сады Эдема» <https://ru.wikipedia.org/wiki/%D0%A1%D0%B0%D0%B4_%D0%AD%D0%B4%D0%B5%D0%BC%D0%B0_(%D0%BA%D0%BE%D0%BD%D1%84%D0%B8%D0%B3%D1%83%D1%80%D0%B0%D1%86%D0%B8%D1%8F_%D0%BA%D0%BB%D0%B5%D1%82%D0%BE%D1%87%D0%BD%D0%BE%D0%B3%D0%BE_%D0%B0%D0%B2%D1%82%D0%BE%D0%BC%D0%B0%D1%82%D0%B0)>.

Для одномерных клеточных автоматов существуют алгоритмы определения обратимости или необратимости. Однако для клеточных автоматов с двумя и более измерениями таких алгоритмов нет.