Рассмотреть те же вопросы для случая произвольного линейного оператора

2.                Рассмотреть те же вопросы для случая произвольного линейного оператора.

§2 Структура графа состояний для линейного оператора над Z_p

Введение

Рассмотрим множество  и линейный оператор  такое, что 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, находящихся на одном ярусе какого-то дерева, для которых выполняется условие:

верно равенство:

,

где ―одна из последовательностей «нулевого» дерева на n-ном ярусе (сумма в поле ) (Следует из теоремы 2.1).

Используя полученное соотношение можно достроить любое дерево до дерева изоморфного «нулевому».

§3 ACS-автомат §3.1 Постановка задачи

В данной работе рассматривается клеточный автомат (одномерный), функционирование которого осуществляется по следующим правилам:

Дана полоска 1n (сам автомат), все клетки, которой находятся в состояниях «0» и «1». Изменение состояния клетки определяется следующим образом: данная клетка переходит в состояние «1», если её соседи находятся в разных состояниях, и в «0»,если её соседи находятся в одинаковых состояниях. Клетки, находящиеся по краям переходят в то же состояние, которое было у единственной соседней клетки в предыдущий момент времени.

По полоске длины n будем определять вектор , где :

Рассмотрим множество  и отображение  такое, что

(здесь и ниже  – операция сложения по mod p=2, т.е. операция сложения в поле Z₂).

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

Для начала рассмотрим некоторые определения и обозначения, которые будут использоваться в дальнейшем в работе:

·                   Ориентированное дерево — это ориентированный граф без циклов, в котором из каждой вершины, кроме одной, называемой корнем ориентированного дерева, выходит ровно одно ребро (более подробно структуры дерева будет определена позже).

·                   m-й ярус – множество вершин дерева, находящихся на расстоянии m от корня.

·                   Частичный порядок на вершинах: , если вершины u и v различны и вершина u лежит на единственном элементарном пути, соединяющем вершиной v с корнем дерева.

·                   Корневое поддерево с корнем v — подграф .

·                   Множество  назовем множеством висячих вершин графа .

§3.2 Краткий обзор предыдущих результатов

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

Утверждение 3.2.1

.

Утверждение 3.2.2

 

1. ;

2. , причем  

3. ;

4. .

 

Утверждение 3.2.3

 

;  и .

Предисловие

В параграфе будет рассказано о свойствах графа состояний оператора j, а именно будет описана его структура.

  §3.3 Структура G_j при p=2 §3.3.1 Исследование структуры

Пользуясь утверждением 3.2.2, мы получаем, что среди всех последовательностей можно выделить следующие: