КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ

---

Номер 22-21-20024

НазваниеИнформационная выразительность степеней неразрешимости

РуководительАрсланов Марат Мирзаевич, Доктор физико-математических наук

Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Казанский (Приволжский) федеральный университет", Республика Татарстан (Татарстан)

Период выполнения при поддержке РНФ

2022 г. - 2023 г.

Конкурс№65 - Конкурс 2022 года «Проведение фундаментальных научных исследований и поисковых научных исследований малыми отдельными научными группами» (региональный конкурс).

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах, 01-101 - Математическая логика и основания математики

Ключевые словаCEA-оператор, тьюринговая сводимость, табличная сводимость, степень неразрешимости, гипериммунная степень, предполная нумерация, вычислимые функции, вычислимо перечислимое множество, низкое множество, иерархия Ершова, колмогоровская сложность, функция без неподвижных точек

Код ГРНТИ27.03.45

СтатусУспешно завершен

---

 

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

---

Аннотация
Для разъяснения трудностей трансляций между реализациями эквивалентных алгоритмов на разных устройствах в проекте используется подход, основанный на степенной (Т-, wtt-, tt- и другие сводимости) классификации классов множеств. Этот подход будет использован для определения понятия сложности класса функций с помощью полурешетки вычислимых нумераций этого класса. Такое понятие сложности класса функций во многих вопросах оказывается более полезным, чем известные понятия сложности отдельно взятых функций. Полурешетка вычислимых нумераций является весьма выразительным алгебраическим объектом, с помощью которого можно различать разнообразные внутренние структурные свойства классов вычислимо перечислимых множеств и частично вычислимых функций. Именно использование подходящих универсальных нумераций позволяет найти наиболее значимые теоремы о существовании, в частности теоремы о неподвижных точках вычислимых функций с той или иной степенью равномерности, которые по их значимости и месту могут быть сравнимы с основными теоремами существования в теории дифференциальных уравнений. В связи с этим одним из фундаментальных направлений проекта является исследование тьюринговых степеней классов множеств с целью более тонкой их классификации на основе информации, закодированной в этих степенях. Хорошо известно, что основным средством для сравнения сложности множеств являются алгоритмические сводимости. Сложность множеств также может быть оценена с помощью ряда иерархий множеств (CEA-иерархии, иерархии Ершова, арифметической иерархии, иерархии высоких и низких множеств и др.). Проект предполагает исследование алгоритмической сложности множеств при помощи тьюринговой сводимости и некоторых других сводимостей, которые определяются наложением разного рода ограничений на вопросы к оракулу в тьюринговой сводимости, а также при помощи сравнений уровней множеств в различных иерархиях. Известны глубокие связи между алгоритмическими сложностями множеств в уровнях этих иерархий и колмогоровской сложностью вычислительных алгоритмов, задаваемых на этих множествах. Принятые в проекте методы исследования могут позволить получить новые серьезные результаты в этом направлении. Таким образом, планируемые результаты с одной стороны логично продолжат разработку классических направлений теории вычислимости, а с другой стороны помогут по новому взглянуть на уровень информации, закодированный в множествах, близких к разрешимым.

Ожидаемые результаты
Использование подходящих универсальных нумераций позволяет найти наиболее значимые теоремы о существовании неподвижных точек вычислимых функций с той или иной степенью равномерности. Среди таких нумераций наиболее широко изученными являются предполные универсальные нумерации. Предполные нумерации определяются выполнением в них теоремы рекурсии с параметрами для частично вычислимых функций. В проекте развивается новая научная тематика, которая заключается в существенном расширении класса предполных нумеараций до нумераций, в которых справедлива теорема рекурсии с параметрами или даже теорема о неподвижной точке в ее классической подстановке. В описанной новой тематике ожидаются следующие результаты: (1) описание класса универсальных нумераций, в которых справедлива теорема о неподвижной точке; (2) описание класса универсальных нумераций, в которых справедлива теорема рекурсии с параметрами; (3) получение условий, гарантирующих предполноту универсальных нумераций, вычислимых относительно заданных оракулов. При исследований свойств CEA-иерархии и их связи с другими иерархиями предполагается установить более тонкую связь между уровнями скачков низких в.п. множеств и перечислимостью 2-в.п. степеней относительно таких множеств. В этом направлении ожидаются следующие результаты: (1) для каждой в.п. тьюринговой степени получить полное описание всех принадлежащих этой степени уровней иерархии Ершова; (2) полное описание тьюринговых степеней, которые являются CEA степенями относительно заданного низкого в.п. множества, возможно в терминах скачков этого множества. Последний результат вместе с другими недавними результатами участников проекта, позволит получить полное решение известной проблемы, возникшей из работы Соара Р. и Стоба М. [Relative computable enumerability. Proceedings of the Herbrand symposium, Logic Colloquium’81 (In J. Stern, editor), 1982]. В ряде работ зарубежных математиков была установлена зависимость между способностью множества вычислять, используя в вычислениях по Тьюрингу в качестве оракула диагонально невычислимые функции (DNC функции) и колмогоровской сложностью его начальных сегментов. Ими такая работа проводилась для wtt-, T-сводимостей и уровня Sigma-1 арифметической иерархии Мы надеемся, что разработанные авторами проекта методы исследования позволят получить полное описание колмогоровских сложностей начальных сегментов m-, tt-сводимостей и для множеств более высоких уровней иерархии. В недавних работах Тервейна С. [Generalizations of the Recursion Theorem, Journal of Symbolic Logic, 2018], Барендрегта Х. и Тервейна С. [Fixed point theorems for precomplete numberings, Annals of Pure and Applied Logic, 2019] и Арсланова М.М. [Fixed-point Selection Functions, Lobachevskii Journal of Mathematics, 2021] введено понятие функции выбора неподвижных точек, сводящихся по Тьюрингу к данному множеству функций, изучены ее поведение и зависимость от расположения множества в выше описанных иерархиях и колмогоровской сложностью его начальных сегментов. Эти вопросы в рамках проекта будут исследованы для сильных (m-, tt-) сводимостей. Ожидаемые результаты могут помочь лучше понять зависимость между сложностным расположением множества в выше упомянутых иерархиях и колмогоровской сложностью распознавания принадлежности чисел в это множество.

---

 

ОТЧЁТНЫЕ МАТЕРИАЛЫ

---