MMOnline – Информационный портал о мехмате МГУ


Этот материал доступен в сети по адресу:
http://www.mmonline.ru/message/5336/


16.11.05 19:19  Заседание Московского Математического Общества 22 ноября 2005 г.

Заседание Московского Математического Общества 22 ноября 2005 г.
(начало в 18 час. 10 мин., ауд.16–24 Главного здания МГУ)

В.И. Арнольд.
Сложности конечных последовательностей нулей и единиц.

Последовательность 001001001001 проще, чем 010010111001. Будет рассказана формальная теория, придающая этому высказыванию точный смысл. Пусть $x$ – замкнутая последовательность $n$ нулей и единиц (за $n$-ым элементом опять следует первый). Множество $M$ всех $2^n$ таких последовательностей есть множество вершин $n$-мерного куба (и $n$-мерное векторное пространство над $Z_2$).

Определим операцию $A:M\to M$ как переход от $x$ к последовательности разностей ($\mbox{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$.


Московское Математическое Общество


Copyright © 2000−2021 MMOnline.Ru | http://www.mmonline.ru/