Определение понятия дискретный аттрактор

Дискретный аттрактор — это устройство, на вход которого подаются данные (возможно, сопровождаемые функциональными полями); к этим данным применяется некоторое преобразование F (а также и к функциональным полям — соответствующее правило). Выходные данные снова могут стать входными, а могут и восприниматься как конечный результат. Данные эти представляются в строго определённой форме (определённой разрядности).

Схематично это описывается так:

Начальные входные данные a₀ после преобразования F превращаются в a₁; после повторного преобразования уже получившегося результата a₁ получатся данные a₂. Очевидно, что можно построить некоторый граф переходов данных из состояния a₀ в a₁, из a₁ в a₂, и так далее… Этот граф будет называться графом кодовых переходов. Эти понятия разрабатывались в трудах Владимира Игоревича Арнольда.

Данные представляются в виде последовательностей нулей и единиц, число которых равно разрядности регистра. Таким образом, каждому данному соответствует кодовое состояние машинного регистра.

С графом кодовых переходов связано понятие «компонента связности», эти компоненты бывают следующими:

• 1. Цикл. В работах В. И. Арнольда обозначается как O_m, содержит m циклически соединённых вершин.
• 2. Бинарное дерево из 2ⁿ вершин, которое обозначается знаком T₂ⁿ.

Примеры выглядят так:

Все вершины графа кодовых переходов имеют одну и только одну исходящую дугу. Это верно в силу единственности преобразования F. Входящих дуг может быть несколько. Из этого следуют нижеперечисленные типы структур графа кодовых переходов:

1. Полюс. Точка, возвращающаяся сама в себя.

2. Кольцо. Это последовательность из нескольких вершин, отличных от полюса, имеющих по одной входной дуге.

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

4. Дерево. Эта структура отличается от цепи наличием нескольких входящих дуг для одной (или нескольких) из вершин.

5. Розетка. Эта структура состоит из нескольких деревьев (или одиночных вершин, не содержащих входящих дуг), сходящихся не к полюсу, а к кольцу.

Других типов структур нет.

Говоря о дискретном аттракторе, надо сказать и о таком его свойстве, как устойчивость. Под термином «устойчивость» в данном случае подразумевается способность аттрактора при утере каких-либо промежуточных данных восстановить весь цикл. Действительно, если из начальных данных а₀ генерируется последовательность а₁, а₂, а₃…, и при этом пропадает какое-то промежуточное звено, например, а₄, то, имея предыдущие результаты или одни только начальные данные, несложно будет восстановить всю последовательность.

Следующим важным свойством дискретного аттрактора является компрессия. Для того, чтобы воспроизвести весь граф, необходимо хранить в памяти только начальные значения (начальные данные) и функциональное преобразование, применяемое к ним. Примером такой компрессии служат числа Фибоначчи. В этой последовательности существуют лишь два первых числа; каждое же следующее получается путем суммирования двух предыдущих. (Правда, последовательность чисел Фибоначчи не является ограниченной.) таким образом, сам принцип работы дискретного аттрактора позволяет экономить место в памяти.

Если в обыкновенном дискретном аттракторе вместо одного преобразования F проводить с одними и теми же данными разные преобразования F₁, F₂, F₃ и так далее, то получившееся устройство будет называться репеллером. В графе, построенном при помощи репеллера, может нарушиться правило аттрактора «только одна исходящая дуга для каждого из различных чисел»; или же, без нарушения этого правила, в графе будут встречаться повторяющиеся кода. Очевидно, что, если убрать ограничения на разрядность данных (т.е., фактически, ограничение их определённым диапазоном значений), репеллер даёт возможность ветвиться графу практически неограниченно.

Схема репеллера (общий вид):

Схема репеллера (ветвление):

На этом рисунке показано, что данные после преобразований могут совпадать с данными, уже возникшими ранее.