Київський національний університет

імені Тараса Шевченка

КАРНАУХ Тетяна Олександрівна

УДК 519.7+510.5

КЛАСИ ФУНКЦІЙ ТА ЧИСЕЛ, ЩО ВИЗНАЧАЮТЬСЯ

ТРАНСФОРМАЦІЙНИМИ ТА ГЕНЕРУЮЧИМИ МОДЕЛЯМИ ОБЧИСЛЕНЬ

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

і дискретна математика

Автореферат

дисертації на здобуття наукового ступеня

кандидата фізико-математичних наук

Київ – 2005

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

Робота виконана на кафедрі теоретичної кібернетики Київського національного університету імені Тараса Шевченка

Науковий керівник: доктор фізико-математичних наук, професор

ЛІСОВИК Леонід Петрович,

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

професор кафедри теорії та технології програмування

Офіційні опоненти: доктор фізико-математичних наук, професор

КАПІТОНОВА Юлія Володимирівна,

Інститут кібернетики імені В.М.Глушкова НАН України,

завідувач відділу теорії цифрових автоматів

кандидат фізико-математичних наук, доцент

ГАНЮШКІН Олександр Григорович,

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

доцент кафедри алгебри та математичної логіки

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

м. Київ

Захист відбудеться “--” листопада 2005 року о 14 годині на засіданні спеціалізованої вченої ради Д .001.18 Київського національного університету імені Тараса Шевченка за адресою: 03680, м. Київ-127, проспект академіка Глушкова, 2, корп. 7, Київський національний університет імені Тараса Шевченка, механіко-математичний факультет.

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

Автореферат розісланий “--6 ” жовтня 2005 року.

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

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

Актуальність теми. Теорія алгоритмів бере свій початок з середини 30-х років 20-го сторіччя, коли відбулись перші спроби дати точний математичний еквівалент загальному інтуїтивному представленню про алгоритм. Одним з таких уточнень поняття алгоритму є машини Тьюрінга. Одночасно з уточненням поняття алгоритму точне математичне значення отримує поняття обчислюваності.

На сьогодні доведено, що такі моделі, як числення рівностей Ербрана та Гьоделя, машини Тьюрінга, канонічні системи Поста, нормальні алгорифми Маркова мають однакові обчислювані можливості для класа арифметичних функцій (тобто функцій типу N0N0), а саме, задають клас частково рекурсивних функцій. За тезою Чьорча, сформульованою в 1936 році, клас функцій, обчислюваних за допомогою алгоритмів у широкому інтуїтивному розумінні, співпадає з класом частково рекурсивних функцій. За даних обставин загальна теорія частково рекурсивних функцій набула бурхливого розвитку.

В роботі Т. Хаяші 1975 року та в роботі Р. Гілмана 1996 року зявляються арифметичні функції, які задаються як неспадні функції, множина значень яких співпадає з множиною довжин слів мови. Якщо мову задано граматикою, то отримуємо принципово новий підхід до задання арифметичної функції – за допомогою граматики. Даний підхід є дуже цікавим для досліджень, оскільки дозволяє звузити загальний клас частково рекурсивних функцій за рахунок обмежень, які вводяться для граматики. Зокрема Хаяші та Ґілман розглядають індексні граматики.

Інша гілка розвитку теорії оперує з поняттям обчислюваного дійсного числа, яке вперше було введено в 1936 році А. Тьюрінгом. За першим означенням Тьюрінга під обчислюваним числом ми розуміємо число, двійковий розклад дробової частини якого є обчислюваним на машині Тьюрінга. Фактично обчислюваним числом є сама машина Тьюрінга, яка його обчислює. Дане означення має ряд суттєвих недоліків, оскільки, наприклад, унеможливлює побудову за двома обчислюваними числами, обчислюваного числа, яке є їх сумою. Тому надалі воно зазнало змін. Інші означення обчислюваного числа були сформульовані в 1936 році Банахом і Мазуром. Серед радянської школи слід зазначити внесок Шаніна в дослідження обчислюваних чисел. Крім різних концепцій обчислюваності дійсних чисел, дослідження розгортались і навколо такого напрямку як обчислювальні можливості алгоритмічних пристроїв для задання обчислюваних чисел. В 1990-х роках такі дослідження велись Л.П.Лісовиком та його учнями. Деякі питання, повязанні з часовими характеристиками та з трансцендентністю ще відкриті: чи можна обчислити число в реальний час (тобто так, щоб час, витрачений на обчислення його цифр лінійно залежав від кількості обчислених цифр); чи вірно, що кожне ірраціональне число, яке можна обчислити в реальний час, є трансцендентним. З іншого боку, актуальним є питання генерації трансцендентних чисел.

