Реферат: Структура графа состояний клеточных автоматов определённого типа

Рассмотрим множество и линейный оператор такое, что y – линейный оператор над полем Z_p , в частности, этот оператор может задавать изменение состояния некоторого одномерного клеточного автомата с p состояниями.

Будем рассматривать граф состояний , для которого . Основной целью исследования является изучение структуры графа .

Одним из важных свойств оператора y, которое будет использоваться в дальнейшем, является его аддитивность:

Для исследования структуры графа G_y рассмотрим следующую нумерацию вершин нулевого дерева (см. рис. 2.1).

– вершина, находящаяся на m ярусе, при этом она входит в

(), смысл этих обозначений станет ясным позже. Важно то, что в этих обозначениях в вершину входят , при этом вершины входят в (в нашем случае.

Рис. 2.1

Теорема 2.1

Пусть задана цепь: тогда .

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

Воспользуемся методом математической индукции.

База m=1:

, действительно причем различные вершины, ч.т.д.

Пусть теорема верна для m = l-1, т.е.

Докажем, что Тем, самым, по построению , мы покажем, что .

Действительно, в силу линейности:

Теорема 2.1 доказана.

Назовем дерево с корнем e_n = (0,0,…,0) – «нулевым» деревом, тогда для него верна следующая теорема.

Теорема 2.2

«Нулевое» дерево – p-нарное дерево с точностью до петли в корне (0,0..,0).

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

По теореме 2.1 единственная цепь из висячей вершины в (0,0,..0) однозначным образом определяет все элементы дерева (различность определяемых вершин очевидна, и следует из простоты p).

Теорема 2.3

Каждое дерево притягиваемого каждой точкой каждого цикла графа G_y изоморфно нулевому» дереву.

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

Для любых последовательностей k и l, находящихся на одном ярусе какого-то дерева, для которых выполняется условие: