Кле́точный автома́т, множество элементарных абстрактных автоматов (называемых ячейками), принимающих входной сигнал, изменяющих своё состояние и вырабатывающих выходной сигнал. Каждый из элементарных автоматов может находиться в одном из состояний из некоторого фиксированного множества. Множеству состояний обычно ставится в соответствие подмножество целых чисел $g \in G = \left\{ {1,2,3,\ldots,k} \right\}.$

Клеточный автомат можно представить в виде регулярной решётки ячеек, каждая из которых может находиться в одном из конечного множества состояний. Решётка ячеек может быть любой размерности. Возможно создание не только плоской, объёмной, но и гиперпространственной структуры решётки ячеек. Регулярная сетка автомата может состоять не только из квадратных ячеек (гиперкубов в многомерном случае), но и из других геометрических фигур, например из правильных треугольников, шестиугольников. В отдельных случаях доказано, что такие клеточные автоматы эквивалентны клеточным автоматам большей размерности на сетке с квадратными клетками, при этом необходимы особые правила отображения состояний соседних ячеек. Известны клеточные автоматы с нерегулярной сеткой, в частности мозаики Пенроуза.

Существуют непрерывные клеточные автоматы, в них вместо дискретного набора состояний используются непрерывные функции с областью значений из отрезка $[0,1].$ Для каждой ячейки определяется множество ячеек, называемых окрестностью. Любая ячейка является автоматом Мура, для которого функция выходов линейная $y(t + 1) = k \cdot g(t) + c,$ $k = 1,$ $c = 0,$ $t = 0,1,2,3,\ldots{\rm{ }},$ а функция переходов зависит от состояний некоторого подмножества ячеек (называемых соседними), состояния которых являются входными сигналами для анализируемой ячейки $g(t + 1) = f[{g_i}(t),{g_{i + 1}}(t),...,g(t)]$ или $g(t + 1) = f[{g_i}(t)|{g_i}(t) \in D],$ $t = 0,1,2,3,\ldots{\rm{ }}$ Подмножество ячеек $D = \left. {\left\{ {{g_i}(t)} \right.} \right\}$ называется окрестностью определённого типа для анализируемой ячейки, а всё множество ячеек в совокупности является клеточным автоматом произвольной размерности. См. также Теория автоматов.

Наиболее известные т. н. окрестности Неймана порядков 1 и 2 определяются как подмножество ячеек на расстоянии не более 1 или 2 ячеек от текущей ячейки: $$D_{}^1(i,j) = \left. {\left\{ {{g_{k,l}}(t)|\left| {i - k} \right| + \left| {j - l} \right| \le 1} \right.} \right\},$$$$D_{}^2(i,j) = \left. {\left\{ {{g_{k,l}}(t)|\left| {i - k} \right| + \left| {j - l} \right| \le 2} \right.} \right\}.$$Окрестности Мура порядков 1 и 2 определяются как подмножество ячеек на расстоянии не более 1 или 2 ячеек от текущей ячейки: $$M_{}^1(i,j) = \left. {\left\{ {{g_{k,l}}(t)|\left| {i - k} \right| \le 1,\left| {j - l} \right| \le 1} \right.} \right\},$$$$M_{}^2(i,j) = \left. {\left\{ {{g_{k,l}}(t)|\left| {i - k} \right| \le 2,\left| {j - l} \right| \le 2} \right.} \right\}.$$Возможны различные сложные структуры окрестностей.

Конфигурацией клеточных автоматов называется распределение состояний его ячеек. Клеточный автомат называется обратимым, если для каждой текущей конфигурации существует только одна предшествующая конфигурация. В этом случае существует биективное (взаимно однозначное) отображение состояний ячеек окрестностей в новые состояния ячеек. Если клеточный автомат обратимый, то его обратная эволюция описывается тоже клеточным автоматом. Конфигурации, имеющие более одной предшествующей, являются необратимыми в данном клеточном автомате и условно названы «волшебными садами Эдема». Для одномерных клеточных автоматов существуют алгоритмы определения обратимости, но для клеточного автомата с двумя и более измерениями в общем случае таких алгоритмов нет.

