1.3 Двумерный клеточный автомат

Клеточный автомат (КА) может быть описан с помощью определения следующих основных свойств: окрестности, количества состояний КА, функции, с помощью которой клеточный автомат вычисляет свое последующее состояние (в дальнейшем - правило). Варьируя эти свойства можно получить широкий спектр КА.

В данной работе рассматривается одномерная сеть клеточных автоматов (СКА), любой из которых может иметь два состояния "О" или "1" на каждом такте функционирования сети. Окрестность определяется множеством соседних клеток, от состояния которых зависит последующее состояние данной клетки, а также диапазоном правил, используемых при настройке КА. Впервые определение окрестности было дано Фон Нейманом [4]. Окрестность Фон Неймана включает наиболее близко расположенные физически соседние клетки.

Рассмотрим клеточные автоматы с двумерными решётками из правильных многоугольников, которые встречаются на практике чаще всего. Возможны всего три таких решётки: треугольная (рис.1.1), квадратная (рис.1.2) и гексагональная (рис.1.3). Ниже последнее утверждение будет доказано.

Рисунок 1.1 - Треугольная решетка клеточного автомата

Рисунок 1.2 - Квадратная решетка клеточного автомата

Рисунок 1.3 - Гексагональная решетка клеточного автомата

Теорема 1. Не существует другой решётки из правильных многоугольников, кроме треугольной, квадратной и гексагональной.

Доказательство:

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

Будем рассматривать эту функцию только при n?3, так как треугольник - многоугольник с наименьшим количеством вершин. Возьмем производную от k (n) по n:

Очевидно, что при n?3 функция k (n) убывает, так как . Таким образом, все возможные значения k меньше k (3), то есть шести. К тому же, k (n) > 2, так как

- истинно.

Решётку можно построить, только если целому n будет соответствовать целое k. Из изложенного выше следует, что возможны лишь четыре значения k: 6, 5, 4 и 3. Построим функцию n (k), обратную к k (n), и проверим, каким из возможных значений k соответствует целое n:

Имеем:

- треугольная решётка;

- не целое n, то есть решётку не построить;

- квадратная решётка;

- гексагональная решётка;

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

В нашем случае, окрестность Фон Неймана включает три соседние клетки. В дальнейшем, если рассматривается СКА без специально определенных свойств, имеется в виду одномерная СКА, состоящая из КА, которые имеют два состояния, с взаимосвязями между клетками, определенными для окрестности Фон Неймана.

На рис.1.4 показана структура одномерной линейной СКА, длинны n, с нулевыми граничными условиями.

Рисунок 1.4 - Одномерная n-клеточная СКА с нулевыми граничными условиями

Каждая ячейка СКА - КА, имеющий два состояния, структура которого представлена на рис.1.5.

Рисунок 1.5 - Структура КА

Ячейка состоит из двух основных блоков: элемента памяти на триггере типа D и комбинационной схемы, реализующей функцию возбуждения триггера F. Обозначим текущее состояние i-й ячейки СКА в момент времени t как , тогда последующее состояние определяется выражением:

где F - функция возбужден ил триггера, называемая правилом поведения клеточного автомата.

Правило может быть представлено и виде логической функции, либо таблицей истинности, либо как десятичный эквивалент двоичного числа (0.255), образуемого значениями функции и таблице истинности. В таблице 2.1 представлен пример численного значения правила

Таблица 1.1 - Пример вычисления численного значения правила

Правило 144 = 2⁷ + 2⁴

Правило 65 = 2⁶ + 2¹

Аналогично вычисляется численное значение для любого правила.

Правило функционирования КА может быть записано в виде булевого выражения. Например, для правила 144, соответствующее выражение будет иметь вид:

где x и + операции конъюнкции и дизъюнкции соответственно.

Определение 1. Диаграмма состояний КА.

Диаграмма состояний КА с двумя состояниями представляет собой вектор-столбец, состоящий из нулей и единиц. Обозначим состояние i-й ячейки в момент времени t - , тогда диаграмма состояний i-клетки за m-шагов может быть записана в виде:

где Т - оператор транспонирования матрицы

Определение 2. Диаграмма состояний ячейки СКА.

Диаграмма состояний ячейки, входящей в состав одномерной СКА записывается в виде матрицы, состоящей из трех столбцов (Х_i-1, X_i, X_i+1). Х_i - диаграмма на выходе интересующей ячейки, а Х_i-1, X_i+1 - диаграммы на выходах левой и правой ячеек соответственно.

Определение 3. Диаграмма состояний СКА.

Диаграмма состояний СКА длины n может быть записана в виде совокупности из n триплет

Каждая совокупность из трех столбцов (Х_i-1, Х_i Х_i+1) представляет диаграмму состояний i-й ячейки сети. Нужно заметить, что столбцы Х₀ и Х_n+1 - это столбцы, состоящие из нулей. Эти столбцы соответствуют нулевым граничным условиям.

Определение 4. Детерминизм правил КА.

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

Обозначим состояние окрестности i-й ячейки СКА на шаге t, как

(1.1)

Рассмотрим состояние i - ячейки СКА на шаге t_j и t_k, t_j?t_k, если

(1.2)

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

Определение 5. Универсальная окрестность.

Запишем:

где F представляет правило функционирования КА, а - это состояние окрестности i-й ячейки СКА в момент времени t. Параметр r - это положительное целое число, характеризующее размер окрестности, а, следовательно, и диапазон правил КА [5].

Универсальная окрестность, , ячейки x_i, в одномерной СКА длинны n, может быть представлена в следующем виде:

Таким образом, окрестность Фон Неймана является частным случаем универсальной окрестности.

На рис.1.6 показаны два варианта окрестности с г = 1 и г = 2. Как можно заметить, при r =1, на последующее состояние ячейки влияет три переменные, а при r =2 - пять.

Рисунок 1.6 - Универсальная окрестность с r=1 и r=2

Окрестность определяется диапазоном правил КА [6] в зависимости от параметра r следующим образом , где (2r+1) - количество соседних с рассматриваемой ячеек, участвующих в вычислении последующего.

Окрестность Фон Неймана, рассматриваемая в данной работе, позволяет использовать =256 правил. Этот класс КА называют "элементарный КА Вольфрама" [6].

Диаграмма состояний ячейки СКА с универсальной окрестностью состоит из совокупности (2г+1) столбцов (Х_i-r,.,X_i,… X_i+r), где - диаграмма состояний КА. При этом столбцы (X_-r+1, X_-r+2,…, X₀) и (X_n+1, X_n+2,…, X_n+r) обеспечивают заданные граничные условия.

Увеличение r > 1 и, следовательно, расширение окрестности влечет за собой ряд проблем, одна из которых состоит в кодировании правил, возможное число которых значительно возрастает, в этом случае правила рассматриваются в виде таблицы истинности и соответствующей логической функции. Кроме того, из-за такого расширения окрестности значительно усложняется проектирование СКА с заданными свойствами.

Определение 6. Детерминированность субпоследовательности.

Детерминированность для субпоследовательности S, состоящей из k строк, длины n, на основании (2.1) можно сформулировать следующим образом:

пусть - i-й элемент строки t, тогда субпоследовательность (СП) детерминирована, если

, выполняется (1.2) (1.3)