maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2019-2-306-311mais-1220Research ArticleAlgorithmseT-сводимость множествeT -reducibility of Setshttps://orcid.org/0000-0003-1604-5599ЯруллинРоман РевовичIarullinRoman R.

Аспирант.

Ул. Ермака, 99, Иваново, 153025

 

Graduate student.

99 Ermaka str., Ivanovo, 153025

iarul1402@yandex.ruИвановский государственный университетРоссияIvanovo State UniversityRussian Federation201928062019262306311Copyright © Яруллин Р.Р., 20192019Яруллин Р.Р.Iarullin R.R.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/1220

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

This paper is dedicated to the study of eT -reducibility — the most common in the intuitive sense of algorithmic reducibility, which is both enumeration reducibility and decidable one. The corresponding structure of degrees — upper semilattice of eT -degrees is considered. It is shown that it is possible to correctly define the jump operation on it by using the T-jump or e-jump of sets. The local properties of eT -degrees are considered: totality and computably enumerable. It is proved that all degrees between the smallest element and the first jump in DeT are computably enumerable, moreover, these degrees contain computably enumerable sets and only them. The existence of non-total eT -degrees is established. On the basis of it, some results have been obtained on the relations between, in particular, from the fact that every eT -degree is either completely contained in some T -or e-degrees, or completely coincides with it, it follows that non-total e-degrees contained in the T-degrees, located above the second T -jump, coincide with the corresponding non-total eT -degrees.

eT-сводимостьeT-степениeT-скачокeT-reducibilityeT-degreeseT-jumpReferencesРоджерс Х., Теория рекурсивных функций и эффективная вычислимость, М.: Мир, 1972.Rogers H., Theory of Recursive Functions and Effective Computability, The MIT Press, 1987, (in Russian).Соар Р. И., Вычислимо перечислимые множества и степени, Казань: Казанское математическое общество, 2000.Soare Robert I., Recursively Enumerable Sets and Degrees, Springer, 1999.Ходжаянц М.Ю., “О структуре е-степеней”, Известия АН АрССР «Математика», XV:№ 3 (1980), 165-175.Hodzhayanc M.YU., “O strukture e-stepenej”, Izvestiya AN ArSSR “Matematika”, XV:3 (1980), 165-175.Поляков Е. А., Розинас М.Г., Теория алгоритмов, Иваново: Из-во ИВГУ, 1976.Polyakov E. A., Rozinas M. G., Teoriya algoritmov, Ivanovo: IVGU, 1976.Kleene S.C., Post E.L., “The upper semi-lattice of degrees of recursive unsolvability”, Annals of Mathematics, 59 (1954), 379-407.Kleene S.C., Post E.L., “The upper semi-lattice of degrees of recursive unsolvability”, Annals of Mathematics, 59 (1954), 379-407.Case J., “Enumeration reducibility and partial degrees”, Annals of Mathematical Logic, 2:4 (1971), 419-439.Case J., “Enumeration reducibility and partial degrees”, Annals of Mathematical Logic, 2:4 (1971), 419-439.Розинас М.Г., “Операция скачка для некоторых видов сводимости”, ВИНИТИ Деп. 3185-76.Rozinas M. G., “Operaciya skachka dlya nekotoryh vidov svodimosti”, VINITI Dep. 3185-76.Медведев Ю. Т., “Степени трудности массовых проблем”, Докл. АН СССР, 104 (1955), 501-504;Medvedev YU. T., “Stepeni trudnosti massovyh problem”, Dokl. ANSSSR, 104 (1955), 501-504.Ходжаянц М.Ю., “е-степени, T-степени и аксиоматические теории”, ДАН АрмССР, 73:2 (1981), 73-77.Hodzhayanc M. Yu., “e-stepeni, Т-stepeni i aksiomaticheskie teorii”, DAN ArSSR, 73:2 (1981), 73-77.Солон Б.Я., “Соотношения между е-степенями и Т-степенями”, Известия высших учебных заведений, “Математика", 3 (1995), 51-61.Solon B.YA., “O sootnoshenie mezhdu e-stepenyami i T-stepenyami”, Izvestiya vuzov, “Matematika”, 3 (1995), 51-61.

The authors declare that there are no conflicts of interest present.