*/

Клеточным автоматом (КА) [84, 85] называют множество одинаковых конечных автоматов [87 – 95], локально связанных между собой, работающих синхронно. Конечные автоматы, из которых состоит КА, называют элементарными автоматами или клетками. Конечным автоматом без выходов называется тройка объектов A = Q, S, δ, где Q – входной алфавит, S – алфавит внутренних состояний, δ: Q × S → S – функция переходов автомата. На каждом такте он переходит из состояния s  S в новое состояние s´  S согласно функции переходов s´ = δ(q, s), где q  Q – символ входного алфавита, подаваемый на вход автомата. Таким образом, поведение конечного автомата сводится к преобразованию всевозможных последовательностей входных символов q0, q1, q2, … в последовательности внутренних состояний s0, s1, s2, … Конечный автомат называется детерминированным, если его функция переходов δ детерминирована. В противном случае автомат называется вероятностным [96, 97]. Обычно функцию переходов δ задают в виде таблицы, называемой таблицей переходов. Размер таблицы переходов, напрямую связанный со сложностью реализации автомата, равен |Q| × |S|, где |Q| и |S| — мощности множеств Q и S соответственно. Для недетерминированного автомата, кроме того, это значение увеличивается во столько раз, сколько допустимо различных вариантов переходов для каждого состояния.

Формально КА определяется как тройка объектов (W, A, N), где W = {w1, w2, … , wi, …} – множество клеток, заданное их координатами в некотором дискретном пространстве. Каждой клетке w  W поставлен в соответствие конечный автомат A, являющийся элементарным автоматом. Для каждой клетки w  W определено некоторое упорядоченное множество N(w)  W, называемое множеством соседних клеток N(w) = {N1(w), N2(w), …, Nl(w), …, Nbm(w)}, элементы которого Nl(w)  W (l = 1, 2, …, bm), находятся в отношении соседства с клеткой w и называются ее соседними клетками. Константа bm определяет количество соседей каждой клетки КА. Входы элементарного автомата A поставлены в соответствие внутренним состояниям его соседей, а его внутренние состояния — входам соседних автоматов. Таким образом, структура множества клеток W клеточного автомата представляется графом, в котором вершинами являются клетки, а ребрами — отношение соседства. Этот граф имеет регулярную структуру и степени вершин равные bm. Состояние клетки w  W представлено булевым вектором s(w) с компонентами s1(w), s2(w), …, sb(w). Множество состояний s(w) всех клеток w  W в один и тот же момент времени t называется глобальным состоянием σ(t) = {s(w1), s(w2), …, s(wi), …} клеточного автомата или его конфигурацией. Множество глобальных состояний КА обозначается ∑.

КА функционирует синхронно и итеративно. На каждой итерации происходит смена состояний s(t) всех элементарных автоматов w  W, на состояния s(t + 1) =  (s(t)), обозначаемые также s´, при этом КА переходит из глобального состояния σ(t) в новое глобальное состояние σ(t + 1). Функция (s(t)) является функцией переходов элементарного автомата. Последовательность глобальных состояний, в которые переходит КА из некоторого начального состояния, называют его эволюцией. Эволюция КА представляется в виде последовательности σ(1), σ(2), …, σ(t), …, где σ(t)  ∑. В зависимости от того, детерминированными или вероятностными являются элементарные автоматы, КА является детерминированным или вероятностным, соответственно. Эволюция детерминированного КА не меняется от запуска к запуску при фиксированном начальном состоянии. Недетерминированный КА при разных запусках проходит разную эволюцию даже из одного и того же начального состояния.