Класи функцій, визначених перетворювачами над надсловами

Размещено на http://www.allbest.ru/

2

Київський університет імені Тараса Шевченка

АВТОРЕФЕРАТ ДИСЕРТАЦІЇ

на здобуття наукового ступеня кандидата фізико-математичних наук

Класи функцій, визначених перетворювачами над над словами

01.01.08 - математична логіка, теорія алгоритмів і дискретна математика

Шкаравська Ольга Юріївна

Київ-1999



Дисертацією є рукопис.

Роботу виконано на кафедрі теоретичної кібернетики Київського університету імені Тараса Шевченка Науковий керівник: - доктор фізико-математичних наук, професор, ЛІСОВИК Леонід Петрович, кафедра теорії програмування Київського університету імені Тараса Шевченка.

Офіційні опоненти:

- доктор фізико-математичних наук, професор КАПІТОНОВА Юлія Володимирівна інститут кібернетики НАН України, завідуюча відділом теорії цифорвих автоматів;

- кандидат фізико-математичних наук, доцент ПРАЦЬОВИТИЙ Микола Петрович, завідуючий кафедрою вищої математики

Національного Педагогічного Університету імені М.П. Драгоманова.

Провідна установа: Інститут математики НАН України

Захист відбудеться “31” травня 1999 року о 14 год.

на засіданні спеціалізованої вченої ради Д 26.001.18 при Київському університеті імені Тараса Шевченка за адресою:

252127, м.Київ - 127, проспект акад. Глушкова,6 ,Київський університет імені Тараса Шевченка, механіко-математичний факультет

З дисертацією можна ознайомитися в бібліотеці Київського університету імені Тараса Шевченка (вул. Володимирська, 58)

Автореферат розісланий “ 27” квітня 1999 року

Вчений секретар спеціалізованої вченої ради А.П.Петравчук

перетворювач дійсне число фрактальна безліч



ЗАГАЛЬНА ХАРАКТЕРИСТИКА РОБОТИ

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

Актуальність теми. Машини Т'юрінга, зокрема скінченні автомати Мілі, можна розглядати як засіб задання дійсних функцій. З цієї точки зору скінченні автомати Мілі і узагальнені послідовнісні машини розглядалися С. Ейленбергом. Для визначення значення f(x) автомат послідовно переробляв вхідний об'єкт - розклад дійсного числа x у двійковій (десятковій) системі числення - у вихідний об'єкт - відповідний розклад числа f(x).

Поняття R-перетворювача, введене Л. П. Лісовиком, узагальнює підхід Ейленберга. Скінченні R-перетворювачі, на відміну від автоматів Мілі, можуть бути асинхронними і задавати відображення двійкових розкладів у так звані двійкові розклади з переповненнями, тобто ті, що допускають появу символу 2 у зображенні числа. Суперпозиції функцій, які задаються R-перетворювачами, досліджувалися Лісовиком і П.В. Дробишевим. Пізніше поняття R-перетворювача було узагальнене до поняття Rⁿ_m-перетворювача, котрий має m вхідних і n вихідних стрічок, та R_(s,t)-перетворювача, котрий переробляє s-кові зображення дійсних чисел у вихідні t-кові зображення. Ще більш загальними об'єктами є RA_{[0, 1)}-перетворювачі, котрі обробляють спеціальні нескінченні зображення дійсних чисел.

Такий підхід до задання дійсних функцій є, з одного боку, конструктивним, з іншого - відрізняється від традиційних теорій конструктивного аналізу, оскільки на вхідні дані не накладається умова конструктивності (ефективної обчислюваності), а конструктивні дйсні функції (КДФ) за звичай задаються на конструктивних дійсних числах (КДЧ). В залежності від потужності та структури пам'яті, перетворювачі можуть бути скінченними, магазинними, стековими, C-машинами, або бути перетворювачами загального вигляду зі зліченною множиною станів. Як показав Лісовик, R-перетворювачами загального вигляду задаються всі неперервні функції та функції, що мають розриви першого роду у двійково-раціональних точках. У зв'язку із цим виникає новий критерій для класифікації дійсних функцій - за типом пам'яті R-перетворювача, котрим визначається задана функція.

З практичної точки зору перетворювачі уявляють собою алгоритми, котрі з довільною точністю можуть обчислювати значення функції у заданній точці. Перетворювачі також можуть розглядатися як засоби задання фрактальних множин рекурсивної природи і функцій на таких множинах.

Мета і задачі досліджень.

Мета даної дисертаційної роботи - побудувати зв'язки між класами дійсних функцій, визначених різними типами перетворювачів над надсловами, і класами дійсних функцій, описуваних методами класичного аналізу - диференційовними функціями, афінними перетворенями, характеристичними функціями фрактальних множин.

