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

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

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

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

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

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

m-звідність з інформаційними обмеженнями

БЄЛЯЄВ Володимир Миколайович

Київ-2006

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

Робота виконана в Одеському національному університеті імені І.І. Мечникова Міністерства освіти і науки України

Науковий керівник

доктор фізико-математичних наук, професор Варбанець

Павло Дмитрович, Одеський національний університет імені І.І. Мечникова, завідувач кафедри комп'ютерної алгебри та дискретної математики.

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

доктор фізико-математичних наук, професор Оманадзе Роланд Шалвович, Тбіліський державний університет імені Ів. Джавахішвілі, Інститут прикладної математики імені І. Векуа, професор кафедри дискретної математики, м. Тбілісі, Грузія;

доктор фізико-математичних наук, професор Лісовик Леонід Петрович, Київський національний університет імені Тараса Шевченка, професор кафедри теорії програмування

Провідна установа

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

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

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

Автореферат розісланий “ 24 ” січня 2006 р.

Вчений секретар

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

Загальна характеристика роботи

Актуальність теми. Поняття алгоритму започатковувалось на самих ранніх етапах розвитку математики. Для відповіді на питання про існування алгоритмічного рішення можна обмежитись інтуїтивним поняттям алгоритму, оскільки достатньо лише запропонувати рішення і переконатися в тому, що процедура рішення є ефективною. У випадку ж необхідності упевнитися в зворотному, тобто у відсутності алгоритму, необхідна формальна характеризація алгоритму - потрібно показати, що застосування будь-якого алгоритму не дасть бажаного рішення. Такі характеризації були дані лише в 30-их роках минулого сторіччя в роботах К. Гьоделя, А. Тюрінга, А. Чьорча, Ж. Ербрана, Е. Поста і С. Кліні. Ці дослідники визначили різні поняття рекурсивних функцій і відповідні поняття рекурсивно перераховних множин, використовуючи, зокрема, абстрактні обчислювальні машини, схеми правил чи породжувальні граматики. Усі ці, на перший погляд, різні підходи визначали один клас функцій і клас множин.

Початок розвитку найважливіших розділів теорії алгоритмів - теорії рекурсивно перераховних множин і ступенів нерозв'язності - відносяться до ще більш пізнього часу - середини 40-их - початку 50-их років. Саме в ті роки були опубліковані фундаментальні роботи Е. Поста і С. Кліні, що містили не тільки первісні методи і результати теорії, але й визначили на найближчі два-три десятиріччя шляхи її розвитку.

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

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

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

Вивчення m-звідності, а також табличної і обмеженої табличної звідності було почато Е. Постом Post E.L. Recursively enumerable sets of positive integers and their decision problem. Bull. Amer. Math. Soc. - 1948. - v.54. - P. 641-642.. Мабуть, першим результатом у цьому напрямку була побудова Е. Постом m-повної множини. Попутно виникають і вивчаються поняття продуктивності і креативності множин, тісно пов'язаних з нумерацією рекурсивно перераховних множин. Трохи пізніше з'ясувалося, що класи 1-повних і m-повних множин збігаються і вони складаються з креативних множин. Цим було наведено перший приклад рекурсивно перераховного m-ступеня, що не розпадається, тобто m-ступеня, що складається з єдиного 1-ступеня.

Велику увагу приділяли дослідники співвідношенням між різними звідностями. Пізніше проблемою опису m-ступенів, що не розпадаються, займалися також П. Янг, К. Джокуш, Ю.Л. Єршов, Г.Н. Кобзєв. А. Лахлан показав Lachlan A.H. Two theorems on many-one degrees of recursively enumerable sets. Algebra and Logic. - 1972. -v.11, No 2. - P. 216-229., що кожен нерекурсивний р.п. T-ступінь містить мінімальний m-ступінь. Пізніше А.Н. Дьогтєв посилив цей результат. Він показав Дегтев А.Н. О частично упорядоченных множествах 1-степеней, содержащихся в рекурсивно-перечислимых m-степенях. Алгебра и логика. - 1976. - вып.15, No3.-С.248-266., з одного боку, існування такої р.п. множини, що частковий порядок 1-ступенів усередині її m-ступеня має найменший елемент; з іншого боку, для кожного існує р.п.м. така, що відповідний порядок має в точності мінімальних елементів.

