Алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях

Рассматривается открытая проблема достижимости в одномерных кусочно-аффинных отображениях с двумя интервалами. Найдены частные случаи алгоритмической разрешимости рассматриваемой проблемы, сформулированные на языке топологических свойств орбит в таких системах....

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2013
Автор:	Курганский, А.Н.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут прикладної математики і механіки НАН України 2013
Назва видання:	Труды Института прикладной математики и механики
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/124195
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях / А.Н. Курганский // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2013. — Т. 27. — С. 191-198. — Бібліогр.: 9 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-124195
record_format	dspace
spelling	irk-123456789-1241952017-09-23T03:03:44Z Алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях Курганский, А.Н. Рассматривается открытая проблема достижимости в одномерных кусочно-аффинных отображениях с двумя интервалами. Найдены частные случаи алгоритмической разрешимости рассматриваемой проблемы, сформулированные на языке топологических свойств орбит в таких системах. Розглянуто вiдкриту проблему досяжностi в одновимiрних кусково-афiнних вiдображеннях з двома iнтервалами. Знайдено окремi випадки алгоритмiчної розв’язностi цiєї проблеми, якi сформульованi на мовi топологiчних властивостей орбiт у таких системах. We consider the open reachability problem for one dimensional piecewise-affine mappings with two intervals (2-PAM). We give some decidable results following from specific topological properties of reachable states of the 2-PAM’s. 2013 Article Алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях / А.Н. Курганский // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2013. — Т. 27. — С. 191-198. — Бібліогр.: 9 назв. — рос. 1683-4720 http://dspace.nbuv.gov.ua/handle/123456789/124195 519.7 ru Труды Института прикладной математики и механики Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
description	Рассматривается открытая проблема достижимости в одномерных кусочно-аффинных отображениях с двумя интервалами. Найдены частные случаи алгоритмической разрешимости рассматриваемой проблемы, сформулированные на языке топологических свойств орбит в таких системах.
format	Article
author	Курганский, А.Н.
spellingShingle	Курганский, А.Н. Алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях Труды Института прикладной математики и механики
author_facet	Курганский, А.Н.
author_sort	Курганский, А.Н.
title	Алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях
title_short	Алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях
title_full	Алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях
title_fullStr	Алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях
title_full_unstemmed	Алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях
title_sort	алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2013
url	http://dspace.nbuv.gov.ua/handle/123456789/124195
citation_txt	Алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях / А.Н. Курганский // Труды Института прикладной математики и механики НАН Украины. — Донецьк: ІПММ НАН України, 2013. — Т. 27. — С. 191-198. — Бібліогр.: 9 назв. — рос.
series	Труды Института прикладной математики и механики
work_keys_str_mv	AT kurganskijan algoritmičeskaâproblemadostižimostiv1mernyh2intervalʹnyhkusočnoaffinnyhotobraženiâh
first_indexed	2025-07-09T01:00:35Z
last_indexed	2025-07-09T01:00:35Z
_version_	1837129099889344512
fulltext	ISSN 1683-4720 Труды ИПММ НАН Украины. 2013. Том 27 УДК 519.7 c©2013. А.Н. Курганский АЛГОРИТМИЧЕСКАЯ ПРОБЛЕМА ДОСТИЖИМОСТИ В 1-МЕРНЫХ 2-ИНТЕРВАЛЬНЫХ КУСОЧНО-АФФИННЫХ ОТОБРАЖЕНИЯХ Рассматривается открытая проблема достижимости в одномерных кусочно-аффинных отображе- ниях с двумя интервалами. Найдены частные случаи алгоритмической разрешимости рассматри- ваемой проблемы, сформулированные на языке топологических свойств орбит в таких системах. Ключевые слова: кусочно-аффинные отображения, проблема достижимости. 1. Введение. При исследовании непрерывных динамических систем наряду с методами теории динамического хаоса, определяющими такие свойства, как эрго- дичность, перемешивание, топологическая транзитивность, устойчивость и т.д., при- менение методов теории алгоритмов представляется также интересным и, главное, естественным и полезным с точки зрения приложения теории детерминированного хаоса в задачах криптографической защиты информации. Аналогии или проводи- мые параллели между хаотическими и криптографическими системами мотивируют исследования в области применения дискретных аналогов непрерывных хаотиче- ских систем в задачах криптографического преобразования информации [1, 2, 3, 4]. Однако, математические связи относящихся к делу свойств дискретных систем и их непрерывных прототипов скорее находятся на уровне взаимосвязи узелков на память и запоминаемых фактов. Поэтому поиск таких способов перехода от непре- рывных систем к их дискретным аналогам, при которых существует математическая взаимосвязь хаотического поведения первых с алгоритмическими свойствами вто- рых, является фундаментальной проблемой. В связи с этим приобретает значение изучение алгоритмических свойств и вы- числительных возможностей самих непрерывных хаотических систем. И, таким об- разом, в частности, на стыке теории динамических систем и теории алгоритмов возникает проблема вычислительной универсальности непрерывных динамических систем и тесно с ней связанная проблема достижимости. Близкий к теме обзор по вы- числительным системам с непрерывным временем см. [5]. Там же обращается внима- ние на сложность понимания уже самого понятия вычислительной универсальности непрерывной динамической системы, хотя ясно в общих чертах, что вычислительная универсальность системы связана с подходящей алгоритмической интерпретацией поведения системы, при которой моделируется машина Тьюринга. Пример исследо- вания в области определения универсальных вычислительных систем можно найти в [6]. Проблема достижимости формулируется как вопрос: существует ли для данной системы алгоритм, определяющий по любым данным точкам или областям фазово- го пространства проходит ли через них одна и та же фазовая кривая или орбита системы? 191 А.Н. Курганский Непрерывные хаотические динамические системы показывают сложное поведе- ние, позволяющее предполагать для некоторых из них алгоритмическую неразре- шимость проблемы достижимости из точки точки. До сих пор единственным спо- собом доказательства алгоритмической неразрешимости является моделирование с помощью изучаемой системы универсальной машины Тьюринга. Публикации по- казывают в какой-то мере безуспешный поиск таких доказательств для различных непрерывных динамических систем. В связи с этим представляет интерес исследова- ние вычислительной универсальности гибридных дискретно-непрерывных систем и систем с дискретным временем. Примеры и обзор таких исследований с дальнейшим списком литературы см. [7]. На практике оказывается, что чем выше размерность фазового пространства, тем проще доказать универсальность системы. Поэтому теоретически более инте- ресны системы низкой размерности. В [8] для одномерных кусочно-элементарных отображений в базисе функций {x2, x3, x1/2, x1/3, 2x, x + 1, x − 1}, а также дробно- рациональных функций, доказана алгоритмическая неразрешимость достижимости из точки точки. Однако при этом уже долгое время остается открытой пробле- ма достижимости в одномерных кусочно-аффинных отображениях даже в простей- шем случае двух интервалов [7]. Настоящая работа посвящена обратимым кусочно- аффинным отображениям с двумя интервалами. В ней мы приводим достаточные условия на языке теории динамических систем в виде ограничений на инвариантные меры обратимых кусочно-аффинных отображений, при которых проблема достижи- мости в таких системах оказывается алгоритмически разрешимой. 2. Обозначения. Обозначим через N = {1, 2, . . .}, Z, P , Q и R множества нату- ральных, целых, простых, рациональных и действительных чисел, соответственно, Z+ = {0, 1, 2, . . .}. Зафиксируем произвольное конечное множество F = {p1, p2, . . . , pk} ⊂ P про- стых чисел, упорядоченное индексами по возрастанию. Обозначим m = p1p2 . . . pk. Пусть x положительное рациональное число и x = ∏ p∈F pαp его каноническое раз- ложение, где αp ∈ Z, p ∈ F . Обозначим через \|x\|p p-адическую норму числа x, а через ‖x‖p = logp(\|x\|p), т.е. ‖x‖p = −αp. Назовем ‖x‖p логарифмом p-адической нор- мы числа x. Приведем следующие полезные далее свойства логарифма p-адической нормы, которые прямо следуют из свойств p-адической нормы: ‖x‖p < ‖y‖p ⇒ ‖x + y‖p = ‖y‖p, (1) ‖x · y‖p = ‖x‖p + ‖y‖p, (2) ‖xr‖p = r‖x‖p, (3) ‖x‖p = ‖y‖p ⇒ ‖x + y‖p ≤ ‖y‖p. (4) Если существует такое простое p /∈ F , что ‖x‖p > 0, то положим по определе- нию ‖x‖m = +∞, иначе положим ‖x‖m = max p∈F ‖x‖p. Назовем число ‖x‖m и вектор- столбец (‖x‖p1 , ‖x‖p2 , . . . , ‖x‖pk )T , соответственно, логарифмической m-нормой и 192 О проблеме достижимости в 2-интервальных кусочно-аффинных отображениях логарифмической m-вектор-нормой числа x. Содержательно логарифмическая m- норма числа, если ‖x‖m > 0, представляет собой число цифр после запятой в записи числа x в системе счисления по основанию m, то есть x можно представить в ви- де x = y ·m−‖x‖m , где y целое число, последняя цифра которого в m-ичной системе счисления отлична от 0. Если ‖x‖m ≤ 0, то x целое. Логарифмическую вектор-норму числа x обозначим через (‖x‖)m. Логарифмическая m-норма не является нормой в точном смысле этого слова. Пусть X – отрезок [0, 1] с отождествленными концами, т.е. X = R/Z, и отображе- ние f : X → X такое, что X = X1 ∪X2 ∪ . . . ∪Xl – разбиение на не пересекающиеся интервалы и f (x) = aix + bi ⇔ x ∈ Xi, ‖ai‖m < +∞, ‖bi‖m < +∞. Обозначим f ′(x) = ai, если x ∈ Xi. Обозначим через f∗ (x) = {fn (x)}n∈N орбиту точки x. Далее везде предполагаем, что функция f имеет указанный вид. 3. Проблема достижимости. Проблема достижимости из точки точки звучит так: существует ли для данного отображения f : X → X алгоритм, отвечающий для произвольных точек x0, x1 ∈ X на вопрос принадлежит или нет точка x1 множеству x1 ∈ f∗(x0). Ограничимся в проблеме достижимости рассмотрением только рацио- нальных точек X, то есть возьмем X = R/Z∩Q, по следующим соображениям. Как хорошо известно из теории динамических систем, кусочно-аффинное отображение f(x) = 2x (mod 1) является хаотическим для почти всех x ∈ X. Но ни одно число этого множества почти всех из X, очевидно не содержащего рациональных чисел, не представимо на компьютере, если под числом не понимать алгоритм, его порож- дающий. Если же под числом понимать произвольный алгоритм его порождающий, проблема достижимости для f(x) = 2x (mod 1) оказывается тривиально алгорит- мически неразрешимой в общем случае, несмотря на то, что отображение очень простое. Таким образом, принятие во внимание нерациональных чисел принципи- ально усложняет уже только формулировку проблемы достижимости даже для про- стейших кусочно-аффинных отображений. Приведенный пример обращает на себя внимание еще тем, что он лишний раз показывает необходимость аккуратного пони- мания математических теорем с точки зрения компьютерных наук: несмотря на то, что с точки зрения теории динамического хаоса отображение 2x (mod 1) является хаотическим для почти всех x ∈ [0, 1], это отображение не показывает хаотического или вообще сколько-нибудь сложного поведения ни для одного числа из доступных в языках программирования встроенных типов данных. Можно сказать, что слож- ность орбиты f∗(x), f(x) = 2x (mod 1), следует из сложности x. Стоит при этом заметить, что некоторые топологически сопряженные с f(x) = 2x (mod 1) отобра- жения показывают хаотическое поведение на множестве рациональных точек, если язык программирования поддерживает арифметику произвольной точности. Ряд важных асимптотических свойств динамических систем оказывается инва- риантным относительного топологического сопряжения. Но не ясно, влечет ли со- пряженность двух систем их эквивалентность с точки зрения проблемы достижимо- сти. Ответ на этот вопрос не очевиден. Поэтому, имея в виду как гипотезу алгорит- мическую разрешимость проблемы достижимости в 2-PAM, имеет смысл находить связи топологических и алгоритмических свойств орбит и проводить соответствую- 193 А.Н. Курганский щую классификацию систем, возможно более тонкую, чем сопряженность. В каче- стве иллюстрации простой связи топологических и алгоритмических свойств можно привести следующий пример. Если для динамической системы доказано свойство пе- ремешивания или эргодичности, то проблема достижимости открытой области фа- зового пространства становится, очевидно, тривиальной. В этом случае ответ всегда – да, достижима. Пример менее тривиального утверждения, связывающий тополо- гические и алгоритмические свойства кусочно-аффинных отображений, приведен далее в основной части работы. 4. Основной результат. Здесь мы докажем, что как минимум для обратимого кусочно-аффинного отображения с двумя интервалами при определенных ограни- чениях на ее инвариантные меры проблема достижимости из точки точки алго- ритмически разрешима. Компьютерное моделирование показывает, что инвариант- ные меры обратимых кусочно-аффинных отображений с двумя интервалами, по всей видимости, необходимо обладают требуемыми свойствами для алгоритмиче- ской разрешимости проблемы достижимости, но в настоящей работе мы оставляем это утверждение как гипотезу. Не ограничивая общности, рассматриваем далее только такие x ∈ X, для ко- торых ‖x‖m < +∞. В противном случае, если ‖x‖m = +∞, достаточно изменить множество F = {p1, ..., pk}, чтобы выполнилось требование ‖x‖m < +∞. Обозначим через A матрицу (aij), где aij = ‖ai‖pj , 1 ≤ i ≤ l, 1 ≤ j ≤ k. Через rank(A) обозначим ранг матрицы A. Лемма 1. Для любого положительного a ∈ R существует зависящее от a и F число b ∈ R такое, что для всех x ∈ [0, 1] с ограничением сверху ‖x‖m < a, выполняется ограничение снизу ‖x‖p > b для всех p ∈ F . Доказательство. Пусть выполняются условия леммы. Обозначим α = − ∑ p∈F,‖x‖p≤0 ‖x‖p и β = ∑ p∈F,‖x‖p≥1 ‖x‖p. Тогда pα 1 pka k ≤ pα 1 pβ k ≤ x ≤ 1. Отсюда следует −α ≥ −ka ln pk ln p1 . Что и требовалось доказать. ¤ Лемма 2. Пусть Φ множество инвариантных мер инъективного кусочно- аффинного отображения f : X → X. Пусть существуют такие Kmin > 0, Kmax < +∞, что для любых φ ∈ Φ и x ∈ X таких, что φ(x) 6= 0, выполняет- ся Kmin < φ(x) < Kmax. Тогда для отрезка произвольной орбиты x1, x2, . . . xn+1, где xi+1 = f(xi), выполняется Kmin Kmax ≤ \|c1 · c2 · . . . · cn\| ≤ Kmax Kmin , где ci = aj, если xi ∈ Xj. 194 О проблеме достижимости в 2-интервальных кусочно-аффинных отображениях Доказательство. Пусть φ инвариантная мера на X отображения f . Тогда y = f(x) влечет φ(y) = φ(x) \|f ′(x)\| (оператор Перрона–Фробениуса). Обозначим ci = f ′(xi). Тогда φ(xn+1) = φ(x1) \|c1·c2·...·cn\| и \|c1 · c2 · . . . · cn\| = φ(x1) φ(xn+1) . Отсюда следует утверждение леммы. ¤ Теорема 1. Если для инъективного кусочно-аффинного отображения f : X → X с двумя интервалами существуют такие Kmin > 0 и Kmax < +∞, что для любой инвариантной меры φ : X → R отображения f и для любых x ∈ X таких, что φ(x) 6= 0, выполняется Kmin < φ(x) < Kmax, то проблема достижимости для f алгоритмически разрешима. Доказательство. Напомним обозначения: X = X1 ∪ X2 и f(x) = aix + bi, если x ∈ Xi. Рассмотрим произвольные x, y ∈ X такие, что y ∈ f∗(x). Пусть последо- вательность (отрезок орбиты f∗(x)) x1, x2, . . . , xn+1 такая, что x1 = x, xn+1 = y, xi+1 = f(xi), 1 ≤ i ≤ n. Если мы найдем вычислимую из Kmin, Kmax, a1, a2, b1, b2, x, y верхнюю оценку M = M(Kmin,Kmax, a1, a2, b1, b2, x, y) длины n отрез- ка орбиты, то тем самым мы докажем алгоритмическую разрешимость проблемы достижимости, поскольку для проверки достижимости из точки x точки y доста- точно рассмотреть начальный отрезок орбиты длины, не превышающей числа M . Но для доказательства существования вычислимой оценки M длины n достаточно доказать, что логарифмические нормы ‖xi‖m для всех i ∈ {1, . . . , n+1} ограничены сверху некоторым вычислимым числом M1 = M1(Kmin,Kmax, a1, a2, b1, b2, x, y). От- сюда, поскольку ‖xi‖m есть число знаков после запятой в записи числа xi в системе счисления по основанию m, сразу следует оценка сверху числа n: n < M < mM1 . Если отрезок орбиты длины, большей mM1 , состоит из чисел, логарифмические m- нормы которых меньше M1, то он обязательно содержит два одинаковых числа. Поскольку f функция, то орбита в этом случае зацикливается. В свою очередь, для доказательства вычислимого ограничения сверху на ‖xi‖m достаточно доказать, что для любого p ∈ F логарифмические нормы ‖xi‖p ограничены сверху одним вычис- лимым числом M2 для всех i ∈ {1, . . . , n+1}. В силу определения логарифмической m-нормы, M2 = M1. Обозначим h = max{‖b1‖m+1, ‖b2‖m+1, ‖x1‖m, ‖xn+1‖m}. Возьмем произвольное p ∈ F и выделим в последовательности x1, x2, . . ., xn+1 произвольную подпоследова- тельность xj , xj+1, . . . , xr такую, что её элементы x ∈ {xj+1, xj+2, . . . , xr−1} облада- ют свойством ‖x‖p > h, при этом ‖xj‖p ≤ h и ‖xr‖p ≤ h. Для простоты, но не огра- ничивая общности рассуждений, положим j = 1, r = n + 1 и ‖x1‖p = ‖xn+1‖p = h. Далее, рассматривая частные случаи, мы либо укажем верхнюю вычислимую оценку числа n, либо укажем вычислимое число M2 = M2(Kmin,Kmax, a1, a2, h) та- кое, что для всех x ∈ {x1, x2, . . . , xn+1} ‖x‖p ≤ M2. Как сказано выше, этого будет достаточно для доказательства теоремы. Пусть xi+1 = f(xi) = cixi + di, где ci ∈ {a1, a2}, di ∈ {b1, b2}. Из свойств (1) и (2) логарифма p-адической нормы и того, что ‖xi‖p > ‖bj‖p, i ∈ {1, 2, . . . , n}, j ∈ {1, 2}, 195 А.Н. Курганский следует ‖xi+1‖p = ‖xi‖p + ‖ci‖p. Откуда получаем: ‖xn+1‖p = ‖x1‖p + n∑ i=1 ‖ci‖p = ‖x1‖p + 2∑ i=1 αi‖ai‖p для некоторых целых неотрицательных α1 и α2, α1 + α2 = n. Учитывая ‖x1‖p = ‖xn+1‖p, получим 2∑ i=1 αi‖ai‖p = 0. Пусть r наибольшее общее кратное чисел α1 и α2. Обозначим α = α1/r и β = α2/r, то есть α и β минимальные неотрицательные целые такие, что α‖a1‖p + β‖a2‖p = 0. Таким образом, получаем 2∑ i=1 αi‖ai‖p = r(α‖a1‖p + β‖a2‖p). Напомним, что в силу условий теоремы выполняется Kmin Kmax ≤ \|c1 · c2 · . . . · cn\| ≤ Kmax Kmin , т.е. Kmin Kmax ≤ \|aα 1 aβ 2 \|r ≤ Kmax Kmin , Рассмотрим два случая \|aα 1 aβ 2 \| 6= 1 и \|aα 1 aβ 2 \| = 1. Первый случай, другими слова- ми, означает линейную независимость столбцов матрицы A: rank(A) = 2, а второй означает их линейную зависимость: rank(A) < 2. Пусть \|aα 1 aβ 2 \| 6= 1, тогда либо \|aα 1 aβ 2 \| > 1, либо \|aα 1 aβ 2 \| < 1. Если выполняется \|aα 1 aβ 2 \| > 1, то и из условия \|aα 1 aβ 2 \|r ≤ Kmax Kmin следует r ≤ ln Kmax Kmin ln \|aα 1 aβ 2 \| . Если выполняется \|aα 1 aβ 2 \| < 1, то и из условия \|aα 1 aβ 2 \|r ≥ Kmin Kmax следует r ≤ ln Kmin Kmax ln \|aα 1 aβ 2 \| . Таким образом, в обоих случаях мы имеем вычислимое ограничение сверху на число n = r(α + β). Предположим теперь \|aα 1 aβ 2 \| = 1. Поскольку при \|a1\| = 1 и \|a2\| = 1 мы полу- чаем вырожденный случай кусочно-аффинного отображения, то интересен только случай a1 6= 1 и a2 6= 1. Не ограничивая общности рассуждений, положим a1 > 1 и a2 < 1. Заметим также, что ‖a2‖p = −α β ‖a1‖p. Рассмотрим произвольную подпосле- довательность x1x2 . . . xj+1, j ≤ n, рассматриваемой последовательности. Пусть α1, α2 такие, что \|c1c2 . . . cj \| = \|a1\|α1 \|a2\|α2 . Тогда ‖xj+1‖p = ‖x1‖p + α1‖a1‖p + α2‖a2‖p = (α1 − α2 α β )‖a1‖p. С другой стороны, в силу леммы 2, Kmin Kmax ≤ \|a1\|α1 \|a2\|α2 ≤ Kmax Kmin . 196 О проблеме достижимости в 2-интервальных кусочно-аффинных отображениях Поскольку \|aα 1 aβ 2 \| = 1, то \|a2\| = \|a1\|− α β и Kmin Kmax ≤ \|a1\|α1−α2 α β ≤ Kmax Kmin . Учитывая предположение \|a1\| > 1, получаем α1 − α2 α β ≤ ln Kmax Kmin ln \|a1\| . Отсюда следует, что ‖xj+1‖p = ‖x1‖p + (α1 − α2 α β )‖a1‖p ≤ h + ( ln Kmax Kmin ln \|a1\| ) ‖a1‖m. Таким образом, мы показали вычислимую границу сверху для логарифмических p- норм элементов орбиты и тем самым, в силу приведенных в начале доказательства рассуждений, доказали теорему. ¤ 5. Заключение. Заметим, что мы доказали алгоритмическую разрешимость проблемы достижимости в обратимых кусочно-аффинных отображениях с двумя интервалами при определенных ограничениях на инвариантные меры лишь для каждого отдельно взятого отображения. Из основного результата работы не следу- ет алгоритмическая разрешимость сразу для всех упомянутых отображений вместе взятых, поскольку мы не знаем как вычислять величины Kmin и Kmax по кусочно- аффинному отображению. Доказательство более общих утверждений будет прове- дено в дальнейших работах. 1. Savchenko A.Ya., Kovalev A.M., Kozlovskii V.A., Scherbak V.F. Inverse dynamical systems in secure communication and its discrete analogs for information transfer // Proc. of NDES. 2003. – P. 112–116. 2. Ковалев А.М., Савченко А.Я., Козловский В.А., Щербак В.Ф. Обращение динамических си- стем вход–выход в задачах защиты информации // Искусственный интеллект. – 2007. – № 4. – С. 416–424. 3. Ковалев А.М., Савченко А.Я., Козловский В.А., Щербак В.Ф. Обратные динамические систе- мы регулируемой размерности в задачах преобразования информации // Труды ИПММ НАН Украины. – 2008. – Т. 17. – С. 115–123. 4. Ковалев А.М., Козловский В.А., Щербак В.Ф. Обратимые динамические системы с переменной размерностью фазового пространства в задачах криптографического преобразования инфор- мации // Прикл. дискретная математика. – 2008. – № 2 (2). – С. 39–44. 5. Olivier Bournez, Manuel L. Campagnolo A Survey on Continuous Time Computations // New Computational Paradigms, Springer New York, 2008. – P. 383–423. 6. Delvenne J.-C. What is a universal computing machine? // Applied Mathematics and Computation. – Vol. 215, Issue 4. – 2009. – P. 1368–1374. 7. Asarin E., Mysore V., Pnueli A., Schneider G. Low dimensional hybrid systems – decidable, unde- cidable, don’t know // Information and Computation. – 2012. – Vol. 211. – P. 138–159. 197 А.Н. Курганский 8. Kurganskyy O., Potapov I., Sancho-Caparrini F. Reachability Problems in Low-Dimensional Itera- tive Maps // Int. J. Found. Comput. Sci. – 2008. – 19 (4). – P. 935–951 9. Каток А.Б., Хасселблат Б. Введение в теорию динамических систем с обзором последних достижений. – М.: МЦМНО, 2005. – 464 с. O. Kurganskyy On reachability problem in 1-dimensional 2-interval piecewise-affine mapings. We consider the open reachability problem for one dimensional piecewise-affine mappings with two intervals (2-PAM). We give some decidable results following from specific topological properties of reachable states of the 2-PAM’s. Keywords: piecewise-affine mapping, reachability problem. О.М. Курганський Алгоритмiчна проблема досяжностi в 1-вимiрних 2-iнтервальних кусково-афiнних вi- дображеннях. Розглянуто вiдкриту проблему досяжностi в одновимiрних кусково-афiнних вiдображеннях з двома iнтервалами. Знайдено окремi випадки алгоритмiчної розв’язностi цiєї проблеми, якi сформульо- ванi на мовi топологiчних властивостей орбiт у таких системах. Ключовi слова: кусково-афiннi вiдображення, проблема досяжностi. Ин-т прикл. математики и механики НАН Украины, Донецк topologia@mail.ru Получено 12.11.13 198

Алгоритмическая проблема достижимости в 1-мерных 2-интервальных кусочно-аффинных отображениях

Репозитарії

Схожі ресурси