Методи досліджень.

Основним “стратегічним” методом досліджень стало висування гіпотез із подальшим їх аналізом, спростуванням або уточненням і перетворенням на теорему. “Технічні” методи досліджень обчислювальних можливостей скінченних і магазинних перетворювачів, серед яких провідне місце посідає так звана “техніка слідів”, грунтуються на рекурсивній природі цих об'єктів. Також інтенсивно використовувався метод побудови прикладів і контрприкладів, в розділі 3 - метод діагоналізації Кантора.

Наукова новизна одержаних результатів. В роботі отримано такі нові результати:

доведено, що клас диференційовних на деякому інтервалі функцій, які задаються магазинними R-перетворювачами, міститься у класі лінійних на цьому інтервалі функцій;

розглянуто необхідну і достатню умову, за якої афінне перетворення з раціональними параметрами підмножини n-вимірного простору можна задати скінченним Rⁿ_m-перетворювачем;

доведено узагальнення теореми Мостовського-Успенського про переклад зображень дійсних чисел для строгих R_(s,t)-перетворювачів: для існування строгого R_(s,t)-перетворювача, котрий задає тотожню фукцію, необхідно і достатньо, аби множина простих дільників числа s містила множину простих дільників числа t; також показано, що необхідна і достатня умова можливості перекладу для скінченних R_(s,t)-перетворювачів є більш жорсткою;

побудовано R²₁-перетворювачі, котрі задають криву Пеано з коефіцієнтом перекриття 3 і сюр'єкцію одиничного відрізку на килим Серпинського;

доведено, що за довільною ієрархічною ітерованою функціональною схемою (HIFS) можна побудувати систему перетворювачів, які задають той самий вектор компактних множин з Rⁿ, що і задана HIFS; розглянуто умову, за якої ці перетворювачі є скінченними; побудовано RA_{[0, 1]}-перетворювач, який задає незамкнену множину.

Усі наведені твердження грунтуються на рекурсивній природі перетворювачів, на повторюваності або “майже повторюваності” команд перетворювача під час обробки нескінченного зображення дійсного числа. Зокрема, така властивість обумовлює зв'язок областей визначення функцій, які задаються перетворювачами, та широкого класу фрактальних множин.

Практичне значення отриманих результатів. Зазначені результати можна використовуати для подальших досліджень проблем обчислюваності дійсних функцій і досліджень у теорії фрактальних множин. З практичної точки зору інтерес уявляють алгоритми довільної точності для задання афінних перетворень для заданих множин PОRⁿ раціональних матриці M і вектору h. Також варто спробувати застосувати алгоритм побудови кривої Пеано з коефіцієнтом перекриття 3 у задачах математичного програмування, обробки зображень, передачі даних тощо, в яких використовуються прямі та звортні відображення відрізку на квадрат.

Особистий внесок здобувача. Авторові роботи належить твердження про лінійність функцій, які задаються магазинними перетворювачами (вперше воно було сформульовано для скінченних перетворювачів), один з двох способів його доведення, також конструкція кривої Пеано з коефіцієнтом перекриття 3 та теорема про зв'язок множин, які визначаються системами перетворювачів та HIFS.

Апробація результатів роботи. Результати роботи доповідалися на ІІ-й Міжнародній конференції “Математичні алгоритми” (Нижній Новгород, червень 1995 року), на семінарі “Фрактальний аналіз і суміжні питання” при Педагогічному університеті ім. М.П. Драгоманова, на семінарі при відділі теорії цифрових автоматів інституту кібернетики НАН України.

Публікації. За темою дисертації опубліковано 4 наукових роботи, список яких наведений у кінці автореферату. Роботи [1 - 3] створені у співавторстві з науковим керівником. В роботах [1] і [3] авторові належить ідея доведення теорем 1 і 1 відповідно, в яких йдеться про існування скінченного R²₁-перетворювача, котрий задає криву Пеано з коефіцієнтом перекриття 3. Твердження теореми 5[3] про лінійність функцій, які задаються магазинним перетворювачем, і метод її доведення належать авторові дисертаційної роботи.

Структура та обсяг дисертації. Дана дисертаційна робота складається з переліку умовних позначень, вступу, семи розділів та розділу, в якому вказано висновки. Її обсяг становить 151 сторінки. Робота містить 8 рисунків і 5 таблиць. Список використаних джерел складається зі 47 найменувань.

ОСНОВНИЙ ЗМІСТ

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

У першому розділі оглянуто основні наукові і прикладні праці, котрі стосуються тематики досліджень.

