Определение клеточного автомата

Клеточные автоматы были предложены в работе фон Неймана. Большой ин­терес к ним связан с тем, что автоматы этого класса являются универсальной моделью параллельных вычислений, также как машины Тьюринга являются аналогичной моделью для последовательных вычислений.

Клеточный автомат - дискретная динамическая система, представляющая собой совокупность одинаковых клеток, одинаковым образом соединенных между со­бой. Все клетки образуют, так называемую, решетку клеточного автомата. Ре­шетки могут быть разных типов, отличаясь как по размерности, так и по форме клеток.

Каждая клетка является конечным автоматом, состояния которого определяют­ся состояниями соседних клеток и, возможно, ее собственным состояниям.

Отметим, что в клеточных автоматах, как моделях вычислений, не рассматри­ваются входные и выходные воздействия. При аппаратной реализации клеточ­ные автоматы обычно называют однородными структурами.

Клеточные автоматы в общем случае характеризуются следующими свойства­ми.

Изменения значений всех клеток происходят одновременно после вы­числения нового состояния каждой клетки решетки.

Решетка однородна. Невозможно отличить никакие два места на решетке по ландшафту.

Взаимодействия локальны. Лишь клетки окрестности (как правило, сосед­ние) способны повлиять на данную клетку.

Множество состояний клетки конечно.

Итак, клеточный автомат A представляет собой четвёрку объектов {G, Z, N, f}, где Ø G –дискретное метрическое множество, решётка автомата. Наличие метрики позволяет гарантировать, что все клетки окрестности будут на конечном расстоянии от данной, так как ни для какой метрики никакие две точки дискретного метрического пространства не могут быть бесконечно удалены друг от друга. Кроме того, понятие метрики и координаты клетки оказывается чрезвычайно полезным при определении и нахождении окрестных клеток, а также анализе происходящего на решётке. Как правило, пространство G является одно-, двух- или трёхмерным, однако оно может быть и большей размерности;

Ø Z – конечное множество возможных состояний клеток. Можно написать, что состояние решётки является элементом множества Z|G|;

Ø N – конечное множество, определяющее окрестность клетки, то есть, те |N| клеток, которые влияют на новое состояние данной. Его можно задать, например, как множество относительных смещений (в текущей метрике) от данной клетки, позволяющее найти элементы окрестности;

Ø f – правила автомата. Они представляют собой вычислимую программу, которая, используя |N|+1 аргумент для автомата с клетками с памятью и |N| аргументов для автомата с клетками без памяти, позволяет вычислять новое состояние данной клетки. Иногда правила могут быть записаны, как логическая или математическая функция переходов, действующая Z×Z|N|

® Z для автомата с клетками с памятью и Z|N|

® Z для автомата с клетками без памяти.

Автомат, определённый таким образом, обладает всеми свойствами классических клеточных автоматов:

1. Локальность правил взаимодействия обеспечивается конечностью |N| и дискретностью G;

2.Однородность обеспечивается единственностью определения окрестности N, множества значений Z и правил f;

3. Число возможных состояний каждой клетки конечно по определению множества Z;

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

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

Как отмечалось выше, при решении задач, возникает необходимость отказаться от последних трёх свойств классической модели.

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

Пусть UniiZ Z1 == (где Zi – дизъюнктны) и по принадлежности состояния клетки тому или иному Zi они и будут классифицироваться по областям. Пусть внутри каждой из них новые состояния клеток будут вычисляться по правилам f i, учитывая клетки окрестности, определённые с помощью N i. Тогда, можно записать UniiN N1 ==, что не нарушит конечности множества N, а f=f i, если состояние клетки, для которой вычисляется новое значение, принадлежит Zi. Однако теперь при вычислении f могут быть использованы не все клетки окрестности N. Таким образом, нарушение второго свойства на практике, не ведёт к его нарушению в теории.

Необходимость выйти за ограничения, накладываемые третьим свойством, чаще всего возникает при использовании в качестве значений, размещаемых в клетках, чисел с плавающей точкой. Если хранить их не в переменных стандартных типов данных (например, float или double [12]), а в виде последовательность цифр с произвольной точностью. Это не нарушит работу модели, если правила f при этом останутся вычислимыми.

Как правило, время получения нового состояния клетки останется конечным, либо если правила f только преобразуют значения из клеток, не классифицируя их по принадлежности некоторым множествам, либо если они учитывают принадлежность значений из клеток только конечному множеству множеств (то есть, если можно разбить множество возможных состояний клетки на конечный набор дизъюнктных множеств UniiZ Z1 == и в правилах проверять значение состояния обрабатываемой клетки на принадлежность Zi, а не на равенство каждому элементу бесконечного множества Z).

Возможность отказаться от четвёртого свойства позволяет существенно повысить

производительность системы и вдвое уменьшить затраты памяти, так как при этом не

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

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