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