Ю.Л. Єршов займався дослідженням верхніх напівґрат m-ступенів р.п. множин і показав, що вони не є ґратами. Дослідженням співвідношень між btt- і m-звідностями займався також Г.Н. Кобзєв. Серед робіт закордонних і вітчизняних дослідників у цій галузі потрібно відзначити також роботи Д. Майхіла, Д. Декера, Р. Фрідберга, Д. Шенфілда, М.М. Арсланова, Р.Ш. Оманадзе, С.С. Марченкова.

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

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

Мається на увазі використання звідностей (наприклад m-, tt-звідностей) з накладенням не часових чи зонних, але інформаційних обмежень на доступ до оракулів. Таким чином, множини в одному ступені виявляються зв'язаними ще й інформаційними обмеженнями зведення; і теорія рекурсивних функцій одержує більш тонкі засоби, ніж ті, що використовувались раніше. Ці засоби можна використовувати для вирішення нових питань про можливість тих чи інших побудов у теорії рекурсії.

Тут необхідно згадати роботи Булитко В.К. Субтьюринговы сводимости ограниченной сложности. Изв. вузов. Матем. - 1992. - No 1. - С.27-37.^, Bulitko V.K. About segment complexity of Turing reductions. Math. Log. Quart. - 1999. - v.45, i.4. - P.561-571. В.К. Булітко, в яких автор, використовуючи метод субтюрінгових звідностей, вирішив відому проблему характеризації повних максимальних множин, поставлену А. Лахланом і М.М. Арслановим, а також узагальнив відому теорему Р. Фрідберга про інверсію стрибка. Саме ідея інформаційних обмежень на функцію, що здійснює зведення (ідея, яка є підґрунтям визначення субтюрингових звідностей), лягла в основу досліджень цієї роботи.

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

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

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

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

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

дослідження структури ієрархії m-звідностей з інформаційними обмеженнями, а також окремих важливих їх класів;

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

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

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

Вивчається сукупність обмежених m-звідностей. Доведено, що ця сукупність утворює ґрати відносно природно визначених операцій. Класична необмежена m-звідність є найбільшим елементом у цих ґратах. Доведено, що єдиним ко-атомом у цих ґратах є звідність . Вивчаються аналогії і розбіжності цієї звідності і класичної 1_звідності.

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

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

Для структури ступенів нерозв'язності відносно звідності отримано критерій бути верхніми напівґратами.

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

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

Апробація результатів. Результати, отримані в дисертації, доповідалися: на семінарі “Теорія алгоритмів” в Одеському національному університеті ім. І.І. Мечникова; на всеукраїнській конференції “Алгебраїчні методи дискретної математики” (м. Луганськ, 2002 р.); на IV міжнародній алгебраїчній конференції в Україні (м. Львів, 2003 р.); на V міжнародній алгебраїчній конференції в Україні (м. Одеса, 2005 р.);

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

Особистий внесок. Основні результати дисертації досить повно відображені в 4 статтях і 4 тезах доповідей, з них стаття [1] виконана в співавторстві з В.К. Булітко. У статті [1] В.К. Булітко належать доведення теорем 5 і 8.

Структура й обсяг роботи. Дисертаційна робота складається з вступу, чотирьох розділів, висновку і списку літератури, викладених на 112 сторінках машинописного тексту. Список літератури містить 41 найменування. Роботу проілюстровано 6 рисунками.

Основний зміст роботи

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

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

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

Лема 1.4. Для довільної з.р.ф. з умовою можна побудувати такі, що і.

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