Для инициализации работы клеточного автомата требуется задать начальное распределение состояний всех ячеек (начальную конфигурацию) и правило перехода состояний ячеек в следующую конфигурацию. Для каждого дискретного момента времени (временно́го такта), используя правило перехода и состояния ячеек окрестности, определяется новое состояние для каждой ячейки в следующий момент времени. При этом возникают слои конфигураций для соответствующего временно́го такта. Обычно правила перехода одинаковы для всех временны́х тактов, всех ячеек и применяются ко всей решётке (клеточному автомату). Преобразования конфигураций клеточного автомата при последовательных временны́х тактах называют эволюцией (смена поколений, слоёв конфигураций автомата).

Задачи теории клеточных автоматов

В теории клеточных автоматов выделяют основные задачи: построение начальной конфигурации, при которой клеточный автомат за определённое количество тактов решает поставленную задачу; определение алгоритмической разрешимости и сложности задач в клеточном автомате. Для клеточного автомата, рассматриваемого как единое целое, важнейшими параметрами являются распределение начальных состояний ячеек (начальная конфигурация) и способ отображения (называемый правилом) в состояние текущей ячейки. Количество всех возможных правил перехода зависит от количества состояний ячейки $\left| G \right|,$ количества соседних ячеек в соответствующей окрестности $\left| D \right|$ и равно $N = {\left| G \right|^{{{\left| G \right|}^{|D|}}}}.$ Различные правила перехода в новое состояние ячеек порождают различные типы эволюций клеточного автомата в дискретном времени. Простейшим является одномерный клеточный автомат, ячейки которого имеют два состояния, соседями являются две смежные с ней ячейки. Три ячейки (центральная и смежные с ней) порождают $2^3=8$ состояний трёх ячеек. На основе правила текущего состояния тройки ячеек определяется состояние центральной ячейки на следующем шаге. Для простейшего автомата возможны $2^8 = 256$ правил, пронумерованных по предложенному С. Вольфрамом стандартному соглашению. Клеточные автоматы, функционирующие по этим правилам, исследованы и промоделированы. Интересными оказались правила с номерами 30, 110, 161, представленные в таблице.

Правила, определяющие функционирование клеточного автомата

Для моделирования начальная конфигурация для симметричности у каждого автомата выбиралась следующим образом: центральная ячейка – 1 (чёрная), остальные – 0 (белые). С. Вольфрам в своей книге «Новый вид науки» (Wolfram S. A new kind of science. Champaign, 2002.) выделил 4 класса правил, приводящих к различным типам эволюций клеточного автомата при большинстве начальных конфигураций. Опишем их в порядке возрастания сложности: класс 1 – возникает быстрая стабилизация конфигурации клеточного автомата и его гомогенность, любые случайные образования быстро исчезают; класс 2 – возникают быстрая стабилизация конфигурации или колебания, большинство случайных структур быстро исчезает, но отдельные остаются; небольшие изменения в начальной конфигурации оказывают локальный характер на дальнейшую эволюцию автомата; класс 3 – возникают псевдослучайные, хаотические последовательности, любые возникающие стабильные структуры почти сразу же уничтожаются окружающим шумом; локальные изменения в начальных конфигурациях оказывают существенное влияние на дальнейшую эволюцию автомата; класс 4 – возникают сложные взаимодействующие структуры, имеющие локальные, устойчивые длительное время функционирующие подструктуры, могут появляться отдельные конфигурации класса 2; локальные изменения в начальных конфигурациях оказывают существенное влияние на дальнейшую эволюцию автомата.

Хорошо изучены одномерные клеточные автоматы, которые можно рассматривать в виде ленты (кольца) с произвольным количеством ячеек. Для одномерного клеточного автомата на плоскости можно отобразить эволюции по указанным правилам, если по одной из осей отложить дискретное время, а по другой оси отложить поколения конфигураций клеточного автомата. Приведём некоторые результаты моделирования. Правило 30 приводит при почти всех простых начальных конфигурациях к эволюции с хаотической, кажущейся случайной динамикой, что характерно для класса 3. Правило 110 приводит при почти всех простых начальных конфигурациях к эволюции с динамикой, не являющейся полностью случайной, но периодичность отсутствует, что характерно для класса 4. При этом возникают структуры, которые взаимодействуют друг с другом неочевидным, сложным образом. Доказано, что некоторые из порождаемых правилом структур достаточно разнообразны, чтобы обладать полнотой по Тьюрингу, что свидетельствует об универсальности эволюций этого класса. Правило 161 порождает при почти всех простых начальных конфигурациях фрактальные структуры, в частности вложенные подобные треугольники, что характерно для класса 1.

Существует класс тоталистических (от англ. totalistic; total – сумма) клеточных автоматов, для которых на каждом временно́м такте эволюции состояние каждой ячейки равно целому числу из некоторого подмножества натуральных чисел, а новое состояние ячейки определяется суммой значений состояний ячеек окрестности. Клеточный автомат называется внешним тоталистическим, если состояние ячейки на новом временно́м такте зависит также от предыдущего состояния этой же ячейки. Например, игра «Жизнь» – внешний тоталистический двумерный клеточный автомат с бинарным состоянием ячеек. Клеточные автоматы называются стохастическими, если используются вероятностные правила изменения конфигураций. Например, для таких автоматов в правилах можно задать вероятность смены цвета ячейки на следующем такте, а в игре «Жизнь» к имеющимся правилам добавить правило, позволяющее ячейке с некоторой вероятностью менять цвет.

Эволюция двумерного клеточного автомата в компьютерной реализации игры «Жизнь».Эволюция двумерного клеточного автомата в компьютерной реализации игры «Жизнь».

Conway's Game of LifeConway's Game of Life

Историческая справка

Первые научные труды по клеточно-автоматной теории появились в 1940-х гг. в работах С. Улама и Дж. фон Неймана, а также Н. Винера и А. Розенблуэта, которые разработали математическую модель, описывающую распространение импульсов сердечных нервных узлов (работа актуальна и в современных исследованиях по аритмии и возбудимым средам). Норберт Винер. Музей Массачусетского технологического института.Норберт Винер. Музей Массачусетского технологического института.В 1960-е гг. клеточные автоматы рассматривались как частный тип динамических систем. В 1969 г. Г. А. Хедланд дал анализ полученных результатов этого нового направления. Наиболее значимым результатом явилось описание набора правил клеточного автомата как множества непрерывных эндоморфизмов в сдвиговом пространстве. В 1970-е гг. получила известность двумерная клеточная автоматная модель с бинарными состояниями, известная как игра-модель «Жизнь» (Conway's Game of Life), изобретённая Дж. Х. Конуэем и получившая популярность благодаря М. Гарднеру. В классическом варианте игры использовались правила: если ячейка имеет двух «живых» соседей, она сохраняет состояние. Если ячейка имеет трёх «живых» соседей, она переходит в «живое» состояние, в остальных случаях клетка «умирает». Несмотря на свою простоту, клеточный автомат показал огромное разнообразие типов эволюций, лежащих между хаосом и порядком. Одним из эффектов, проявившихся в игре-модели, является возникновение сочетаний ячеек, названных глайдерами и движущихся как единое целое по двумерной сетке. Доказана возможность построения сеточного автомата, в котором с помощью глайдеров выполняются вычисления. В 1969 г. К. Цузе опубликовал «Вычислимый космос» – первую книгу из области «цифровой физики» (Zuse. 1969). В книге делается попытка обоснования дискретности самой природы физических законов и утверждается, что вся Вселенная является гигантским многомерным клеточным автоматом. В качестве физической реализация клеточных автоматов разработаны проекты специализированных вычислительных устройств, в которых процессорные элементы размещены в однотипных ячейках равномерной сетки. Состояния процессорных элементов определяются взаимодействием со смежными ячейками из окрестностей Неймана или Мура. Однородные вычислительные среды, систолические матрицы из одноразрядных ячеек Гилда, используемые при проектировании сверхбольших интегральных схем, можно рассматривать с позиций клеточных автоматов, в которых взаимодействие ячеек реализовано различными способами передачи информации, а не только электрическими соединениями.

В 1987 г. Б. Силверман предложил клеточный автомат Wireworld. В 2002 г. П. Чапман построил образец игры «Жизнь», который является Регистровой машиной Минского (РММ, автор – М. Л. Минский). Фактически РММ эквивалентна машине Тьюринга. Первая версия образца была большой (268 096 живых ячеек на площади 4558 x 21 469) и медленной (20 поколений в секунду при использовании программы Life32 на процессоре AMD K6-2 400). Таким образом, в игре «Жизнь» можно выполнить любой алгоритм, который можно реализовать на современном компьютере.