Аскарбеккызы Акнур, Магистрант
ул. Аль-Фараби, 71, г. Алматы
Askarbekkyzy Aknur, Master Student
Al-Farabi Street, 71, Almaty, 050000
Баженов Николай Алексеевич, Кандидат физико-математических наук, старший научный сотрудник
г. Новосибирск, 630090
Bazhenov Nikolay Alekseevich, Candidate of Physical and Mathematical Sciences, Senior Researcher
Novosibirsk, 630090
В работе Баженова Н.А., Зубкова М.В., Калмурзаева Б.С. было начато исследование вопросов существования супремумов и инфимумов позитивных линейных предпорядков относительно вычислимых сводимостей бинарных отношений, в последней главе эти вопросы были рассмотрены в структуре вычислимых линейных порядков, изоморфных стандартному порядку натуральных чисел. Далее, в работе Аскарбеккызы А., Баженова Н.А., Калмурзаева Б.С. было продолжено исследование этой структуры. В последней работе немаловажную роль сыграло понятие самополных линейных порядков. Предпорядок R называется самополным, если для любой вычислимой функции g(x), осуществляющей сводимость R в R, ее область значений пересекает все supp(R)-классы. В данной статье оценивается точная алгоритмическая сложность индексных множеств всех самополных рекурсивных линейных порядков, изоморфных стандартному порядку натуральных чисел и целых чисел. Исследование индексных множеств позволяет оценить точную сложность различных понятий в исследуемых конструктивных структурах. Доказывается, что индексное множество самополных вычислимых линейных порядков, изоморфных стандартному порядку натуральных чисел, является П03-полным множеством. Доказывается, что индексное множество самополных вычислимых линейных порядков, изоиорфных стандартному порядку целых чисел, являетмя П03-полным множеством.
The work of Bazhenov N.A., Zubkov M.V., Kalmurzayev B.S. started investigation of questions of the existence of joins and meets of positive linear preorders with respect to computable reducibility of binary relations. In the last section of this work, these questions were considered in the structure of computable linear orders isomorphic to the standard order of natural numbers. Then, the work of Askarbekkyzy A., Bazhenov N.A., Kalmurzayev B.S. continued investigation of this structure. In the last article, the notion of a self-full linear order played important role. A preorder R is called self-full, if for every computable function g(x), which reduces R to R, the image of this function intersects all supp(R)-classes. In this article, we measure exact algorithmic complexities of index sets of all self-full recursive linear orders isomorphic to the standard order of natural numbers and to the standard order of integers. Researching the index sets allows us to measure exact algorithmic complexities of different notions in constructive structures, that we are investigating. We prove that the index set of all self-full computable linear orders isomorphic to the standard order of that we are investigating. We prove that the index set of all self-full computable linear orders isomorphic to the standard order of integers is П3 0-complete.
The authors declare that there are no conflicts of interest present.