Теорема 1.6. Для довільних класів відношення рефлексивне тоді і тільки тоді, коли…

Теорема 1.7.

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

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

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

Теорема 1.10. Для довільних класів , що задовольняють умовам теорем 1.6 і 1.7, і довільних функцій таких, що наступні бінарні відношення є звідностями:

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

Теорема 1.11.

1)Верхній сингулярний зведений клас транзитивний тоді і тільки тоді коли він складається з гібридної функції типу для деякої загальнорекурсивної функції .

2)Якщо нижній транзитивний сингулярний зведений клас складається з функції , де - з.р.ф., тоді де . Якщо для тотальної виконується умова, що є -гібридною, тоді є сингулярним транзитивним нижнім класом.

Далі в роботі наводяться приклади негібридних сингулярних класів.

У другому розділі досліджується ієрархія обмежених m-звідностей, заснована на відношенні включення. Відомо, що класичні звідності впорядковані відношенням для звідностей, утворюють зростаючу послідовність. Кожна наступна звідність в цьому списку слабкіше попередніх. У літературі також досліджувалися табличні звідності з обмеженнями на типи функцій, які використовуються в табличних умовах. Ці звідності також утворюють нетривіальну ієрархію відносно включення. Позначимо множину обмежених m-звідностей, частково впорядкованих відношенням , через Пишемо якщо і . У підрозділі 2.1 доводиться наступна теорема, яка демонструє нетривіальність часткового порядку .

Теорема 2.1. Довільний зчисленний частковий порядок ізоморфно вкладається.

У підрозділі 2.2 доводиться наступна теорема, яка показує, що операції і в коректно визначають операції узяття найменшої верхньої і найбільшої нижньої межі:

Теорема 2.3. Множина утворює ґрати відносно операцій.

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

Теорема 2.4. В є єдиний ко-атом і немає атомів.

Далі в роботі звідність відіграє важливу роль, і тому для неї вводиться спеціальне позначення (m^*-звідність). Після цього в роботі розглянуті приклади елементів ґрат , а також ефективні способи породжувати нескінченні сукупності усе більш слабких звідностей і нескінченні сукупності усе більш сильних звідностей.

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

У підрозділі 3.1 на прикладі звідності , де - клас всіх поліномів з , демонструється подібна складність. Називаємо клас з.р.ф. перераховним, якщо існує рекурсивна функція така, що .

Пропозиція 3.1. Нехай звідність така, що й існують перераховні класи рекурсивних функцій з які мінорують і маорують відповідно. Тоді знайдуться рекурсивні множини.

Нижче під нетривіальним інтервалом для звідності ми будемо розуміти впорядковану пару -ступенів множин.

Теорема 3.2. Нехай звідність така, що й існують перераховні класи рекурсивних функцій з що мінорують і мажорують відповідно. Тоді існує ізоморфне вкладення довільної скінченої частково впорядкованої множини в довільний нетривіальний інтервал структури рекурсивних _ступенів.

Треба зазначити, що для m^*-звідності умови теореми не виконуються і існує лише 5 рекурсивних m^*-ступенів. Цією теоремою вирішується версія проблеми для обмежених m-звідностей, поставленої Р. Доуні і наведеної в списку відкритих питань теорії рекурсивних функцій.

У підрозділі 3.3 реалізована ідея застосування інструмента обмежених m_звідностей для визначення подібності на нечислових структурах за допомогою кодування і розбиття множин кодів на ступені нерозв'язності. Як наслідок, в предметній області визначаються класи подібності, члени яких, в залежності від обраної звідності, можуть мати істотні подібності, спільні властивості. В якості предметної області в підрозділі обрано множину нескінчених, в загальному випадку, дерев. Обрано також стандартне кодування дерев в підмножини . Далі ототожнюються всі множини, які є кодами таких укладок одного дерева, що від однієї такої укладки до іншої існує ефективний перехід. За допомогою m_звідностей з інформаційними обмеженнями природно виникають класи подібності дерев - два дерева потрапляють в один такий клас, якщо вони мають кодові множини з одного ступеня нерозв'язності відносно обмеженої m_звідності. Серія результатів підрозділу 3.3.3 демонструє, як спеціально обрані властивості дерев взаємодіють з інформаційними обмеженнями.

