Аннотация:
Последовательность 001001001001 проще, чем 010010111001. Будет рассказана формальная теория, придающая этому высказыванию точный смысл.
Пусть $x$ — замкнутая последовательность $n$ нулей и единиц (за $n$-ым элементом опять следует первый). Множество $M$ всех $2^n$ таких последовательностей есть множество вершин $n$-мерного куба (и $n$-мерное векторное пространство над $Z_2$). Определим операцию $A\colon M\to M$ как переход от $x$ к последовательности разностей ($\mod 2$) соседних элементов из $x$. Динамическая система $A$ задается направленным графом с $2^n$ вершинами. Из каждой вершины $x$ выходит ровно одно ребро (ведущее в $Ax$). Сложность последовательности $x$ определяется числом и периодами аттракторов динамической системы $A$, лесами притягиваемых ими деревьев и положением точки $x$ в этих лесах. При $n=11$ аттракторов 4, и 3 из них имеют период 341, а один — период 1. Каждое дерево леса имеет здесь 2 вершины: x—x, доставляя $2(3\cdot 341+1)=2^{11}$ вершин. При $n=12$ аттракторов 24. из них 20 имеют периодом 12, 2 аттрактора имеют период 6, один — период 1. Каждое дерево леса имеет здесь 16 вершин. Зависимость сложности динамики $A$ от числа $n$ представляется загадочной и никакие асимптотики неизвестны. Многочлены $x$ степени меньше $k$ выделяются по (Ньютону) условием $A^kx=0$. В графе системы $A$ эти вершины образуют дерево, притягиваемое аттрактором $x=0$. Многочленов мало. Большинство точек $x$ сложнее всех многочленов. Примером сложной функции кажется теоретико-числовой логарифм: соответствующая ему точка притягивается к самому длинному циклу и лежит далеко от корня притягивающегося дерева системы $A$.
|
