Структура графа состояний клеточных автоматов определённого типа (стр. 4 из 4)
На основе результатов параграфа 2 (теоремы 2.2, 2.3), для анализа структуры графа состояний оператора w достаточно определить высоту нулевого дерева, тем самым будут определена высота дерева притягиваемого каждой точкой каждого цикла графа Gw (теорема 2.3).
Теорема 4.1
Если
, то наименьший период функции 
(modp) по i равен pk.Доказательство
Проверим сначала, что число pk является периодом при
: 
Действительно, т.к.:
,то
, ч.т.д.Теперь покажем, что это наименьший период, если
, наименьший период должен быть делителем числа pk, поэтому мы проверим, что pk-1 – не период.Докажем, что при
число сочетаний 
, действительно, пусть j= i-(p-1)pk-1, тогда 
. Тогда, т.к.: 
,откуда т.к.
и 
, то 
,т.е. , ч.т.д.С другой стороны
, поэтому число pk-1 не является периодом функции 
(modp) по переменной i, когда 
, при этом условии 
.Теорема 4.2
Если длину последовательности представить в виде:
где 
, 
, тогда pk есть высота «нулевого» дерева.Доказательство
Проведем явное интегрирование функции
периода n, т.е. определим a, такое, что j(a) = (1,1,…,1) (строгое определение интегрирования см. в [1])
Рис. 4.1
Легко видеть, что все интегрированные «интегралы» (с начальным условием
при t=1) – это приведенные по модулю p косые линии треугольника Паскаля, на которых j= 0 для исходной функции 
, а затем, по мере повторного «интегрирования», ответы доставляют косые линии с j = 0,1,2… (см рис. 4.1)Следовательно, для выяснения того, сколько раз удастся «проинтегрировать» функцию
(т.е. определить высоту нулевого дерева) в классе n-периодических функций (т.е. в классе n-периодических последовательностей) остается выяснить, при каких значениях j функция 
аргумента i будет иметь период n.В силу теоремы 4.1, если n=
, то построение «нулевого» дерева, описанного выше, будет успешным до тех пор, пока «j-кратные интегралы» 
от функции будут оставаться n-периодическими функциями аргумента i. Но наименьший период указанной функции переменной i равен pr при 
. Чтобы эта функция была n-периодической, необходимо, чтобы число n= делилось на наименьший период, т.е. чтобы 
. Откуда следует, что если длину последовательности представить в виде: n= , тогда pk есть высота «нулевого» дерева, ч.т.д.§5 Перспективы исследования
1. Более подробно исследовать структуру
, а именно:· Определить количество циклов и их длину;
· Описать множество корней деревьев и т.д.
2. Рассмотреть двумерный вариант клеточного автомата (на клеточном прямоугольнике
) с теми же вопросами, т.е. описать структуру графа состояний.3. Более подробно рассмотреть матричную интерпретацию.
4. В связи с использованием одномерных клеточных автоматов, а также линейных операторов, в теории кодирования, найти количественные и качественные характеристики автомата (например, определить коллизии и т.д.).
5. В связи с тем, что некоторые правила «эквивалентны», изучить их относительно данного аспекта (т.е. найти некоторую «совместимость» между правилами). Определить условия эквивалентности правил, найти разбитие на классы эквивалентности. Данная задача является открытой проблемой.
§6 Резюме
Основным предметом исследования являлась рассмотрение структуры графа
, более подробное изучение которой, является одним из наиболее перспективных направлений дальнейшего исследования. В общем случае получена следующая характеристика структуры графа :1. Каждая компонента связности графа
является циклом (возможно длины 1), каждая вершина которого притягивает дерево (возможно нулевой высоты).2.
и 
;3.
;4. «Нулевое» дерево ― p-нарное дерево с точностью до петли в корне en (0,0..0), причем его высота равна
·
(для оператора 
, описывающего функционирование ACS-автомата и 
), если длину последовательности представить в виде 
где , ;·
(для оператора , описывающего функционирование ACS-автомата и 
) если длину последовательности представить в виде: 
где , .5. «Нулевое» дерево ― p-нарное дерево с точностью до петли в корне en (0,0..0), причем его высота равна
(для оператора взятия разности), если длину последовательности представить в виде: где , ;6. Все деревья (в том числе притягиваемые каждой вершиной каждого цикла) будут иметь столько ярусов, сколько и «нулевое», причем будут иметь такую же структуру. Т.е. дерево, притягиваемое каждой точкой каждого цикла графа состояний, изоморфно дереву, притягиваемому точкой en (0,0..0).
Используемые источники. Список использованной литературы
Используемые источники
1. М.С. Глущенко, П.С. Пересторонин, Почти центральная симметрия (доклад на IV Балтийском научно–инженерном конкурсе, Санкт-Петербург, 2008 г.)
2. М.С. Глущенко, П.С. Пересторонин, Почти центральная симметрия (доклад на XII Белорусской республиканской конференции учащихся общеобразовательных учреждений, Минск, 2008 г.)
Список использованной литературы
1. В.И. Арнольд, Сложность конечных последовательностей нулей и единиц и геометрия конечных функциональных пространств (из доклада Московскому математическому Обществу 22 ноября 2005 г.)
2. В.И. Арнольд, Топология и статистика арифметических и алгебраических формул, Успехи математических наук 58(2003), №4, 3-28