В четвертому розділі продовжене дослідження ступенів нерозв'язності для обмежених m-звідностей. Добре відомо Роджерс Х. Теория рекурсивных функций и эффективная вычислимость. - М.: Мир,  1972. - 624 с., що для класичних -звідностей структури відповідних ступенів нерозв'язності є верхніми напівґратами. У випадку ж накладення інформаційних обмежень досить низькі верхні границі можуть привести до такої патології, як відсутність точної верхньої межі для системи відповідних ступенів. Наступна теорема дає умову, необхідну і достатню для того, щоб структура ступенів нерозв'язності для обмеженої m-звідності була верхніми напівґратами.

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

В другому і третьому підрозділі продовжується вивчення m^*-звідності. Результати другого підрозділу демонструють аналогії і розбіжності m^*_звідності і класичної 1-звідності. 1-звідність не може бути представлена як обмежена m-звідність і відрізняється від m^*-звідності на рекурсивних множинах і на перераховних нерекурсивних множинах, однак за своїми властивостями вона досить близька до неї. Серед результатів цього підрозділу потрібно зазначити критерій циліндрів у термінах m^*_звідності і наслідки з нього - критерій m^*-нерозпадного m_ступеня, тобто m-ступеня, що складається з єдиного m^*-ступеня. Нагадаємо, що m-ступінь називається нерозпадним, якщо він складається з єдиного 1-ступеня.

Теорема 4.4. - циліндр

Наслідок 4.7. m-ступінь множини є нерозпадним тоді і тільки тоді, коли він m^*- нерозпадний.

У третьому підрозділі застосовується метод Янга для дослідження _розпадючогося m^*-ступеня, де мінорується перераховним підкласом . Звідності типу можна вважати, у деякому розумінні, ефективними апроксимаціями m^*-звідності.

Теорема 4.10. Якщо m^*-ступінь включає більш ніж один -ступінь, тоді він включає нескінченний ланцюг -ступенів.

У підрозділі 4.4 досліджується проблема повноти для обмежених m-звідностей. Сукупність множин будемо називати повною системою множин (п.с.м.) для звідності.

Очевидно, сукупність усіх р.п.м. утворює п.с.м. для довільної обмеженої m_звідності. Для класичної m-звідності п.с.м. складається з однієї множини - креативної множини. У випадку обмеженої m-звідності з поліноміальними верхніми обмеженнями п.с.м. також складається з однієї креативної множини. П.с.м. для даної звідності називаємо нетривіальною, якщо вона не включає ніякої повної для даної звідності множини. Наступні теореми доводять існування звідностей з нетривіальними п.с.м.:

Теорема 4.11. Для звідності не існує повних множин, де клас функцій.

Теорема 4.12. Нехай для звідності знайдеться лінійна функція . Тоді для звідності не існує повних множин.

Якщо досить низькі верхні границі звідності приводять до феномена відсутності повної множини, то істотні нижні обмеження приводять до суттєвого переносу структури множини, що зводиться, на оракул. У класі простих і псевдопростих множин підкласи T-повних множин зручно описуються Арсланов М.М. Локальная теория степеней неразрешимости и -множества. Казань.: Изд. КГУ, 1987. - 138с. за допомогою поняття слабкої ефективізації. Зв'язок між T-повнотою множини і T-повнотою множини , коли і оракул належить до класу простих або псевдопростих множин встановлює серія теорем 4.13-4.18.

Теорема 4.16. Нехай для р.п.м. виконуються наступні умови:

1) з нижньою границею г.р.ф.

2) 2-слабко ефективно проста

