КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер проекта 22-21-20024
НазваниеИнформационная выразительность степеней неразрешимости
Руководитель Арсланов Марат Мирзаевич, Доктор физико-математических наук
Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Казанский (Приволжский) федеральный университет" , Республика Татарстан (Татарстан)
Конкурс №65 - Конкурс 2022 года «Проведение фундаментальных научных исследований и поисковых научных исследований малыми отдельными научными группами» (региональный конкурс)
Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-101 - Математическая логика и основания математики
Ключевые слова CEA-оператор, тьюринговая сводимость, табличная сводимость, степень неразрешимости, гипериммунная степень, предполная нумерация, вычислимые функции, вычислимо перечислимое множество, низкое множество, иерархия Ершова, колмогоровская сложность, функция без неподвижных точек
Код ГРНТИ27.03.45
ИНФОРМАЦИЯ ИЗ ЗАЯВКИ
Аннотация
Для разъяснения трудностей трансляций между реализациями эквивалентных алгоритмов на разных устройствах в проекте используется подход, основанный на степенной (Т-, wtt-, tt- и другие сводимости) классификации классов множеств. Этот подход будет использован для определения понятия сложности класса функций с помощью полурешетки вычислимых нумераций этого класса. Такое понятие сложности класса функций во многих вопросах оказывается более полезным, чем известные понятия сложности отдельно взятых функций. Полурешетка вычислимых нумераций является весьма выразительным алгебраическим объектом, с помощью которого можно различать разнообразные внутренние структурные свойства классов вычислимо перечислимых множеств и частично вычислимых функций. Именно использование подходящих универсальных нумераций позволяет найти наиболее значимые теоремы о существовании, в частности теоремы о неподвижных точках вычислимых функций с той или иной степенью равномерности, которые по их значимости и месту могут быть сравнимы с основными теоремами существования в теории дифференциальных уравнений.
В связи с этим одним из фундаментальных направлений проекта является исследование тьюринговых степеней классов множеств с целью более тонкой их классификации на основе информации, закодированной в этих степенях. Хорошо известно, что основным средством для сравнения сложности множеств являются алгоритмические сводимости. Сложность множеств также может быть оценена с помощью ряда иерархий множеств (CEA-иерархии, иерархии Ершова, арифметической иерархии, иерархии высоких и низких множеств и др.). Проект предполагает исследование алгоритмической сложности множеств при помощи тьюринговой сводимости и некоторых других сводимостей, которые определяются наложением разного рода ограничений на вопросы к оракулу в тьюринговой сводимости, а также при помощи сравнений уровней множеств в различных иерархиях. Известны глубокие связи между алгоритмическими сложностями множеств в уровнях этих иерархий и колмогоровской сложностью вычислительных алгоритмов, задаваемых на этих множествах. Принятые в проекте методы исследования могут позволить получить новые серьезные результаты в этом направлении.
Таким образом, планируемые результаты с одной стороны логично продолжат разработку классических направлений теории вычислимости, а с другой стороны помогут по новому взглянуть на уровень информации, закодированный в множествах, близких к разрешимым.
ОТЧЁТНЫЕ МАТЕРИАЛЫ
Публикации
1.
Файзрахманов М.Х.
Extremal numberings and fixed point theorems
Mathematical Logic Quarterly, № 4, Т. 68, С. 398-408. (год публикации - 2022)
10.1002/malq.202200035
2.
Морозов А.С., Пузаренко В.Г., Файзрахманов М.Х.
Семейства перестановок и идеалы тьюринговых степеней
Алгебра и логика, Т.61, №6, С.706–719 (год публикации - 2023)
10.33048/alglog.2022.61.603
3. Морозов А.С., Пузаренко В.Г., Файзрахманов М.Х. Группы перестановок и идеалы тьюринговых степеней Алгебра и логика (год публикации - 2023)
4.
Файзрахманов М.Х.
Splitting of c.e. degrees and superlowness
Siberian Electronic Mathematical Reports, № 2, Т. 19, С. 578-585. (год публикации - 2022)
10.33048/semi.2022.19.048
5.
Калимуллин И.Ш., Лемпп С., Нг К.М., Ямалеев М.М.
On cupping and Ahmad pairs
Journal of Symbolic Logic (год публикации - 2023)
10.1017/jsl.2022.84
6.
Арсланов М.М.
On a general method of constructing Post reducibilities and the corresponding completeness criteria
Lobachevskii Journal of Mathematics, Vol. 43, P. 3430–3434 (год публикации - 2022)
10.1134/S1995080222150057
7.
Арсланов М.М.
Критерии полноты для одного класса сводимостей
Известия вузов. Математика, 10, 73-78 (год публикации - 2022)
10.26907/0021-3446-2022-10-73-78
Публикации
1.
Ямалеев М.М.
Isolation from Side and Cone Avoidance in the 2-Computably Enumerable wtt-Degrees
Journal of Mathematical Sciences (United States), V. 275, pages 54–65 (год публикации - 2023)
10.1007/s10958-023-06659-9
2.
Талипова А.И., Ямалеев М.М.
Неравномерность плотности вниз в n-вычислимо перечислимых тьюринговых степенях
Известия вузов. Математика, 2022, No. 11, С. 124–131 (год публикации - 2023)
10.26907/0021-3446-2022-11-124-131
3. Файзрахманов М.Х. Позитивные сводимости, экстремальные нумерации и полнота Математические труды, Т.26, №1,С.176-191 (год публикации - 2023)
4.
Файзрахманов М.Х.
Две теоремы о минимальных обобщенно-вычислимых нумерациях
Вестник Московского университета. Серия 1: Математика. Механика, № 3, С.28–35 (год публикации - 2023)
10.55959/MSU0579-9368-1-64-3-5
5.
Файзрахманов М.Х.
О вложении первого неконструктивного ординала в полурешетки Роджерса
Математические заметки, Т.113, №5, С.764-774 (год публикации - 2023)
10.4213/mzm13708
6.
Файзрахманов М.Х.
Вложение первого неконструктивного ординала в полурешетки Роджерса семейств арифметических множеств
Сибирский матемачтический журнал, Т.64, №4, С.830-840. (год публикации - 2023)
10.1134/S0037446623040146