Анотація до роботи:

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

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

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

Інструмент обмежених 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.