І, наприкінці, остання з найважливіших гілок розвитку поняття обчислюваності оперує поняттям обчислюваної дійсної функції. Різні підходи до поняття обчислюваної дійсної функції були запропоновані Банахом та Мазуром, Гржегорчиком, Марковим, Лісовиком.

R-перетворювачі Лісовика є узагальненням підходу С. Ейленберга. Для визначення значення f(x) R-перетворювач послідовно переробляє вхідне -слово – двійковий розклад числа x, – в двійковий розклад числа, яке трактується як f(x). Найсуттєвіша новація полягає в тім, що на виході крім звичайних двійкових знаків ще дозволяється використовувати так звані символи переповнення 2 і . R-перетворювачі можна класифікувати в залежності від потужності та структури памяті.

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

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

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

Мета і задачі дослідження. Оцінити можливості моделей обчислень з різними обмеженнями (на тип памяті та/або на подання результату обчислень) щодо задання арифметичних функцій, дійсних чисел та дійсних функцій. Вказати звязки між класом функцій, обчислюваних строгими реалами, та класами функцій, описуваних методами класичного аналізу.

Наукова новизна одержаних результатів. В дисертаційній роботі автором отримані нові теоретичні результати, зокрема—

досліджено властивості граматик з нестираючою стековою памяттю (зокрема доведено рекурсивність відповідних мов) ; —

побудовано гніздові стекові генератори, що обчислюють трансцендентні числа;—

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

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

Всі ці результати отримано вперше.

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

Особистий внесок здобувача. В розділі 2 викладено відомі результати, що використовуються у розділах 3-5. Формулювання теореми 3.2.6 належить науковому керівнику. Означення класа функцій IGF0 та формулювання теореми 3.2.5 отримано у співавторстві з науковим керівником. Усі інші наукові результати одержані здобувачем особисто.

Автор висловлює щиру подяку науковому керівнику – професору Леоніду Петровичу Лісовику за постійну увагу до роботи і допомогу в розвязанні складних питань, що виникали під час роботи над дисертацією. Також автор висловлює щиру подяку своїм рідним за їх підтримку та свому першому справжньому вчителю математики – Якіру Михайлу Семеновичу.

Апробація результатів дисертації. Результати дисертації доповідалися на міжнародній науковій конференції "Dynamical system modelling and stability investigation" (м. Київ, 2003 р.) в секції "Programming and logic-mathematical methods of modelling", на X-ій міжнародній науковій конференції імені академіка М.Кравчука (м. Київ, 2004 р.), на семінарі з фрактального аналізу при кафедрі вищої математики Національного педагогічного університету імені М.П. Драгоманова, на VI-й міжнародній науковій конференції "Дискретные модели в теории управляющих систем" (м. Москва, 2004 р.).

Публікації. Основні результати дисертації опубліковано у роботах [1-9], з яких [1-5] – у фахових виданнях з переліків, які затверджено ВАК.

Структура та обєм дисертації. Дисертація викладена на 188 сторінках машинописного тексту, включає перелік умовних позначень та означень, вступ, 5 розділів, висновки, список використаних джерел (на 5 сторінках), 2 рисунки, 6 додатків (на 38 сторінках). Другий, третій і четвертий розділи складаються з трьох підрозділів, пятий – з чотирьох підрозділів. Додаток Б складається з пяти розділів, додаток В – з сьоми розділів, дотаток Г – з двох розділів. Список використаних джерел складається із 56 найменувань, з них 22 іноземними мовами.

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

