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

то , ч.т.д.

Теперь покажем, что это наименьший период, если , наименьший период должен быть делителем числа pk, поэтому мы проверим, что pk-1 – не период.

Докажем, что при число сочетаний dth=61 height=29 src="images/referats/1519/image176.gif">, действительно, пусть j= i-(p-1)pk-1, тогда . Тогда, т.к.:

,

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

С другой стороны , поэтому число pk-1 не является периодом функции

(mod p) по переменной 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-автомата и ) если длину последовательности представить в виде: где , .

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