У підрозділі 1.1 розглядаються конструктивні підходи до числа і функції, запропоновані і досліджувані різними авторами. Зокрема оглянуто внесок в конструктивний аналіз Т'юрінга, Банаха, Мазура, Гржегорчика. Детально висвітлено визначення КДЧ і КДФ та відповідні властивості за Мартином-Льофом.

Підрозділ 1.2 присвячений основним результатам теорії перетворювачів. Зокрема зазначено результати Лісовика про існування R-перетворювача, котрий задає неперервну ніде не диференційовну функцію, R²₁-перетворювача, котрий задає криву Пеано з коефіцієнтом перекриття 4, про вкладеність класу функцій, які задаються скінченними R-перетворювачами, у клас функцій, які відображають раціональні числа в раціональні, та про строгу вкладеність класу функцій, які задаються скінченними R-перетворювачами, у клас функцій, які задаються магазинними R-перетворювачами. Властивості суперпозицій функцій, які задаються R-перетворювачами, досліджували Лісовик і Дробишев. Останнім побудовано скінченно 2-метареальну функцію, множина точок розриву якої континуальна, та часткову скінченно 2-метареальну функцію, область визначення якої є множина двійково-раціональних чисел.

Лісовиком і Дробишевим доведено алгоритмічну розв'язуваність проблем еквівалентності, монотонності і рівності в класі скінченно-метареальних функцій.

У підрозділі 1.3 розглядаються алгоритми Пеано та Гільберта побудови неперервних сюр'єкцій відрізка на квадрат. Також розглянуто принципи застосування відображень і розгорток Пеано в математичному програмуванні та передачі данних. Зазначені інші галузі прикладної науки, де застосовуються такі відображення.

У підрозділі 1.4 визначене поняття ієрархічної ітерованої функціональної схеми (HIFS), яка уявляє собою систему вигляду

X_i=И{f_k(X_j)Ѕ (k, j)ОQ_i },

де f_k є стискання в R^m, Q_iН{1,…d₁}ґ{1,…d₂} за 1ЈkЈd₁, 1ЈiЈd₂.

За Бандтом та іншими авторами відомо, що така система визначає єдиний вектор непорожніх компактних множин, який є її розв'язком. HIFS є одним з основних засобів задання фрактальних множин та інтенсивно використовуються в комп'ютерній графіці.

У другому розділі даної роботи обгрунтовано вибір напрямків досліджень. Основний напрямок полягає в аналізі обчислювальної потужності R-перетворювачів з магазинною пам'яттю. Інший напрямок пов'язаний з дослідженням можливостей скінченних R-перетворювачів у заданні неаналітичних функцій та узагальнень R-перетворювачів ---перетворювачів, у заданні фрактальних множин.

Також у цьому розділі описаний один з основних методів дослідженння перетворювачів з обмеженнями на пам'яті - “техніка слідів”. Її було впроваджено незалежно різними авторами - Хенні, Трахтенбротом і Барздинем, Рабином. У цій роботі використано термінологію Хенні.

Розділи з 3-го по 7-й присвячені дослідженням автора роботи в теорії перетворювачів.

В третьому розділі аналізується обчислювальна потужність магазинних R-перетворювачів. Основний результат розділу, теорема 3.1, доводиться у підрозділі 3.1.

Теорема 3.1. Нехай функція f(x) всюди диференційовна на деякому інтервалі (a', b'), де a'<b', і задається недетермінованим RМП-перетворювачем A. Тоді f(x) - лінійна на (a', b') функція.

Ідея доведення грунтується на “техніці слідів”.