В першому розділі дисертації наведено огляд праць, присвячених теорії обчислюваності, різним генеруючим та трансформаційним моделям (перетворювачам, генераторам). Крім огляду моделей граматик та автоматів розглянуто моделі задання арифметичних функцій за допомогою формальних мов. Також висвітлено різні підходи до поняття обчислюваного дійсного числа (Тьюрінг, Банах, Мазур, Шанін, Мартін-Льоф, Лісовик) та обчислюваної дійсної функції (Банах, Мазур, Гржегорчик, Марков, Лісовик). Крім цього розглянуто основні результати теорії R-перетворювачів, започаткованої у 1987 році Л.П.Лісовиком.

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

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

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

виведений деякий термінальний символ (у цьому випадку автомат знищується);–

виведений один нетермінал (у цьому випадку автомат виконує один такт роботи);–

виведено два нетермінали, причому з кожним отриманим нетерміналом зв'язується точна копія автомата нетермінала (у цьому випадку ми можемо спостерігати процес копіювання пам'яті автоматів).

В залежності від властивостей памяті нетерміналів виникає класифікація граматик.

В теоремах 3.1.3.2-3.1.3.5 встановлюється замкненість класу мов T(Mem,m0) відносно обєднання, конкатенації, ітерації та перетину з регулярними мовами відповідно.

В теоремі 3.1.3.6 стверджується, що клас мов (Mem,m0) замкнений відносно послідовністного перетворення.

В теоремах 3.1.4.3, 3.1.5.1, 3.1.5.2, 3.1.5.4 встановлюється, що –

клас мов, породжуваних МТ-граматиками, збігається з класом мов, що розпізнаються машинами Тьюрінга;–

клас мов, породжуваних граматиками зі скінченною памяттю, збігається з класом контекстно-вільних мов;–

клас індексних мов співпадає з класом МП-мов;–

клас індексних мов не збігається з класом NES-мов і строго міститься в класі S-мов.

Одними з найважливіших результатів підрозділу 3.1, які використовуються надалі при характеризації NES-функцій є такі теореми.

3.1.6.4. Теорема. Для NES-граматики G розв'язна проблема L(G)=.

3.1.6.5. Теорема. Для NES-граматики G розв'язна проблема wL(G).

При доведенні теореми 3.1.6.4 "техніку слідів", яка дозволяє замінювати частини виведення, модифіковано для використання в випадку NES-граматик. Перетворення виконуються над деревом виведення. Також розроблено реалізацію цих замін таким чином, що при виконанні замін на однакове дерево виведення, явна заміна виконується тільки один раз, а в решті випадків фактично підставляється тільки посилання на відповідний фрагмент дерева виведення. Після виконання всіх необхідних для перетворення замін виконується так зване розвязання посилань. Такий спосіб дозволяє реально зменшити кількість входжень нетерміналів з найдовшими стековими словами у дерево виведення, чим гарантує скінченність загального процесу скорочення.

Також доведено такі властивості NES-мов

3.1.6.6. Теорема. Клас NES-мов не замкнений відносно перетину.

3.1.6.7. Теорема. Клас NES-мов в алфавіті не замкнений відносно доповнення.

Результати цього підрозділу використовуються у доведенні деяких тверджень підрозділа 3.3.

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

В загальному випадку в залежності від загальних обмежень та типу памяті граматики виникають клас функцій IGF та класи NES-функцій і S-функцій. В підрозділі 3.2 досліджується клас функцій IGF0.

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

3.2.4. Теорема. Клас IGF0 збігається з класом усіх строго зростаючих функцій з N+ у N+, що задаються системами лінійних рекурентних співвідношень з натуральними коефіцієнтами.

3.2.5. Теорема. Клас функцій IGF0 замкнений відносно операцій додавання, множення, сумування, додавання натуральної константи до результату і додавання натуральної константи до аргументу.

Також доведено, що клас IGF0 містить всі строго зростаючі на N+ і приймаючі на N+ позитивні значення поліноми з цілими коефіцієнтами.

Модель задання функції через перетворення памяті нетермінала в термінальне слово в процесі виведення також дозволяє задавати функції декількох аргументів (NES- та S-функції), які розглядаються в підрозділі 3.3. S-функції вводяться наступним чином. Розглянемо S-граматику G=(N,{a},{f},P,S0,$,), де

{S0, T, X}N,

P=P0P1,

