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

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

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

1. m = 1:

Пусть , тогда . Тогда, учитывая утверждение 1.1, и , по

лучим требуемое.

2. Пусть утверждение леммы верно для m = k, тогда:

3. Докажем теорему для m = k+1.

Мы имеем: , тогда:

Если и , то:

Из утверждения 3.2.1:

, но , т.е. , откуда , ч.т.д.

Теорема 3.3.1.3

«Нулевое» дерево ― бинарное дерево с точностью до петли в корне en.

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

Теорема 3.3.1.4

Все деревья (в том числе и примыкающие к каждой вершине произвольного цикла) будут иметь столько ярусов, сколько и «нулевое», причем будут иметь такую же структуру.

Более точно: дерево, притягиваемое каждой точкой каждого цикла графа состояний, изоморфно дереву, притягиваемому точкой en.

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

Предположим «нулевое» дерево состоит из n ярусов тогда:

1. Если наше дерево состоит менее чем из n ярусов, то, пользуясь теоремой 3.3.1.2, мы восстанавливаем его до дерева изоморфного «нулевому».

2. Если дерево имеет m ярусов, где n<m тогда , получается, что «нулевое» дерево состоит из m ярусов Ї противоречие.

§3.3.2 Исследование высоты деревьев

Теорема 3.3.2.1

Если длина последовательности равна 2k-1, то высота деревьев будет равна 2k-1.

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

Пример для k=1 и k=2 строятся довольно просто:

k=1 k=2

0 (1) 0 0 (1,0,0) 0

0 (0) 0 0 (0,1,0) 0

0 (1,0,1) 0

0 (0,0,0) 0

Докажем по индукции

1. База индукции:

Пусть k=3, тогда:

0 (1,0,0,0,0,0,0) 0

0 (0,1,0,0,0,0,0) 0

0 (1,0,1,0,0,0,0) 0

0 (0,0,0,1,0,0,0) 0

0 (0,0,1,0,1,0,0) 0

0 (0,1,0,0,0,1,0) 0

0 (1,0,1,0,1,0,1) 0

0 (0,0,0,0,0,0,0) 0

Высота дерева равна 2k=7.

2. Пусть утверждение верно для n=k, тогда докажем его для n=k+1:

;

тогда:

Так как -й элемент равен «0» и остальные элементы симметричны относительно его, то в каждом последующем поколении этот элемент будет равен «0», следовательно, правая и левая части перейдут в состояние (0,0,…,0) через 2k поколений. Таким образом, высота дерева будет 2k +2k-1=2k+1-1=2n-1 ч.т.д.

Теорема 3.3.2.2

Если длину последовательности представить в виде где , тогда 2k-1 Ї высота «нулевого» дерева.

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

По теореме 3.3.2.1 , где с корнем .

Возьмем последовательность длиной ;

заметим, что тогда:

(в связи с симметрией относительно )

Но тогда:

Высота дерева при n=2n-1 равна высоте дерева при n=3×2n-1. В связи с симметрией относительно , мы получаем:

Высота дерева при n=2n+1+2n-1-1 равна высоте дерева при n=3×2n-1-1.

Таким образом, мы получаем, что если представить длины последовательности в виде: , то 2-1k Ї высота дерева.

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

§3.4 Структура Gj при p¹2

Введение

В параграфе 2 мы рассматривали структуру графа состояний для произвольного линейного оператора над Zp. В данном параграфе пойдет речь о структуре графа Gj определенного в параграфе 3.1. По аналогии со случаем p=2, по состоянию числовой полоски длины n (т.е. самого автомата с состояниями 0,1, p-1) будем определять вектор, и рассматривать такое, что:

Все остальные основные определения вводятся аналогичным образом, как и в случае p=2, основным предметом исследования является структура графа Gj.

Одним из важных свойств оператора j является его аддитивность:

которая следует из линейности оператора j.

В предыдущем параграфе было доказано утверждение о том, что для произвольного линейного оператора y «нулевое» дерево – p-нарное дерево с точностью до петли в корне (0,0 ,0) (теорема 2.2). В данном параграфе будет определена высота нулевого дерева, тем самым будут определена высота дерева притягиваемого каждой точкой каждого цикла графа Gj (теорема 2.3).

 Скачать реферат