Тоді T-повна.

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

Висновки

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

Автор висловлює глибоку подяку науковому керівнику професору Варбанцю П.Д. і професору Булітко В.К. за увагу і підтримку в роботі, а також за корисну інформацію з теми дисертації.

Роботи автора за темою дисертації

[1] В.Н. Беляев, В.К. Булитко. m-сводимости с верхними и нижними ограничениями для сводящих функций. Математические заметки. - 2001. - Вып. 70, No 1. - С. 12-21.

[2] В.Н. Беляев. Структура степеней неразрешимости для m-сводимости с ограничениями на сводящую функцию. Вестник Одесского гос. ун-та. - 2001. - Том 6, вып. 3. Физ.-мат. науки. - С. 67-71.

[3] V.N. Belyaev. Strong reducibilities with restrictions on reducing function. Kalmar Workshop on Logic and Computer Science. - Szeged, Hungary. - 2003. - P. 81-87.

[4] V.N. Belyaev. On bounded m-reducibilities. Algebra and Discrete Mathematics. - Lugansk. - 2005. - №2 - P. 1-19.

[5] V.N. Belyaev. Reducibility with upper and low limits. - Bull. Symbolic Logic.- 2002.-vol. 8, No 1.- P. 166-167.

[6] В.М. Бєляєв. m-звідності з обмеженнями для функцій, що зводять. Матеріали всеукраїнської конференції "Алгебраїчні методи дискретної математики". - Луганськ, 2002. - С. 63-64.

[7] V.N. Belyaev. Reducibility with upper and low limits. 4th International Algebraic Conference in Ukraine. - Lviv. - 2003.- P. 38.

[8] V.N. Belyaev. On bounded m-reducibilities. 5th International Algebraic Conference in Ukraine. - Odessa. - 2005.- P. 29.

Бєляєв В.М. m-звідність з інформаційними обмеженнями. - Рукопис.

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

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

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

Беляев В.Н. m-сводимость с информационными ограничениями. - Рукопись.

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

Работа посвящена исследованию нового типа алгоритмических сводимостей, который возникает из-за информационных ограничений доступа к оракулу в m-редукциях. Изучаются пары классов неубывающих тотальных одноместных арифметических функций, которые определяют рефлексивные и транзитивные бинарные отношения. Установлены критерии рефлексивности и транзитивности таких отношений. Изучена решетка m-сводимостей с информационными ограничениями. Исследуется структура рекурсивно перечислимых степеней неразрешимости относительно m_сводимостей с информационными ограничениями. Получен критерий верхней полурешеточности для структуры степеней неразрешимости. Исследуются условия существования полных множеств. Получен критерий цилиндров в терминах m_сводимостей с информационными ограничениями.

Ключевые слова: рекурсивная функция, ограниченные сводимости, степени неразрешимости, мажоранта, классы информационных ограничений

Belyaev V.N. m-reducibility with informational restrictions. - Manuscript.

Thesis of a dissertation for obtaining the degree of candidate of sciences in physics and mathematics, specialty 01.01.08 - mathematical logic, algorithms theory and discrete mathematics. - Kyiv Taras Shevchenko university, Kyiv, 2005.

New type of algorithmic reducibilities, which occurs by the restrictions on the volume of oracle access in m-reductions, is investigated in the dissertation. Pairs of such classes of nondecreasing total one-place arithmetic functions that define reflexive and transitive binary relations are considered. Criteria of reflexivity and transitivity of such relations are found. The lattice of m-reducibilities with informational restrictions is investigated. The structure of recursively enumerable degrees for m-reducibilities with informational restrictions is studied. A criterion for the structure of unsolvability degrees to be an upper semi-lattice is obtained. The conditions of existence of complete sets are investigated. New characterization of cylinders in terms of m-reducibilities with informational restrictions is obtained.

Key words: recursive function, bounded reducibilities, degrees of unsolvability, majorant, classes of informational restrictions

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