P0={(S0,$#S0,$f#), (S0,$fS0,$ff), (S0,$#T,$#), (S0,$fT,$f),

(T,$fT, 1), (T, fT, 1),

(T,#X,0), (T,fX,0),(T,$#X,$#), (T,$fX,$f)}

причому в множині продукцій P1 нетермінали S0, T не зустрічаються і кожна пара з множини N$f, f, $, } є лівою частиною не більш ніж однієї продукції з множини P1. Будемо казати, що граматика G обчислює функцію h:N0N0N0 (можливо часткову) з областю визначення

Dom h={(n,m) | n,mN0, nm і w{a}* (X,(n,m))*w}, де

(n,m)=$fn-mfm при n>m і (n,n)=$fn,

якщо L(G)={ah(n,m) | (n,m)Dom h і (S0,$)*(X,(n,m))*ah(n,m)}.

При цьому функцію h будемо називати S-функцією. Якщо граматика G є NES-граматикою, то функцію h будемо називати NES-функцією.

В роботі також вказано звязок між функціями класу IGF0 та NES-функціями.

3.3.3. Теорема. Для функції f, що належить класу функцій IGF0, існує NES-функція h така, що f(x)=h(x,x) для всіх xN+.

3.3.4. Теорема. Область визначення довільної NES-функції є рекурсивною множиною.

Остання теорема дозволяє виділити з загального класу частково рекурсивних функцій підклас функцій з рекурсивною областю визначення. Якщо повернутись до задання функції за допомогою числення рівностей Ербрана-Гьоделя, то кожній NES-функції відповідатиме числення спеціального вигляду, яке можна інтерпретувати як систему рекурентних співвідношень з певними обмеженнями на зміну аргументів.

В четвертому розділі розглянуто обчислювані числа з декількох точок зору: з точки зору типу робочої памяті та з точки зору трансцендентності обчислюваного числа. В підрозділі 4.1 розглянуто числа, обчислювані генераторами із гніздовою стековою (ГС) памяттю, побудовано універсальну машину Тьюрінга для цього класу чисел та аналітично доведено існування чисел, для обчислення яких гніздової стекової памяті недостатньо.

4.1.3. Теорема. Існує універсальна машина Тьюрінга для класа дійсних чисел, обчислюваних за допомогою ГС-генераторів.

4.1.4. Теорема. Існують дійсні обчислювані числа, які не можна обчислити за допомогою ГС-генераторів.

В доведенні теореми 4.1.4 показано, що число x=||w||, де

w=

не може бути обчислено за допомогою гніздового стекового генератора, оскільки мова Pref {w} не є індексною.

Доведення останнього факту базується на замкненості класа індексних мов відносно лівого та правого ділення на регулярну мову та перетину з регулярними мовами, оскільки за допомогою цих операцій із мови Pref {w} можна отримати мову {}{| nN+}, яка не є індексною, бо швидкість зростання її слів перевищує експоненційну [Hayashi T. On derivation trees of indexed grammars – an extension of the uvwxy-theorem. // Publ. RIMS Kyoto Univ. – 1973. – Vol. 9, N 1. - P.61-92.].

В підрозділі 4.3 доведено, що гніздова стекова память дозволяє генерувати трансцендентні числа. Для цього здійснено аналітичну побудову зліченної множини трансцендентних чисел, обчислюваних ГС-генераторами:

4.2.2. Теорема. Існує нескінченна множина трансцендентних чисел, які можуть бути обчислені ГС-генераторами, а саме

{| mN, m3}.

В підрозділі 4.3 завдяки узагальненню метода канторовської діагоналі алгоритмічно побудовано інші множини трансцендентних обчислюваних чисел. Серцем конструкції є така теорема.

4.3.1. Теорема. Нехай для множини чисел A, AR, існує універсальна машина Тьюрінга MA. Тоді існує універсальна машина Тьюрінга MB, яка реалізує однозначну нумерацію зліченної множини чисел B, BR\A, і MB ефективно будується за машиною MA.

В доведенні метод канторовської діагоналі використовується наступним чином: нове число будується методом перетворення трійок дробових знаків послідовно пронумерованих чисел за такими правилами:

fp(p,abc)=001, якщо abc001,

fp(p,001)=010,

fp(i,abc)=101, якщо abc101 та ip,

fp(i,101)=110, якщо ip.

При цьому при різних значеннях параметра p отримуються різні обчислювані числа, відсутні в множині A.

З її допомогою отримано наступні результати:

4.3.3. Теорема. Існує зліченна множина обчислюваних трансцендентних чисел, які не можна обчислити за допомогою ГС-генераторів.

На відміну від аналітичного підхода до побудови обчислюваних чисел, що не можуть бути обчислені ГС-генераторами, запропонованому в підрозділі 4.1, в підрозділі 4.3 здійснено аналогічну побудову алгоритмічними методами:

4.3.4. Наслідок. Існує зліченна множина обчислюваних чисел, які не можна обчислити за допомогою ГС-генераторів.

Пятий розділ присвячено R-перетворювачам з обмеженнями. В підрозділі 5.1 обмеження накладаються на структуру памяті та словарну обробку -слів (коректність за входом та за виходом). Доведено такі теореми про суперпозицію.

5.1.7. Теорема. Нехай A1=(K1,H1,q1) -– строгий R–перетворювач з класом памяті (M,F) і з обмеженим виходом, A2=(K2,H2,q2) – скінченний R-перетворювач. Нехай також A1 є коректним за виходом або A2 є коректним за входом. Тоді існує R-перетворювач A3=(K3,H3,q3) з класом памяті (M,F) і з обмеженим виходом такий, що O(A3)=O(A1)O(A2).

5.1.8. Теорема. Нехай A1=(K1,H1,q1) – строгий скінченний R–перетворювач, A2=(K2,H2,q2) – R-перетворювач з класом памяті (M,F) (і з обмеженим виходом). Нехай також A1 є коректним за виходом або A2 є коректним за входом. Тоді існує R-перетворювач A3=(K3,H3,q3) з класом памяті (M,F) (і з обмеженим виходом) такий, що O(A3)=O(A1)O(A2).

Наслідки 5.1.9–5.1.14 узагальнюють властивості замкненості класів функцій типу RR, що можуть бути задані перетворювачами певного класу памяті, відносно суперпозиції. Деякі з отриманих результатів підрозділу 5.1 використовуються в підрозділі 5.4.

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

Основною ланкою доведення є наступна лема.

5.2.2. Лема. Нехай -слово wD має вигляд w=w0a1a2…an…, де ai0, iN+, та wi(n)=w0a1a2…anwi,nD (i=1,2). Тоді не існує строгого R-перетворювача A, результат роботи якого визначений над кожним зі слів w, w1(n), w2(n), nN+, і такого, що ||fA(w)||R2\{0} і для всіх nN+ виконано

||fA(w1(n))||<||fA(w)||<||fA(w2(n))||.

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

Доведення леми 5.2.2 використовує той факт, що при зчитуванні деякого скінченного вхідного префікса -слова w R-перетворювач A повинен вирішити у якому вигляді він буде видавати вихідне число: у фінальному або у кофінальному. При цьому рішенні на вихідній стрічці вже надруковано деякий префікс вихідного -слова. В залежності від рішення, прийнятого R-перетворювачем, у разі строгої моделі обчислень йому на вхід подається одне з -слів w1(n), w2(n) так, щоб порушувалась одна з нерівностей

||fA(w1(n))||<||fA(w)||<||fA(w2(n))||.

5.2.3. Теорема. Нехай функція f:RR задається строгим R-перетворювачем, тоді справедливі наступні твердження

x(Dom f)\(R2\{0}) (f(x)R2\{0}

x(Lmin(f)Rmin(f))(Lmax(f)Rmax(f))), (5.7)

x(Dom f)R2 (f(x)R2\{0} x<0 xLmin(f)Lmax(f)), (5.8)

x(Dom f)R2 (f(x)R2\{0} x>0 xRmin(f)Rmax(f)). (5.9)

5.2.6. Теорема. Нехай f: RR неперервна функція, що задається строгим псевдореалом (реалом), тоді виконуються умови (5.7) і

x(Dom f)R2 (f(x)R2\{0} x(Lmin(f)Lmax(f))(Rmin(f)Rmax(f))) (5.10)

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

5.2.8. Наслідок. Функції xn, n2, nN+, ex, ln x, sin x, cos x, tg x не можуть бути задані строгими R-перетворювачами.

5.2.9. Наслідок. Лінійна функція ax+b, де a, bR2\{0}, визначена на відрізку [-; ], >0, не може бути задана строгим R-перетворювачем.

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

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

f(x)=1 при x<0.5,

f(x)= - 4x+4.5-32-2i-1 при 1-2-2i-1x<1-32-2i-3, iN0,

f(x)= -2x+2.5-1.52-2i-1 при 1-32-2i-3x<1-2-2i-2, iN0,

f(x)= 4x-3.5+1.52-2i-1 при 1-2-2i-2x<1-32-2i-4, iN0,

f(x)= 2x-1.5+0.752-2i-1 при 1-32-2i-4x<1-2-2i-3, iN0,

f(x)= 0.5 при x1.

Одним з основних висновків з цього прикладу є така теорема.

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

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

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

5.3.10. Теорема. Нехай SP={Si}iN0 – монотонна послідовність замкнених неперервних систем кубиків така, що Pr1(Si)=R, iN0, і 1) fSP(0)R2\{0}, причому функція fSP в точці x=0 має нестрогий локальний екстремум, або 2) fSP(0)R\(R2\{0}). Тоді функція fSP може бути задана строгим реалом.

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

5.4.7. Теорема. Неперервна всюди визначена на R функція f:RR, що задовольняє умовам (5.7) і (5.10), може бути задана строгим реалом.

Найголовнішим висновком розділу 5 є такий критерій можливості задання всюди визначеної неперервної дйсної фукнції строгим реалом:

5.4.9. Теорема. Неперервна всюди визначена функція f:RR може бути задана строгим реалом тоді і тільки тоді, коли вона задовольняє умовам (5.7) і (5.10).

Отримана характеризація функцій, обчислюваних строгими R-перетворювачами, може стати у нагоді при розвязанні такого питання: чи вірно, що кожну неперервну визначену на відрізку [0;1] функцію можна подати як суму двох неперервних визначених на відрізку [0;1] функцій, які задаються строгими R-перетворювачами або строгими реалами.

На закінчення необхідно відзначити, що основною складністю при побудові послідовності систем є перехід до наступної системи послідовності, а точніше поділ кубика. У випадку функцій, що задаються строгими реалами, завжди можна зробити поділ кубика на скінченне число кубиків. Якщо ж тотальна функція задається строгим R-перетворювачем, що не є реалом, то мова може йти про зліченну множину одержуваних кубиків. Проте, розглянутий метод допускає модифікацію, яка дозволяє одержати аналогічний критерій для випадку R-перетворювача, який не є реалом, [7].

ВИСНОВКИ

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

Сформулюємо основні результати дисертації —

досліджено властивості граматик з нестираючою стековою памяттю (зокрема доведено рекурсивність відповідних мов);—

побудовано гніздові стекові генератори, що обчислюють трансцендентні числа;—

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

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

Крім цього в дисертації отримано низку цікавих результатів:—

отримано характеризацію класа функцій, абсолютно обчислюваних за допомогою індексних граматик, в термінах систем лінійних рекурентних співвідношень;—

побудовано машини Тьюрінга, що обчислюють трансцендентні числа, не обчислювані гніздовими стековими генераторами;—

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

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

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

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

СПИСОК ОПУБЛІКОВАНИХ РОБІТ ЗА ТЕМОЮ ДИСЕРТАЦІЇ

1. Карнаух Т.О. Класи пам'яті R-перетворювачів. //Вісник Київського університету. Серія: фіз.-мат. науки. – 2003. – №2. – C. 148-154.

2. Карнаух Т.О. Обчислюваність трансцендентних чисел генераторами з гніздовою стековою пам'яттю. // Вісник Київського університету. Серія: фіз.-мат. науки. – 2003. – №3. – C. 216-220.

3. Карнаух Т.О. Граматики з пам'яттю. // Вісник Київського університету. Серія: фіз.-мат. науки. – 2004. – №2. – C. 245-252.

4. Карнаух Т.О. Про один метод апроксимації дійсних функцій // Вісник Київського університету. Серія: фіз.-мат. науки. – 2004. – №3. – C. 215-222.

5. Карнаух Т.О. Моделювання дійсних функцій строгими R-перетворювачами. // Вісник Київського університету. Серія: фіз.-мат. науки.–2004. – №4. – C. 192-200.

6. Лисовик Л.П., Карнаух Т.А. О классе функций, вычислимых с помощью индексных грамматик. // Кибернетика и системный анализ. – 2003. – №1. – C. 108-115.

7. Карнаух Т.О. Особливості моделювання неперервних функцій R-перетворювачами. // "Dynamical system modelling and stability investigation", thesis of conference reports. – 2003. – C. 401.

8. Карнаух Т.О. Словарні методи побудови трансцендентних чисел. // Десята міжнародна наукова конференція імені академіка М. Кравчука, 13-15 трав. 2004р., Київ: Матеріали конф. – К.:Задруга, 2004. – C. 123.

9. Карнаух Т.А. Об одном механизме управления выводом в грамматиках. // Дискретные модели в теории управляющих систем: VI международная конференция: Москва, 7-11 декабря 2004 г. Труды. – М.: Издательский отдел Факультета ВМиК МГУ им. М.В.Ломоносова, 2004. – С.116-120.

Карнаух Т.О. Класи функцій та чисел, що визначаються трансформаційними та генеруючими моделями обчислень. – Рукопис.

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

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

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

Ключові слова: обчислюваність, граматика з памяттю, строгий реал, трансцендентне число, гніздовий стековий генератор.

Карнаух Т.А. Классы функций и чисел, задаваемые трансформационными и генерирующими моделями вычислений. – Рукопись.

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

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

В диссертации введено понятие грамматики с памятью. Грамматика с памятью это обобщение КС-грамматики, в котором правила вывода бесконтекстны, но с терминалами связаны состояния памяти, которые управляют выводом и при этом могут изменяться и наследоваться при выводе нетерминалов. На базе грамматик с памятью введено понятие NES-функции, а также исследованы свойства грамматик с нестирающей стековой памятью (в частности доказана рекурсивность соответствующих языков).

В доказательстве разрешимости проблемы пустоты для NES-грамматик используется модифицированная "техника следов". Преобразования выполняются над деревом вывода, при этом замены выполняются так, что не происходит дублирования подставляемых фрагментов дерева вывода: используются ссылки на соответствующий фрагмент, а после происходит "разрешение ссылок". Этот способ позволяет уменьшить количество вхождений нетерминалов с длиннейшими стековыми словами в дерево вывода, чем гарантирует конечность процесса сокращения вывода. Данное сокращение вывода сводит вопрос о пустоте NES-языка к пустоте соответствующего контекстно-свободного языка.

Вычисление арифметической функции с помощью грамматики задается посредством преобразования памяти нетерминала в слово в однобуквенном терминальном алфавите. Также показано, что класс функций, абсолютно вычислимых с помощью индексных грамматик, совпадает с классом строго возрастающих функций типа N0N+, задаваемых системами линейных рекуррентных соотношений с натуральными коэффициентами.

Кроме того, построены гнездовые стековые генераторы, вычисляющие трансцендентные числа. В работе показано, что существует универсальная машина Тьюринга для множества действительных чисел, вычислимых гнездовыми стековыми генераторами. Поэтому на основании существования универсальной машины Тьюринга для множества алгебраических действительных чисел с помощью модифицированного метода диагонализации Кантора построено счетное множество машин Тьюринга, вычисляющих трансцендентные числа, не вычислимые гнездовыми стековыми генераторами.

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

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

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

Ключевые слова: вычислимость, грамматика с памятью, строгий реал, трансцендентное число, гнездовой стековый генератор.

Karnaukh T.O. Function and number classes defined by transducers and generators. — Manuscript.

The thesis for obtaining the Candidate of Physical and Mathematical degree on the speciality 01.01.08 — Mathematical Logic, Theory of Algorythms and Discrete Mathematics. — Kyiv National Taras Shevchenko University, Kyiv, 2005.

This work is devoted to the investigation of the computational models with different constraint (on memory type and/or output representation) with regard to their abilities to specify arithmetical functions, real numbers and real functions. Interconnections between classes of real functions, which are computable by strict R-transducer-reals, and real functions, described in terms of classical analysis, are established.

In this work properties of grammars with memory, in particular with nonerasing stack memory, are investigated. Also nested stack generators for computing transcendental numbers are built. For continuous total real function necessary and sufficient conditions for its defining by strict R-transducer-real are obtained.

Key words: computability, grammar with memory, strict R-transducer-real, transcendental number, nested stack generator.