1.1 Основные определения и понятия

Клеточный автомат является дискретной динамической системой, поведение которой полностью определяется в терминах локальных зависимостей [1]. Назовём дискретным пространством пространство над дискретным множеством [2] элементов. Экземпляр пространства этого класса будем называть решёткой клеточного автомата, а каждый его элемент - клеткой. Каждая клетка характеризуется определённым значением из некого множества. О клетке говорят, что она содержит или имеет соответствующее значение, либо находится или пребывает в состоянии, кодируемом данным значением. Оно можем быть булевым, целым, числом с плавающей точкой, множеством или другим объектом, в зависимости от потребностей задачи.

Совокупность состояний всех клеток решётки называется состоянием решётки. Состояние решётки меняется в соответствии с некоторым законом, который называется правилами клеточного автомата. Каждое изменение состояния решётки называется итерацией. Время в рассматриваемой модели дискретно и каждая итерация соответствует некому моменту времени.

Правила определяют, какое значение должно содержаться в клетке в следующий момент времени, в зависимости от значений в некоторых других клетках в текущий момент, а также, возможно, от значения, содержащегося в ней самой в текущий момент. Если новое состояние клетки зависит от текущего её состояния, то о соответствующем клеточном автомате говорят, что он является автоматом с клетками с памятью, иначе - автоматом с клетками без памяти.

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

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

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

Когда описанная процедура будет проделана для всех клеток верхнего листа, те из них, которые слегка выделены, можно пометить окончательно. Дальше эту процедуру можно повторять от листа к листу до тех пор, пока хватит терпения.

Таким образом, можно реализовать клеточный автомат "Жизнь", который обладает множеством интересных свойств и любопытнейшей историей [3].

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