Алгебра в Казанском университете (продолжение)

Ю.А. Альпин и С.Н. Ильин провели исследования по линейной алгебре и теории матриц. Ими доказано существование рациональных процедур для ряда важных задач линейной алгебры, найдены новые области локализации собственных значений матриц и корней полиномов, установлен критерий унитарной эквивалентности матричных семейств. В ходе исследования матричных полуколец полностью описаны обратимые матрицы над положительно упорядоченными полукольцами, и найден критерий регулярности полного матричного полукольца. Получены точные оценки числовых характеристик знаковых портретов вещественных матриц, дана формула для наименьшего из рангов бесконечных продолжений теплицевой матрицы.

Научная деятельность коллектива под руководством  М.М. Арсланова связана с исследованиями в области теории вычислимости, науки, развивающейся на стыке алгебры и математической логики. В своей докторской диссертации М.М. Арсланов исследовал тьюринговые степени, содержащие функции без т.н. ''неподвижных точек'', с их помощью сформулировав критерии полноты множеств в арифметической иерархии. Эти его работы  положили начало целому направлению исследований в этой области с участием многих математиков, работающих в теории вычислимости. Теперь эти критерии хорошо известны в литературе как критерии полноты Арсланова. Ему также принадлежат первые результаты в разработке структурной теории тьюринговых степеней неразрешимости, принадлежащих разностной иерархии множеств, хорошо известной как иерархия Ершова, в частности доказательство элементарной неэквивалентности полурешеток степеней перечислимых множеств и степеней, содержащих первого за этим уровнем уровня иерахии. Впоследствии им совместно со своим учеником  И.Ш. Калимуллиным и профессором С. Лемппом (США) был установлен такой результат и для следующей пары уровней иерархии, что решает проблему, долгое время остававшей открытой. В настоящее время И.Ш. Калимуллин исследует алгоритмические свойства алгебраических структур, а также связанных с ними алгоритмических сводимостей. Среди его основные результаты  решение проблемы элементарной эквивалентности элементарных полурешеток n-в.п. степеней по перечислимости при различных n, доказательство определимости операции скачка в степенях по перечислимости, классификация различных сводимостей массовых проблем представимости алгебраических структур (равномерные и неравномерны варианты, всюду определенные и частичные массовые проблемы). Совместно со своим учеником М.Х. Файзрахмановым им построена иерархия спектров семейств на различных уровнях комулятивной иерархии фон Неймана, ими также найдены алгебраические структуры, спектры которых состоят из дополнений классов степеней, низких на фиксированном предельном уровне гиперарифметической иерархии.

М.Х.  Файзрахманов в своей кандидатской диссертации  исследовал уровни иерархии Ершова, содержащие тьюринговые скачки множеств. Ему удалось дать полное описание уровней иерархии, содержащие тьюринговые скачки, не принадлежащие меньшим уровням. Он также изучает так называемые обобщенно вычислимые нумерации– нумерации семейств, вычислимых с помощью оракула. В этом направлении им были получены критерии существования универсальных обобщенно вычислимых нумераций конечных семейств.  

В 2000-х годах на кафедре алгебры и математической логике начинает активно развиваться направление вычислимых линейных порядков. Первые результаты этого направления были получены в кандидатской диссертации А.Н. Фролова, еще одного ученика М.М. Арсланова. В своих первых работах А.Н. Фролов разрабатывал технику построения вычислимых представлений для линейных порядков, в алгоритмическом смысле близких к вычислимым и называемых низкими. Им (в некоторых случаях в совместных работах) был получен целый ряд результатов, позволяющих получить описание самого широкого известного на данный момент класса низких линейных порядков, имеющих вычислимые представления (этот вопрос был поставлен Р. Доуни в 1998 году).

А.Н. Фроловым также изучается вопрос описания спектров представлений линейных порядков. Первые результаты в этом направлении им были получены еще кандидатской диссертации. Впоследствии им был получен  ряд примеров ограниченных спектров линейных порядков, построены примеры спектров линейных порядков, содержащих в точности все n-высокие степени, а также все степени, не являющиеся n-низкими для n>1.

Все эти результаты легли в основу его докторской диссертации, защищенной в 2014 году.

Ученик Фролова М.В. Зубков исследовал связь между вычислимыми линейными порядками, предельно монотонными функциями и эта-представлениями. В кандидатской диссертации он дал описание сильно эта-представимых тьюринговых степеней, в терминах псевдовозрастающих на  множестве рациональных числе предельно монотонных функций. Им также изучались уровни разностной иерархии Σ-0-2-множеств, содержащие сильно эта-представимые множеcтва. 

В 2015 году под руководством А.Н. Фролова защитил  кандидатскую диссертацию Р.И. Бикмухаметов. В ней  он доказал алгоритмическую независимость ряда отношений на вычислимых линейных порядках. В частности, им были рассмотрены такие естественные отношения, как отношение соседства, блока, предельности слева и справа, плотности. Также эти отношения рассматривались на начальных сегментах линейных порядках. Одним из основных результатов диссертационной работы Р.И. Бикмухаметова является доказательство того, что Σ-2-0-начальные сегменты вычислимых линейных порядков исчерпывают все Σ-0-2-степени и все вычислимые порядки без наибольшего элемента.

Н.Н. Корнеева изучает сложности бесконечных последовательностей над конечным алфавитом относительно различных типов автоматной сводимости, таких, как конечно-автоматная и асинхронно автоматная сводимости,  и возникающие при этом  степени неразрешимости. В кандидатской диссертации она  исследовала структурные свойства множества степеней асинхронно автоматных преобразований. В частности, было установлено существование континуума атомов, вложимость любого конечного линейно-упорядоченного множества как начального сегмента. Также был получен отрицательный ответ  на вопрос дополняемости  вверх и положительный ответ на вопрос дополняемости вниз как в множестве степеней асинхронно автоматных преобразований,  так и в множестве степеней  конечно-автоматных преобразований. В настоящее время Н.Н. Корнеева изучает подструктуры указанных степенных структур. В частности, структурные свойства  степеней конечно-автоматных и асинхронно автоматных преобразований последовательностей с разрешимой монадической теорией и последовательностей со свойством префиксной разрешимости.