Реферат: Структура графа состояний клеточных автоматов определённого типа
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).
Теорема 3.4.0
Вершина 
является висячей тогда и только тогда, когда n – нечётное и выполняется условие: