eT-сводимость множеств


https://doi.org/10.18255/1818-1015-2019-2-306-311

Полный текст:


Аннотация

Статья посвящена eT-сводимости - самой общей в интуитивном смысле алгоритмической сводимости, являющейся одновременно сводимостью по перечислимости и сводимостью по разрешимости. Рассматривается соответственная степенная структура - верхняя полурешётка eT-степеней. Показано, что на ней можно корректным образом определить операцию скачка, используя Т -скачок или е-скачок множеств. Рассмотрены локальные свойства eT-степеней: тотальность и перечислимость. Доказано, что все степени между наименьшим элементом и первым скачком в DeT являются вычислимо перечислимыми, более того, эти степени содержат вычислимо перечислимые множества и только их. Установлено существование нетотальных еТ -степеней. На основе этого получены некоторые результаты о соотношениях между степенями, в частности, из того, что всякая eT-степень или содержится полностью в некоторой Т - или е-степени, или полностью совпадает с ней, следует, что нетотальные е-степени, содержащиеся в Т-степенях, расположенных выше второго Т -скачка, совпадают с соответствующими нетотальными еТ -степенями.


Об авторе

Роман Ревович Яруллин
Ивановский государственный университет
Россия
Аспирант.Ул. Ермака, 99, Иваново, 153025 


Список литературы

1. Роджерс Х., Теория рекурсивных функций и эффективная вычислимость, М.: Мир, 1972.

2. Соар Р. И., Вычислимо перечислимые множества и степени, Казань: Казанское математическое общество, 2000.

3. Ходжаянц М.Ю., “О структуре е-степеней”, Известия АН АрССР «Математика», XV:№ 3 (1980), 165-175.

4. Поляков Е. А., Розинас М.Г., Теория алгоритмов, Иваново: Из-во ИВГУ, 1976.

5. Kleene S.C., Post E.L., “The upper semi-lattice of degrees of recursive unsolvability”, Annals of Mathematics, 59 (1954), 379-407.

6. Case J., “Enumeration reducibility and partial degrees”, Annals of Mathematical Logic, 2:4 (1971), 419-439.

7. Розинас М.Г., “Операция скачка для некоторых видов сводимости”, ВИНИТИ Деп. 3185-76.

8. Медведев Ю. Т., “Степени трудности массовых проблем”, Докл. АН СССР, 104 (1955), 501-504;

9. Ходжаянц М.Ю., “е-степени, T-степени и аксиоматические теории”, ДАН АрмССР, 73:2 (1981), 73-77.

10. Солон Б.Я., “Соотношения между е-степенями и Т-степенями”, Известия высших учебных заведений, “Математика", 3 (1995), 51-61.


Дополнительные файлы

Для цитирования: Яруллин Р.Р. eT-сводимость множеств. Моделирование и анализ информационных систем. 2019;26(2):306-311. https://doi.org/10.18255/1818-1015-2019-2-306-311

For citation: Iarullin R.R. eT -reducibility of Sets. Modeling and Analysis of Information Systems. 2019;26(2):306-311. (In Russ.) https://doi.org/10.18255/1818-1015-2019-2-306-311

Просмотров: 47

Обратные ссылки

  • Обратные ссылки не определены.


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)