On algorithmic and topological properties of orbits for piecewise-affine mappings.pdf При исследовании непрерывных динамических систем наряду с методами теории динамического хаоса, определяющими, например, такие свойства, как эргодичность, перемешивание, топологическая транзитивность и устойчивость, применение методов теории алгоритмов представляется также интересным и, главное, естественным и полезным с точки зрения приложения теории детерминированного хаоса в задачах криптографической защиты информации. Параллели между хаотическими и криптографическими системами мотивируют исследования в области применения дискретных аналогов непрерывных хаотических систем в задачах криптографического преобразования информации [1]. Однако математические связи относящихся к делу свойств дискретных систем и их непрерывных прототипов скорее находятся на уровне взаимосвязи узелков на память и запоминаемых фактов. В связи с этим на стыке теории динамических систем и теории алгоритмов представляет интерес фундаментальная проблема вычислительной универсальности непрерывных динамических систем и тесно с ней связанная проблема достижимости. Динамическая система является вычислительно универсальной, если существует интерпретация поведения системы, при которой моделируется машина Тьюринга. Проблему достижимости можно сформулировать так: существует ли для данной системы алгоритм, определяющий по данным точкам или областям фазового пространства, проходит ли через них одна и та же фазовая кривая. Непрерывные хаотические динамические системы показывают сложное поведение, позволяющее предполагать для некоторых из них алгоритмическую неразрешимость проблемы достижимости из точки точки. До сих пор единственным способом доказательства алгоритмической неразрешимости является моделирование с помощью изучаемой системы универсальной машины Тьюринга. Публикации показывают в какой-то мере безуспешный поиск таких доказательств для различных непрерывных динамических систем. В связи с этим представляет интерес исследование вычислительной универсальности гибридных дискретно-непрерывных систем и систем с дискретным временем. Примеры таких исследований можно найти в [2]. На практике оказывается, что чем выше размерность фазового пространства, тем проще доказать универсальность системы. Поэтому представляют интерес системы низкой размерности. Например, в [3] для одномерных кусочно-элементарных отображений в базисе функций [x2 , xx> , xx> / , 'x 1/3, 2x, x + 1, x - 1}, а также дробно-рациональных функций доказана алгоритмическая неразрешимость достижимости из точки точки. При этом уже долгое время остается открытой проблема достижимости в одномерных кусочно-аффинных отображениях [3] даже в простейшем случае двух интервалов. Настоящая работа посвящена кусочно-аффинным отображениям с двумя интервалами (2-РАМ'ам). Не ясно, влечёт ли сопряжённость двух систем их эквивалентность с точки зрения проблемы достижимости. Во всяком случае, ответ на этот вопрос не очевиден. Поэтому, имея в виду как гипотезу алгоритмическую разрешимость проблемы достижимости в 2-РАМ, имеет смысл находить связи топологических и алгоритмических свойств орбит и проводить соответствующую классификацию систем. Например, если для динамической системы доказано свойство перемешивания или эргодичности, то проблема достижимости измеримой области (ненулевой меры) фазового пространства становится, очевидно, тривиальной. Пример менее тривиального утверждения приведён ниже. Пусть X — отрезок [0,1] с отождествленными концами, т.е. X = R/Z, и отображение f : X ^ X таково, что X = X1 U X2 — разбиение на непересекающиеся интервалы и f (x) = aix + bi, если x G Xi; ai,bi G Q, i = 1,2. Обозначим через f* (x) = [fn (x) : n G N} орбиту точки x. Проблема достижимости из точки точки звучит так: существует ли алгоритм, определяющий по произвольным точкам xo,xi Е X принадлежность xi Е f*(xo). Ограничимся рассмотрением только рациональных точек X по следующим соображениям. Кусочно-аффинное отображение f (x) = 2x (mod 1) является хаотическим для почти всех x Е X. Но ни одно число этого множества почти всех из X не представимо на компьютере, если под числом не понимать алгоритм, его порождающий. Если же под числом понимать произвольный порождающий его алгоритм, проблема достижимости для f (x) оказывается тривиально алгоритмически неразрешимой в общем случае, несмотря на то, что отображение очень простое. Стоит при этом заметить, что некоторые сопряжённые f (x) отображения показывают хаотическое поведение на множестве рациональных точек. Теорема 1. Если f строго эргодическое, т.е. имеет единственную инвариантную меру, или, другими словами, плотности распределения орбит всех точек совпадают, то проблема достижимости алгоритмически разрешима. Следствие 1. Если пространство инвариантных мер конечномерно, то проблема достижимости алгоритмически разрешима.

Скачать электронную версию публикации