Кле́точный автома́т — дискретная модель, изучаемая в математике, теории вычислимости, физике, теоретической биологии и микромеханике. Основой является пространство из прилегающих друг к другу клеток (ячеек), образующих решётку. Каждая клетка может находиться в одном из конечного множества состояний (например, 1 и 0). Решётка может быть любой размерности, бесконечной или конечной, для решётки с конечными размерами часто предусматривается закольцованность при достижении предела (границы). Для каждой клетки определено множество клеток, называемых окрестностью. Например, окрестность фон Неймана ранга 2 включает все клетки на расстоянии не более 2 от текущей. Устанавливаются правила перехода клеток из одного состояния в другое. Обычно правила перехода одинаковы для всех клеток. Один шаг автомата подразумевает обход всех клеток и на основе данных о текущем состоянии клетки и её окрестности определение нового состояния клетки, которое будет у неё при следующем шаге. Перед стартом автомата оговаривается начальное состояние клеток, которое может устанавливаться целенаправленно или случайным образом.
Основное направление исследования клеточных автоматов — алгоритмическая разрешимость тех или иных задач. Также рассматриваются вопросы построения начальных состояний, при которых клеточный автомат будет решать заданную задачу.
История Станислав Улам, работая в Лос-Аламосской национальной лаборатории в 1940-е годы, изучал рост кристаллов, используя простую решёточную модель. В это же время Джон фон Нейман, коллега Улама, работал над проблемой самовоспроизводящихся систем. Первоначальная концепция фон Неймана основывалась на идее робота, собирающего другого робота. Такая модель известна как кинематическая. Разработав эту модель, фон Нейман осознал сложность создания самовоспроизводящегося робота и, в частности, обеспечения необходимого «запаса частей», из которого должен строиться робот. Улам предложил фон Нейману использовать более абстрактную математическую модель, подобную той, что Улам использовал для изучения роста кристаллов. Таким образом возникла первая клеточно-автоматная система. Подобно решётке Улама, клеточный автомат фон Неймана двухмерный, а самовоспроизводящийся робот описан алгоритмически. Результатом явился универсальный конструктор, работающий «внутри» клеточного автомата с окрестностью, включающей непосредственно прилегающие клетки, и имеющего 29 состояний. Фон Нейман доказал, что для такой модели существует паттерн, который будет бесконечно копировать самого себя.
Также в 1940-е годы, Норберт Винер и разработали клеточно-автоматную модель возбудимой среды. Целью было математическое описание распространения импульса в сердечных нервных узлах. Их оригинальная работа продолжает цитироваться в современных исследованиях по аритмии и возбудимым средам.
В 1960-е годы клеточные автоматы изучались как частный тип динамических систем, и впервые была установлена их связь с областью символьной динамики. В 1969 году Г. А. Хедланд () провёл обзор результатов, полученных в этом направлении. Наиболее значимым результатом явилось описание набора правил клеточного автомата как множества непрерывных эндоморфизмов в сдвиговом пространстве.
В 1970-е получила известность двухмерная клеточно-автоматная модель с двумя состояниями клеток, известная как игра «Жизнь». Изобретённая Джоном Конвеем и популяризованная Мартином Гарднером, она использует следующие правила: на квадратной решётке каждая клетка имеет 8 соседей; если клетка имеет двух «живых» соседей, она остаётся в прежнем состоянии. Если клетка имеет трёх «живых» соседей, она переходит в «живое» состояние. В остальных случаях клетка «умирает». Несмотря на свою простоту, система проявляет огромное разнообразие поведения, колеблясь между хаосом и порядком. Одним из феноменов игры «Жизнь» являются глайдеры — сочетания клеток, «движущиеся» по сетке как единое целое и взаимодействующие с другими статичными или подвижными конструкциями. Возможно установить стартовое состояние клеток, при котором глайдеры будут выполнять некоторые вычисления. Впоследствии было доказано, что игра «Жизнь» может полностью эмулировать универсальную машину Тьюринга. 11-го ноября 2002 года Пауль Чепмен () построил вариант «Жизни», который является РММ (Регистровой Машиной Минского). Первая версия образца была большой (268’096 живых ячеек на площади 4,558 x 21,469 клеток) и медленной (20 поколений/сек при использовании Life32 Иогана Бонтеса () на 400 MHz AMD K6-II). Таким образом было доказано, что в игре «Жизнь» можно выполнить любой вычислительный алгоритм.
В 1969 году немецкий инженер Конрад Цузе опубликовал книгу «Вычислимый космос», где выдвинул предположение, что физические законы дискретны по своей природе, и что вся Вселенная является гигантским клеточным автоматом. Это была первая книга из области, называемой сейчас цифровой физикой.
В СССР профессор В. З. Аладьев опубликовал ряд работ по теории клеточных автоматов. Как обобщающий использовался термин «однородные структуры». Была предложена и другая терминология для описания отдельных аспектов данной проблематики. Одну из его с соавторами книг по клеточным автоматам BookAuthority включила в список 100 лучших электронных книг всех времён по дискретной математике«Selected problems in the theory of classical cellular automata» made it to BookAuthority’s best Discrete Mathematics ebooks of all time!.
В 1983 году Стивен Вольфрам опубликовал первую из серии статей, исследующих элементарные клеточные автоматы . Неожиданная сложность поведения этих простых одномерных автоматов привела Вольфрама к предположению, что сложность естественных систем обусловлена сходным механизмом. Кроме того, в течение этого периода Вольфрам формулирует концепцию истинной случайности и вычислительной неприводимости, и выдвигает предположение, что автомат с «правилом 110» может быть универсальным (полным по Тьюрингу). Это доказал в 1990 году его ассистент Мэтью Кук.
В 1987 году Брайан Сильверман () предложил клеточный автомат Wireworld.
В 2002 году Вольфрам публикует 1280-страничный текст «Наука нового типа» (), где широко аргументирует, что достижения в области клеточных автоматов не являются изолированными, но весьма устойчивы и имеют большое значение для всех областей науки.
Математическое определение Двумерный клеточный автомат можно определить как множество конечных автоматов на плоскости, помеченных целочисленными координатами (i, j), каждый из которых может находиться в одном из состояний : . Изменение состояний автоматов происходит согласно правилу перехода , где — некоторая окрестность точки . К примеру, окрестность фон Неймана определяется как , а окрестность Мура . Число всех возможных правил перехода определяется числом состояний и количеством соседей n и составляет A.G.Hoekstra, J.Kroc, P.Sloot. Simulating complex systems by cellular automata. Springer, 2010. ISBN 978-3-642-12202-6
Классификация
Классификация по типам поведения
Стивен Вольфрам в своей книге A New Kind of Science предложил 4 класса, на которые все клеточные автоматы могут быть разделены в зависимости от типа их эволюции. Классификация Вольфрама была первой попыткой классифицировать сами правила, а не типы поведения правил по отдельности. В порядке возрастания сложности классы выглядят следующим образом: Класс 1: Результатом эволюции начальных условий является быстрый переход к гомогенной стабильности. Любые негомогенные конструкции быстро исчезают. Класс 2: Результатом эволюции начальных условий является быстрый переход в неизменяемое негомогенное состояние либо возникновение циклической последовательности. Большинство структур начальных условий быстро исчезает, но некоторые остаются. Локальные изменения в начальных условиях оказывают локальный характер на дальнейший ход эволюции системы. Класс 3: Результатом эволюции почти всех начальных условий являются псевдо-случайные, хаотические последовательности. Любые стабильные структуры, которые возникают почти сразу же уничтожаются окружающим их шумом. Локальные изменения в начальных условиях оказывают неопределяемое влияние на ход эволюции системы. Класс 4: Результатом эволюции являются структуры, которые взаимодействуют сложным образом с формированием локальных, устойчивых структур. В результате эволюции могут получаться некоторые последовательности Класса 2, описанного выше. Локальные изменения в начальных условиях оказывают неопределяемое влияние на ход эволюции системы. Некоторые клеточные автоматы этого класса обладают свойством универсальности по Тьюрингу, что доказано для Правила 110 и игры «Жизнь».
Такого рода определения носят по большей части качественный характер и их можно по-разному интерпретировать. Вот что Вольфрам говорит об этом:
Практически при всякой попытке классификации будут возникать ситуации, когда по одному свойству предмет можно отнести к одному классу, а какому-либо другому свойству — к другому классу. Такая же ситуация и с клеточными автоматами: встречаются правила, которые показывают свойства, присущие одновременно одному и другому классу.
Тоталистичные клеточные автоматы Существует специальный класс клеточных автоматов, называемых тоталистичными. На каждом шаге эволюции клеточного автомата значение клетки равно какому-либо целому числу (обычно выбираемого из конечного множества), а новое состояние клетки определяется суммой значений клеток-соседей и, возможно, предыдущим состоянием клетки. Если состояние клетки на новом шаге зависит от её предыдущего состояния, то такой клеточный автомат называется внешним тоталистичным. Игра Жизнь является примером внешнего тоталистического клеточного автомата с набором значений ячеек .
Термин тоталистичный происходит от английского totalistic. В свою очередь total может быть переведено как сумма, что и отражено в принципе действия этого типа автоматов, когда новое значение клетки зависит от суммы значений других клеток.
Связанные определения клеточных автоматов Существует множество возможных обобщений концепций клеточных автоматов.
Один из них — использование сетки не с квадратами (гиперкубами в многомерном случае), а с другими геометрическими фигурами в её основе. Например, если поле представлено шестиугольным паркетом, то шестиугольники будут клетками. Однако иногда такие клеточные автоматы оказывались идентичными клеточным автоматам на сетке с квадратными клетками, только при этом было необходимо ввести специальные правила отношений с клетками-соседями. Другой способ обобщения — использование нерегулярной сетки (например, в виде Мозаики Пенроуза).
Ещё один способ — использование вероятностных правил. Такие клеточные автоматы называются стохастическими. В таких системах задаётся вероятность, что на следующем шаге клетка сменит свой цвет на другой. Или, например, в игре «Жизнь» добавляется правило, что клетка с определённой вероятностью может изменить свой цвет на противоположный, а другие правила этого клеточного автомата остаются без изменений.
Определение соседства клетки может меняться с течением времени и/или пространства. Например, на первом шаге соседями будут горизонтально смежные клетки, а на другом — вертикально смежные.
В клеточных автоматах на новое состояние клетки не влияют новые состояния смежных клеток. Правило можно поменять: можно сделать так, что, например, в блоках 2 на 2 состояния клеток зависят от состояния клеток внутри блока и от таких же смежных блоков.
Существуют непрерывные клеточные автоматы. В таких системах вместо дискретного набора состояний используются непрерывные функции (обычно определяемые на промежутке ).
Свойство обратимости