Використовуючи “техніку слідів” (“слідом” в даному віпадку є пара “стан пам'яті” - “магазинний символ”) до процесу обчислень деякого недетермінованого RMП-перетворювача A над нескінченним ланцюгом символів, можна структурувати область визначення функції таким чином, що вона представляється у вигляді зліченного об'єднання , де K - множина станів, Г - множина магазинних символів, - множина чисел з Dom() з такою властивістю двійкових зображень:

- вони починаються зі слова u₀,

- у процесі обчислень над ними RMП-перетворювач A нескінченну кількість разів перебуває в стані q оглядаючи на верхівці магазина символ a, вже ніколи потім не “заглиблюючись” у магазин нижче рівня, де саме цей символ a знаходиться у магазині. Зовнішнє об'єднання відбувається по всіх тих префіксах u₀, читаючи які з початкового стану q₀ заданий перетворювач впреше переходить у стан q і оглядає символ a, вже ніколи потім не “заглиблюючись” у магазин нижче рівня, де цей символ a знаходиться у магазині.

У доведенні основного результату розділу - теоремі 3.1 - розглядається поведінка похідних чисел функції в точках з деякої фіксованої множини . Виявляється, що всі її точки лежать на одній прямій. З диференційовності функції випливає, що і точки з усього зліченного об'єднання лежать на одній прямій.

Наслідок 3. 1. До класу функцій, які не можна задати скінченними (і магазинними) R-перетворювачами, входять такі: тригонометричні функції, степеневі функції x^a за aП{0, 1}, нелінійні поліноми P(x), логарифмічна log_a(x) і показникова функції a^x, за a>0, a№1.

У підрозділі 3.2 наведено приклад неперервної функції (константи), котра відображає раціональні числа в ірраціональне і задається стековим R -перетворювачем. Таким чином доведено, що клас функцій, які задаються магазинними R -перетворювачами, строго вкладений у клас функцій, які задаються стековими R -перетворювачами.

У четвертому розділі розглядається можливість узагальнення на n-вимірні евклідові простори результату про представність лінійної функції з раціональними параметрами скінченним перетворювачем.

Виявилося, що афінне перетворення вигляду (x)=Mx+h, де матриця M розмірності nґn і вектор h=(h₁,…h_n) раціональні, взагалі кажучи, не можна задати скінченним R_nⁿ-перетворювачем. Причину цього факту викрито у підрозділі 4.1, де розглядаються функції вигляду ax+by, визначені на деякій множині PНR². Будемо казати, що зв'язна множина PНR² задовольняє умові (a), якщо множина Pr₁(P) необмежена і множина Pr₂(P) обмежена, або навпаки. Суть умови (a), полягає в тому, що на скінченній пам'яті не можна реалізувати додавання ax+by, де (x, y) ОP, коли різниця порядків елементів множин Pr₁(P) і Pr₂(P) є необмеженою. Якщо різниця в порядках двох чисел xОPr₁(P) і yОPr₂(P) перевищує кількість станів R₂¹-перетворювача, то R₁²-перетворювач “втрачає” інформацію про порядок більшого числа внаслідок повторюваності станів. На цьому факті базується доведення наступного твердження.

Лема 4.1. Нехай a, b - довільні відмінні від нуля дійсні числа, і множина P'НR² задовольняє умові (a). Тоді не існує скінченного R₂¹-перетворювача A, такого, що Dom()P' і (x, y)=ax+by.

Для заданої матриці M=(m_ij)_i,j=1ⁿ через T_i(M) будемо позначати множину індексів {j|1ЈjЈn Щ m_ij№0}. Нехай матриця M і вектор h=(h₁,…h_n) раціональні, а P є множина вигляду I₁ґ…ґI_n, де I_iНR є або сегмент, або напівзамкнений необмежений промінь або вся числова пряма, 1ЈiЈn. При цьому вважаємо, що будь-яке з чисел a_i=infI_i (b_i=supI_i), відмінне від ±Ґ, є двійково-раціональне число.

У підрозділі 4.2 сформульовано таку умову (b):

Казатимемо, що для матриці M і множини P виконано умову (b), якщо для всіх 1ЈiЈn з Card(T_i(M))і2 випливає обмеженість усіх множин I_j, де jОT_i(M).

Теорема 4.2. Скінченний R_nⁿ-перетворювач A₁, такий, що (x)=Mx+h і Dom()=P існує тоді і тільки тоді, коли для матриці M і множини P виконано умову (b).

Доведення достатності узагальнює конструкцію Лісовика для R-перетворювача, що задає лінійну функцію з раціональними параметрами. Необхідність спирається на лему 4.1.

У п'ятому розділі розглядаються аналоги теореми Мостовського-Успенського для строгих R_{(s, t)}-перетворювачів і строгих скінченних R_{(s, t)}--перетворювачів.

Суть зазначеної теореми полягає в тому, що алгоритм перекладу обчислюваного s-кового зображення дійсного числа в його обчислюване t-кове зображення існує тоді і тільки тоді, коли множина простих дільників числа s, яку позначимо через P_s, містить множину простих дільників числа t, позначену через P_t.

Виявилося, що цей результат узагальнюється на всі, не тільки обчислювані, зображення дійсних чисел.

Теорема 5.1. Строгий R_{(s, t)} -перетворювач A такий що (x)=x, xОR, існує тоді і тільки тоді, коли виконане включення P_sК P_t.

Необхідність доведено методом від супротивного. З того, що множина простих дільників для t не міститься в множині простих дільників числа s, випливає існування раціонального числа x₀, на s -ковому зображенні w котрого заданий R_{(s, t)} -перетворювач A видає послідовність A(w), яка не є t -ковим зображенням числа x₀.

Для доведення достатності побудовано OR_{(s, t)} -перетворювач A', котрий задає тотожню функцію. У заданні відповідної системи продукцій використовувалася рівність 1/t=d/s^b, яка виконується для деяких чисел d, bОN⁺ і випливає з включення множини простих дільників числа t у множину простих дільників числа s. На змістовному рівні побудова t -кового зображення заданого числа x з відрізку [0, 1] полягає у здобутті низки цілих невід'ємних чисел g1, g2,…, gk,…, де gk позначає, “скільки разів дріб 1/t^k міститься у заданому дійсному числі” (але без урахування старших степенів 1/t, тобто дробів вигляду 1/tⁱ, де 1ЈiЈk-1, оскільки з “входження j разів числа 1/t^j ув x” випливає “входження jt разів числа 1/tⁱ ув x”), де kОN⁺. Формально, gk=[x/(1/t^k)]-[x/(1/t^k-1)] або gk=[x/(1/t^k)]-(gk+…+g1), де g1=[x/(1/t). Звідси виливає, що, неформальною мовою, перетворювач має рахувати відповідні кількості дробів d^k/s^bk, де kОN⁺. Для побудови t-кового зображення цілої частини довільного дійсного числа перетворювач “накопичує в пам'яті” її s-кове представлення, на кожному кроці обчислень зчитуюючи черговий вхідний s -ковий символ і нічого не друкуючи на виході аж до того моменту, коли не зустріне символ С. Після читання С перетворювач видає t-кове зображення цілого, s-ковий запис якого міститься в пам'яті, видає також після нього символ С, “скидає” пам'ять і переходить до обробки дробової частини.

Далі в цьому розділі розглянуто можливість перекладу зображень дійсних чисел з однієї системи числення в іншу за допомогою скінченних R_{(s, t)} -перетворювачів. У випадку скінченних R_{(s, t)} -перетворювачів повний аналог теореми Мостовського-Успенського місця не має.

Теорема 5.2. Строгий скінченний R_{(s, t)}-перетворювач B=(K_B, H_B, q₀), такий що (x)=x і Dom(f_B)=D_s, існує тоді і тільки тоді, коли s=tⁿ для деякого числа nОN⁺. (Через Dom(f_B)=D_s позначено множину s -кових представлень всіх дійсних чисел.) При доведенні використано попередньо обгрунтовану лему 5.1.

Лема 5.1. Нехай B=(K_B, H_B, q₀) - строгий скінченний R_{(s, t)}-перетворювач, такий що (x)=x і область визначення функції є вся числова вісь R, або напівзамкнений необмежений промінь вигляду (-Ґ, r], або [r, +Ґ), де rОR, або сегмент. Тоді існують такі числа m, nОN⁺, що s^m=tⁿ.

Ця лема фактично є зворотним твердженням до факту, доведеного Лісовиком, який за умов існування чисел m, nОN⁺, таких що s^m=tⁿ, вказав алгоритм побудови строгого скінченного R_{(s, t)}-перетворювача, що задає тотожю функцію на відрізку [0, 1]. Основним результатом шостого розділу є теорема 6.1. Теорема 6.1. Існує скінченний R₁²-перетворювач А, такий що : [0,1]®[0,1]² - неперервна сюр'єктивна функція і для будь-якої точки z з [0,1]² її прообраз f^-1(z) містить не більше трьох елементів.

Ідея побудови такого відображення нагадує конструкцію Гільберта. Одиничний квадрат ділиться на 9 підквадратів 1-го рангу (рис. 1).

Рис. 1. (У дисертаційній роботі цьому рисунку відповідає рис. 6.1)



Відрізок [0, 1] також ділиться на 9 підвідрізків 1-го рангу: [0, 1/16], [1/16, 1/8], [(m-1)/8, m/8], де 2ЈmЈ8. Підквадрати і підвідрізки приводяться у відповідність, яка визначається “пробігом” відрізка [0, 1] у додатному напрямку і обігом підквадратів 1-го рангу згідно зі стрілками.

Процес ділення сегментів n-го рангу на підсегменти (n+1)-го, nі1, продовжується таким чином, аби відповідні підквадрати обходилися поспіль. Тип обходу підквадрату, якому відповідає в точності один стан R₁²-перетворювача, визначається парою вершин “вхід-вихід”. Наступне правило забезпечує рівність коефіцієнту перекриття трьом. Нехай точка квадрату належить чотирьом підквадратм одночасно, тобто її прообрази належать чотирьом підвідрізкам з прообразу всього квадрату. Тоді для якихось двох з чотирьох підквадратів вона має бути точкою “входу-виходу”, тобто один з її прообразі належить одночасно двом підвідрізкам (є їхньою спільною границею).

В сьомому розділі розглядається узагальнення поняття R_{(s, t)}--перетворювача. Узагальненням нескінченних символьних зображень дійсних чисел з відрізка [a, b] є розклад у вигляді послідовності aСi₁i₂…, де i_l належить деякій фіксованій підмножині множини N, lОN⁺. Вводяться L типів розбиття довільного відрізку на підвідрізки: T₁,…, T_L. Кожний клас T_l, де 1ЈlЈL, визначається послідовністю {r_li}_i=1^h(l) довжини h(l), такою що 0<r_l1<…<r_lh(l)=1, r_l0=0. Кожний відрізок [c, c'] типу T_l розбивається на h(l) підвідрізків, які занумеровано від 1 до h(l) так, що i-й підвідрізок є [c+(c'-c)r_{l i-1}, c+(c'-c)r_{l i}]. Число з зображенням aСi₁i₂…, є єдиним елементом множини [c_l, c_l'], де [c₀, c₀']=[a, b] та кожний з відрізків де [c_l, c_l'] за lОN належить типові T(l)О{T₁,…, T_L}, і за lі1 є i_l -й підвідрізок відрізку [c_l-1, c_l-1'] при розбитті його за відповідним типом T(l-1). Такий спосіб задання дійсних чисел був визначений Лісовиком і подібні представлення є вхідними данними для визначених ним RA_{[0, 1)}-перетворювачів. В даному розділі поняття RA_{[0, 1)}-перетворювача узагальнюється на m-вимірний випадок і розглядаються -перетворювачі, котрі обробляють вектори визначених вище представлень точок з паралелепіпеду

Виявилося, що існують множини, які задаються скінченними -перетворювачами і не є визначеними HIFS.

Лема 7.2. Існує скінченний RA_{[0, 1)}-перетворювач B, такий, що Dom() не є замкненою множиною.

За заданою HIFS можна побудувати систему перетворювачів, котра визначає той самий вектор множин.

Теорема 7.1. Нехай задано систему вигляду

C_i=И{f_k(C_j)Ѕ (k, j)ОQ_i }, 1ЈiЈd₂,

де f_k є стискувальними подібностями в R, де 1ЈkЈd₁ та Q_iН{1,…d₁}ґ{1,…d₂} за 1ЈiЈd₂. Існують -перетворювачі A_i=(K_i, P_i, h_i, H_i, q₀), такі що множина станів K_i містить стан q_i, q₀a_i®0Сq_iОH_i та Dom()=C_i, де 1ЈiЈd₂. Наслідок 7.1. Якщо існує таке число N, що для будь-якого i, за умови існування послідовностей k₁₁, …, k_1N, k₂₁,…, k_2N та i₁₁, …, i_1N , i₂₁,…, i_2N, таких що i₁₁=i₂₁=i та за yО{1, 2} і 2ЈlЈN, множини і не перетинаються, то існує скінченний -перетворювач A_i, такий, що Dom()=C_i, де 1ЈiЈd₂.

Твердження, аналогічні теоремі 7.1 і наслідку 7.1, мають місце і в m-вимірних просторах, mі1.



ВИСНОВКИ

В роботі показано, що клас диференційовних на заданому інтервалі функцій, які визначаються R-перетворювачами з магазинною пам'яттю, вкладений у клас лінійних на цьому інтервалі функцій. Доведено, що клас дійсних функцій, які задаються магазинними R-перетворювачами, строго вкладений у клас функцій, які задаються R-перетворювачами зі стековою пам'яттю.

Досліджується необхідна і достатня умова, за якої афінне перетворення (x)=Mx+h, де PНR², задається скінченним R_nⁿ-перетворювачем. Ця умова накладається на множину P і матрицю M.

Доведено такі факти про можливість перекладу чисел з системи числення з основою s в систему числення з основою t за допомогою R_{(s, t)} -перетворювачів:

- строгий R_{(s, t)} -перетворювач A=(K_A, H_A, q₀), такий що (x)=x, існує тоді і тільки тоді, коли множина простих дільників числа s включає множину простих дільників числа t (аналог теореми Мостовського-Успенського);

- строгий скінченний R_{(s, t)} -перетворювач B=(K_B, H_B, q₀), такий що і Dom(f_B)=D_s, існує тоді і тільки тоді, коли s=tⁿ для деякого натурального числа nОN⁺.

Побудовано скінченний R₁²-перетворювач, котрий задає криву Пеано з коефіцієнтом перекриття 3, найменшим можливим.

Показано, що для довільної заданої HIFS, котра визначає систему компактних множин, можна побудувати систему -перетворювачів A_i, множини станів яких містять стани q_i, такі що Dom()=C_i за , 1ЈiЈd₂. Розглянуто умову, за якої такий перетворювач є скінченним, і побудовано скінченний RA_{[0, 1]} -перетворювач, який задає незамкнену множину

За результатами роботи можна побудувати таблицю, що відображає зв'язок між класами дійсних функцій, описуваних у термінології класичного аналізу, і класами функцій, визначених певними типами перетворювачів над надсловами.

Класи дійсних функцій Класи функцій, визначених		тотожня функція f(x)=x	афінні перетворення вигляду Mx+h з раціональними М, множини	диференційовні на інтервалі	характеристичні функції фрактальних множин, визначених HIFSами
Скінченними Rnn перетворювачами	n=1	P є декартів добуток відрізків, напів-замкнених променів, або числових осей (н. і д. умова визначена у теоремі 4.2.)	частинний випадок магазинних Rnn-пере-творювачів, n=1	частинний випадок скінченних -перетворювачів m=n
магазинними Rnn -перетворювачами	зводиться до випадку скінченних Rnn перетворюва-чів	частинний випадок скінченних Rnn -перетворювачів	є лінійними на цьому ін-тервалі	частинний випадок магазинних-перетворювачів (у цій роботі не досліджувалися)
строгими скінченними R(s,t)mn -перетворювачами (вважається, що s, t - фіксовані, більші за 1, натуральні числа)	К, н. і д. умова: s=tn для деякого натурального числа nОN+..	За n=m класи нерівні і мають непорожній перетин	класи нерівні і мають непорожній перетин	частинний випадок скінченних -перетворювачів
строгими R(s,t)mn -перетворювачами	К, н. і д. умова: множи-на простих ді-льників числа s включає мно-жину простих дільників числа t	За n=m класи нерівні і мають непорожній перетин	класи нерівні і мають непорожній перетин	частинний випадок скінченних -перетворю-вачів.
скінченними -перетворювачами	(?): постає питання про взаємо-вплив вхідних відрізків і вихідної двійкової системи числення	За n=m=1 зводиться до випадку скінченних Rnn -перетворювачів	(?): аналогічно скінченним Rnn -перетво-рювачам	К, д. умова ви-значена в наслідку 7.1
1	2	3	4	5
-перетворювачами	(?): постає питання про взаємовплив вхідних відрізків і ви-хідної двійко-вої системи чи-слення	За m=n=1 зводиться до ви-падку скінченних - Rnn перетвoрювачів	m=1 аналогічно висновку Лісовика про визна-чуваність неперерв-них функцій -перетво-рювачами	К

Табл. 1. Знак теоретико-множинного відношення у клітині таблиці позначає відношення класу функцій, визначеного відповідним рядком, до класу функцій, визначеного відповідним стовпчиком. (?) позначає відкрите питання або гіпотезу.



Результати роботи можна використовувати для подальших досліджень обчислюваності дійсних функцій за допомогою перетворювачів, для досліджень у галузі теорії фракталів, і математичному аналізі - для побудови неперервних функцій з нескінченними множинами точок недиференційовності. Результати, що стосуються побудови алгоритмів обчислення дійсних функцій (наприклад, кривої Пеано), можна також застосовувати в прикладному програмуванні.



СПИСОК ОПУБЛІКОВАНИХ ПРАЦЬ АВТОРА

1. L.P. Lisovik, O. Yu. Shkaravskaya. Real functions defined by transducers // Тезисы Второй Международной конференции “Математические алгоритмы”. - 1995. - С. 34-35;

2. Лисовик Л.П., Шкаравская О.Ю. Функции, определяемые преобразователями с магазинной памятью // Доповіді НАН України. - 1995. - № 9. - C. 57 - 59;

3. Лисовик Л.П., Шкаравская О.Ю. О вещественных функциях, задаваемых преобразователями // Кибернетика и системный анализ. - 1998. - № 1. - C. 82 - 93.

4. Шкаравская О. Ю. Афинные отображения, задаваемые конечными преобразователями // Кибернетика и системный анализ. - 1998. - № 5. - C. 178 - 181 .



АНОТАЦІЯ

Шкаравська О.Ю. Класи функцій, визначених перетворювачами над надсловами. - Рукопис.

Дисертація на здобуття наукового ступеня кандидата фізико-математичних наук за спеціальністю 01.01.08 - математична логіка, теорія алгоритмів і дискретна математика. - Київський університет імені Тараса Шевченка, Київ, 1999.

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

Розв'язано проблему характеристики класу функцій, диференційовних на заданому інтервалі, які визначаються магазинними R-перетворювачами. Розкрито зв'язок між ієрархічними ітерованими функціональними схемами і -перетворювачами. Розроблено алгоритм побудови перетворювача, що задає афінне відображення підмножини n-вимірного простору. Побудовано скінченний R₁²-перетворювач, який задає криву Пеано з найменшим можливим коефіцієнтом перекриття, 3.

Ключові слова: R_(s,t)mⁿ -перетворювач, скінченний R-перетворювач, магазинний R-перетворювач, лінійна функція, афінне перетворення, зображення числа, крива Пеано, ієрархічна ітерована функціональна система(схема), -перетворювач.

Шкаравская О.Ю. Классы функций, определяемых преобразователями над сверхсловами. - Рукопись.

Диссертация на соискание ученой степени кандидата физико-математических наук по специальности 01.01.08 - математическая логика, теория алгоритмов и дискретная математика. - Киевский универcитет имени Тараса Шевченко, 1999.

В работе рассматриваются классы преобразователей над бесконечными символьными представленями вещественных чисел. Исследуются вычислительные возможности таких преобразователей как средств задания действительных функций и фрактальных множеств.

Решена проблема характеристики класса функций, дифференцируемых на заданном интервале, которые определяются магазинными R-преобразователями. Раскрыта связь между иерархическими итерированными функциональными схемами и -преобразователями. Также разработан алгоритм построения преобразователя, задающего аффинное отображение подмножества n-мерного пространства. Построен конечный R₁²-преобразователь, задающий кривую Пеано с наименьшим возможным коеффициентом перекрытия, 3.

Ключевые слова: R_(s,t)mⁿ-преобразователь, конечный R-преобразователь, магазинный R-преобразователь, линейная функция, аффинное преобразование, представление числа, кривая Пеано, иерархическая итерированная функциональная система (схема), -преобразователь.

Shkaravska O. Yu. Classes of the functions defined by transducers over superwords. - Manuscript.

Thesis сandidate of physics and mathematics by speciality 01.01.08 - mathematical logics, theory of algorythms and discrete mathematics. - Kyiv Taras Shevchenko University, Kyiv, 1999.

In this paper, are considered the classes of transducers over infinite symbolic representations of real numbers. The computational potentialities of these transducers as means of defining continuous real functions and fractal sets are studied.

Turing machines, in particular finite automata, can define real functions. From this point of view the finite automata and generalized sequential machines were first studied by S.Eilenberg. A finite automaton sequentially works over the finite binary expansion of x to define f(x) for the corresponding function f.

The notion of the -transducer introduced by L.P.Lisovik generalizes Eilenberg's approach.

Finite -transducers can be asynchronic and define the mappings of binary expansions into the set of so called overflowed expansions. (The symbol 2 is allowed in the overflowed expansion of an arbitrary real number). Later on the notion of the -transducer was generalized by the notions of the -transducer, -transducer and -transducer. An -transducer has m input and n output tapes; an-transducer works over the base-s expansions and builds the base-t expansions (if it builds output expansions without overflowed symbols, it is called strict); an -transducer works over the still more general representations of real numbers. This approach in defining real functions is constructive on the one hand, but it differs from the traditional theories in constructive analysis, on the other hand.

The constructive real functions are defined on the constructive real numbers. The latter ones can be roughly considered as algorithms of approximation of “ordinary” real numbers. Note that we don't restrict ourselves by constructive expansions dealing with transducers.

The -transducers can be classified according to the type of their memory. They could be finite, push-down, stack, C-machines or transducers of a common form with a countable number of states.

L.P.Lisovik has shown that an arbitrary continiuos function or function with the 1^st order discontinuity can be defined by the corresponding -transducer. Thus we have a new criterion of classification of these functions, based on power and structure of the memory of the corresponding transducers. From the practical point of view the transducers are algorithms that calculate the values the functions with an arbitrary precision. Also, the transducers can be considered as means for defining the recursive fractal sets and functions on these sets. In this thesis, the following new results are presented:

it has been shown that the class of the functions differentiable on a given interval and defined by a push-down -transducer is included in the class of the functions linear on the interval;

the necessary and sufficient condition under which the affine mapping, with the rational parameters, of the given subset of the space can be defined by a finite -transducer has been considered;

the generalization of Mostovsky-Uspensky theorem on translation of constructive real numbers for the finite -transducers has been proved: the strict -transducer defining the identity map exists iff the set of the prime divisors of s is included in the set of the prime divisors of t;

the -transducer for Peano curve with the best overlapping coefficient 3 and the function mapping the unit segment onto Serpinsky carpet hve been built;

it has been proved that for an arbitrary hierarchical iterated function system (HIFS) one can build the system of -transducers (which generalize the notion of an -transducer) that define the same vector of the compact sets from as a given HIFS; the -transducer defining the set that is not closed has been built.

All the statements listed above are based on recursive nature of transducers, i.e on iteration or “almost iteration” of the commands of the given transducer while it is working over the infinite expansion of a real number. Also the “trace technique” has been used.

Key words: R_(s,t)mⁿ -transducer, finite R-transducer, push-down R-transducer, linear function, affine mapping, expansion of a number, space-filling curve, hierarchical iterated function system (schema), -transducer.

Размещено на Allbest.ru