Научно-исследовательский семинар
«Теория вычислимости»
Руководители семинара: М.М. Арсланов, И.Ш. Калимуллин.
Со-руководитель семинара: М.М. Ямалеев.
e-mail: Marat.Arslanov@kpfu.ru, ikalimul@gmail.com, marsiam2@yandex.ru
Место проведения: ауд. 501 (при необходимости заседания могут проводиться в аудиториях 510 или 610) второго учебного корпуса КФУ (ул. Кремлевская 35), параллельно заседания проходят в Zoom.
Предстоящие семинары
Прошедшие семинары
Предстоящие семинары
Научно-исследовательский семинар «Теория вычислимости» продолжит свою работу в сентябре 2021 года.

TBA
Название доклада: «TBA».
Аннотация: TBA.

Прошедшие семинары
Старостин Михаил Васильевич
(ассистент кафедры дискретной математики механико-математического факультета, Московский государственный университет, г. Москва)
Название доклада: «Критерий неявной полноты в трехзначной логике».

Аннотация: Неявная выразимость введена А. В. Кузнецовым как один из способов обобщения выразимости суперпозициями. Функция называется неявно выразимой над системой функций, если она эквивалентна некоторой системе уравнений над этой системой. Доклад посвящен задаче полноты по неявной выразимости в трехзначной логике. Был получен критерий неявной полноты в терминах максимальных неявно неполных (предполных) классов. Все 54 предполных класса описаны в терминах сохранения предикатов.

Время: 3 июня (четверг) 2021 г. в 17:30 (мск)
Место проведения: ауд. 510, II учебного корпуса КФУ (ул. Кремлевская, д. 35), а также Zoom.
Ссылка для подключения к конференции в Zoom
https://zoom.us/j/91016498326?pwd=cUY0SkxhVTJ2cndVUStTUFRvQXNJdz09
Идентификатор конференции: 910 1649 8326
Код доступа: 953752
3 июня (четверг) 2021 в 17:30 (мск)
Александрова Светлана Анатольевна
(к.ф.-м.н., научный сотрудник Института математики им. С.Л. Соболева СО РАН, г. Новосибирск)
Название доклада: «Алгоритмическая сложность некоторых аспектов сигма-определимости на структурах».

Аннотация:
В докладе будут рассматриваться вопросы алгоритмической сложности некоторых аспектов сигма-определимости. Будут представлены недавние результаты об алгоритмической сложности списочных надстроек, а также сигма-классификаций над вычислимыми структурами.

Ссылка для подключения к конференции в Zoom
https://zoom.us/j/91016498326?pwd=cUY0SkxhVTJ2cndVUStTUFRvQXNJdz09

Идентификатор конференции: 910 1649 8326
Код доступа: 953752
27 мая (четверг) 2021
17:30 (мск)

Батыршин Ильнур Ильдарович
(к.ф.-м.н., Казанский федеральный университет, г. Казань)
Название доклада: «Структура 1-степеней внутри m-степеней».
Аннотация: В докладе будет рассмотрена структура 1-степеней внутри m-степеней и изложены основные известные результаты об этой структуре. Будет рассмотрен открытый вопрос о существовании бесконечной антицепи 1-степеней в любой несократимой m-степени и изложено доказательство теоремы о существовании такой антицепи в любой несократимой Дельта-2-0 m-степени.

Ссылка для подключения к конференции в Zoom
https://zoom.us/j/91016498326?pwd=cUY0SkxhVTJ2cndVUStTUFRvQXNJdz09

Идентификатор конференции: 910 1649 8326
Код доступа: 953752
20 мая (четверг) 2021 г. 17:30 (мск)
Баженов Николай Алексеевич
(к.ф.-м.н., старший научный сотрудник лаборатории теории вычислимости и прикладной логики Института математики имени С.Л. Соболева СО РАН, г. Новосибирск)
Название доклада: «О полурешётках Роджерса для пунктуальных нумераций».
Аннотация: В докладе рассматриваются пунктуальные нумерации, т.е. равномерно примитивно рекурсивные нумерации семейств примитивно рекурсивных функций. Сводимость между пунктуальными нумерациями также индуцируется примитивно рекурсивными функциями. Приводится обзор недавних результатов об алгебраических свойствах соответствующих полурешёток Роджерса. Результаты получены совместно с М. Мустафой и С.С. Оспичевым.

Место проведения:
ауд. 510, II учебного корпуса КФУ (ул. Кремлевская, д. 35), Zoom.
Ссылка для подключения к конференции в Zoom
https://zoom.us/j/91016498326?pwd=cUY0SkxhVTJ2cndVUStTUFRvQXNJdz09
Идентификатор конференции: 910 1649 8326
Код доступа: 953752
1 апреля (четверг) 2021 г. 17:30 (мск)
Калимуллин Искандер Шагитович (д.ф.-м.н., главный научный сотрудник НОМЦ ПФО, профессор кафедры алгебры и математической логики Казанского федерального университета, г. Казань)
Название доклада: «Пунктуальная категоричность на конусе».
Аннотация: В докладе будет обсуждаться теоретико-модельный критерий пунктуальной категоричности алгебраических структур на конусе.

Место проведения: Ауд. 510 второго корпуса КФУ (ул. Кремлевская 35), а также Zoom.
Время:
25 марта (четверг) 2021 г. 17:30 (мск)
Ссылка для подключения к конференции в Zoom
https://zoom.us/j/91016498326?pwd=cUY0SkxhVTJ2cndVUStTUFRvQXNJdz09
Идентификатор конференции: 910 1649 8326
Код доступа: 953752

Ссылка для подключения к конференции в Zoom
https://zoom.us/j/91016498326?pwd=cUY0SkxhVTJ2cndVUStTUFRvQXNJdz09
Идентификатор конференции: 910 1649 8326
Код доступа: 953752
25 марта 2021 г.
в 17:30 (мск)
, ауд. 510,
II-ое высотное здание КФУ, ул. Кремлевская,
д. 35.

Файзрахманов Марат Хайдарович
(доктор физико-математических наук, доцент, старший научный сотрудник Научно-образовательного математического центра ПФО)
Место проведения: ауд. 510 второго корпуса КФУ (ул. Кремлевская 35), а также Zoom.

Название доклада:
«Теорема Фридберга в высшей теории рекурсии» (совм. с И.Ш. Калимуллиным и В.Г. Пузаренко).

Аннотация: В докладе планируется доказать, что семейство всех Sigma-подмножеств наследственно конечной надстройки модели, кодирующей m-полное Sigma-1-1 множество, обладает однозначной вычислимой нумерацией. Также будет доказано, что в том же допустимом множестве семейство всех Sigma-подмножеств обладает негативной неразрешимой минимальной вычислимой нумерацией.

Ссылка для подключения к конференции в Zoom
https://zoom.us/j/91016498326?pwd=cUY0SkxhVTJ2cndVUStTUFRvQXNJdz09
Идентификатор конференции: 910 1649 8326
Код доступа: 953752
18 марта (четверг), 17:30, ауд. 510,
II-ое высотное здание КФУ, ул. Кремлевская,
д. 35.

Ямалеев Марс Мансурович
(к.ф.-м.н., старший научный сотрудник НОМЦ Приволжского федерального округа)
Место проведения: ауд. 510 второго корпуса КФУ (ул. Кремлевская 35), а также Zoom.

Название доклада:
«Относительная перечислимость с низким в.п. оракулом».

Аннотация: В докладе планируется рассмотреть относительную перечислимость относительно низких в.п. степеней. В работе Соара и Стоба 1982 года было доказано, что для любой низкой в.п. степени существует Дельта-0-2 степень, которая перечислима относительно нее и не является в.п. В работе Арсланова, Лемппа и Шора 1996 был поставлен вопрос о том, может ли построенная Дельта-0-2 степень быть 2-в.п. С тех пор этот вопрос вызвал интерес среди большого числа специалистов по локальной теории степеней и оставался открытым. В недавней совместной работе Арсланова, Батыршина и Ямалеева был получен отрицательный ответ на этот вопрос, и в докладе будут рассмотрены основные идеи доказательства этого результата.

Ссылка для подключения к конференции в Zoom
https://zoom.us/j/91016498326?pwd=cUY0SkxhVTJ2cndVUStTUFRvQXNJdz09
Идентификатор конференции: 910 1649 8326
Код доступа: 953752
4 марта (четверг) 2021 в 17:30 (мск)
Зубков Максим Витальевич
(к.ф.-м.н., доцент кафедры алгебры и математической логики ИМиМ им. Н.И. Лобачевского КФУ)
Название доклада: «Низкие линейные порядки, не имеющие вычислимых представлений».

Аннотация: В докладе будет дан обзор достаточных условий того, что низкие линейные порядки имеют вычислимые представления, а также обзор примеров низких линейных порядков не имеющих таких представлений. Кроме того, будет построен новый пример такого порядка - так называемое eta-представление.

Ссылка для подключения к конференции в Zoom
https://zoom.us/j/91016498326?pwd=cUY0SkxhVTJ2cndVUStTUFRvQXNJdz09

Идентификатор конференции: 910 1649 8326
Код доступа: 953752
11 декабря (пятница)
2020 г. в 17:30 (мск)

Калимуллин Искандер Шагитович (д.ф.-м.н., главный научный сотрудник НОМЦ ПФО, профессор кафедры алгебры и математической логики Казанского федерального университета, г. Казань)
Название доклада: «Пунктуальная категоричность относительно вычислимых оракулов».

Аннотация: Мы изучаем пунктуальные копии алгебраических структуры (примитивно рекурсивные копии определенные на всем множестве натуральных чисел) и изоморфизмы между ними. Мы докажем, что если между двумя любыми такими копиями существует изоморфизм, являющийся вместе со своим обращением примитивно рекурсивным относительно фиксированной вычислимой функции, то алгебраическая структура либо конечно порождена, либо локально конечна

Ссылка для подключения к конференции в Zoom
https://zoom.us/j/91016498326?pwd=cUY0SkxhVTJ2cndVUStTUFRvQXNJdz09

Идентификатор конференции: 910 1649 8326
Код доступа: 953752
4 декабря (пятница)
2020 г. в 17:30 (мск)

Едыгаров Искандер Альфредович (аспирант, Казанский федеральный университет, г. Казань)
Название доклада: «О некоторых свойствах индексных множеств автоматных структур».

Аннотация: В докладе будут рассмотрены структуры, представимые с помощью автоматов и индексные множества этих структур; возможная связь работ Хомского Н., Хусаинова Б., Винокурова Н.

Ссылка для подключения к конференции в Zoom
https://zoom.us/j/91016498326?pwd=cUY0SkxhVTJ2cndVUStTUFRvQXNJdz09

Идентификатор конференции: 910 1649 8326
Код доступа: 953752
13 ноября (пятница)
2020 г. в 17:30 (мск)

Пузаренко Вадим Григорьевич
(д.ф.-м.н., ведущий научный сотрудник ИМ СО РАН, профессор Новосибирского университета, г. Новосибирск)
Место проведения: ауд. 501 второго корпуса КФУ (ул. Кремлевская 35), параллельно заседание будет в Zoom.

Название доклада: «Полуразрешимые нумерации на допустимых множествах».

Аннотация: В докладе будут рассмотрены недавние результаты о полуразрешимых нумерациях на допустимых множествах, полученные в совместной работе с Кулимуллиным И.Ш. и Файзрахмановым М.Х.

Ссылка для подключения к конференции в Zoom
https://zoom.us/j/3804779697?pwd=SnRKVU9BVlJqYjhraWwxaWNxNGxTUT09

Идентификатор конференции: 380 477 9697
Код доступа: 3127654
30 октября (пятница)
2020 г. в 17:30 (мск)

Корнеева Наталья Николаевна
(к.ф.-м.н., доцент кафедры алгебры и математической логики ИММ им. Н.И. Лобачевского КФУ)
Место проведения: ауд. 501 второго корпуса КФУ (ул. Кремлевская 35), параллельно заседание будет в Zoom.

Название доклада: «Автоматные сводимости сверхслов».

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

Ссылка для подключения к конференции в Zoom
https://zoom.us/j/3804779697?pwd=SnRKVU9BVlJqYjhraWwxaWNxNGxTUT09

Идентификатор конференции: 380 477 9697
Код доступа: 3127654
23 октября (пятница)
2020 г. в 17:30 (мск)

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

Ссылка для подключения к конференции в Zoom
https://zoom.us/j/3804779697?pwd=SnRKVU9BVlJqYjhraWwxaWNxNGxTUT09
Идентификатор конференции: 380 477 9697
Код доступа: 3127654
16 октября (пятница)
2020 г. в 17:30 (мск)

Ямалеев Марс Мансурович
(к.ф.-м.н., старший научный сотрудник НОМЦ Приволжского федерального округа)
Название доклада: «Тонкая иерархия и Дельта-0-3 множества».
Аннотация: В докладе планируется рассмотреть уровни тонкой иерархии относительно тьюринговой эквивалентности. В недавней совместной работе с Селивановым был найден первый "новый" уровень в Дельта-0-3 множествах, далее результат был обобщен на ряд других уровней. Более того, в совместной работе с Мельниковым и Селивановым был получен аналогичный результат для Дельта-0-4 множеств. В докладе будут описаны все уровни тонкой иерархии для Дельта-0-3 множеств (результат получен совместно с Селивановым) и рассмотрены возможные подходы для решения проблемы во всех уровнях арифметической иерархии.
9 октября (пятница)
2020 г. в 17:30

Зайнетдинов Дамир Хабирович
(к.ф.-м.н., ассистент кафедры алгебры и математической логики ИМиМ им. Н.И. Лобачевского КФУ)
Название доклада: «Структурные свойства предельно монотонной сводимости множеств».
Аннотация: В рамках доклада будут рассмотрены структурные свойства предельно монотонной сводимости множеств, в частности, будет показано существование максимальной пары множеств. Приводится обзор недавних результатов, а также будут поставлены открытые вопросы для дальнейших исследований.

Для участия в семинаре необходимо подключиться 17 июня после 15:50 по московскому времени к конференции Zoom по ссылке:
https://us04web.zoom.us/j/2252869439?pwd=MUhEbS95QlNkM0h2eHFzb2ErTURDZz09

Идентификатор конференции: 225 286 9439
Пароль: 7TVbdK

17 июня (среда) 2020
в 16:00
платформа Zoom

Ямалеев Марс Мансурович
(к.ф.-м.н., старший научный сотрудник НОМЦ Приволжского федерального округа)
Название доклада: «Теорема Купера о разложении и её обобщения».
Аннотация: В докладе будет подробно рассмотрено доказательство теоремы Купера о разложении собственных 2-в.п. тьюринговых степеней. На основе анализа доказательства будут рассмотрены возможные обобщения этой теоремы. Одним из таких обобщений является разложимость произвольной собственной 2-в.п. степени с избеганием верхнего конуса произвольной другой собственной 2-в.п. степени при условии, что они образуют интервал без в.п. степеней.

Для участия в семинаре необходимо подключиться 10 июня после 16:50 по московскому времени к конференции Zoom по ссылке:
https://us04web.zoom.us/j/2252869439?pwd=MUhEbS95QlNkM0h2eHFzb2ErTURDZz09

Идентификатор конференции: 225 286 9439
Пароль: 7TVbdK

10 июня (среда) 2020
в 17:00
на платформе Zoom

Михайловская Яна Алексеевна
(аспирант кафедры алгебры и математической логики Института математики и механики им. Н.И. Лобачевского)
Название доклада: «Вычислимые линейные порядки, обогащённые отношениями специального вида».
Аннотация: Работа посвящена исследованию взаимосвязей отношений S^n_L на вычислимом линейном порядке L. В работе построены примеры вычислимых линейных порядков, на которых отношения S^n_L и S^{n+1}_L имеют разные тьюринговые степени. Была исследована замкнутость наверх в классе всех вычислимо перечислимых степеней отношения S^n_L на вычислимых линейных порядках, не являющихся \eta-схожими, а также была изучена вычислимая категоричность вычислимых линейных порядков специального вида.

Для участия в семинаре необходимо подключиться 3 июня после 15:50 по московскому времени к конференции Zoom по ссылке:
https://us04web.zoom.us/j/2252869439?pwd=MUhEbS95QlNkM0h2eHFzb2ErTURDZz09

Идентификатор конференции: 225 286 9439
Пароль: 7TVbdK

3 июня (среда) 2020 г. в 16:00
на платформе Zoom

Баженов Николай Алексеевич
(к.ф.-м.н., старший научный сотрудник лаборатории теории вычислимости и прикладной логики Института математики имени С.Л. Соболева СО РАН, г. Новосибирск)
Название доклада: «О полурешётках Роджерса в аналитической иерархии».

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

Для участия в семинаре необходимо подключиться 20 мая после 15:50 по московскому времени к конференции Zoom по ссылке:
https://us04web.zoom.us/j/2252869439?pwd=MUhEbS95QlNkM0h2eHFzb2ErTURDZz09

Идентификатор конференции: 225 286 9439
Пароль: 7TVbdK


Приглашаем Всех желающих принять участие!

20 мая (среда) 2020 г. в 16:00
на платформе Zoom

Зубков Максим Витальевич
(к.ф.-м.н., доцент кафедры алгебры и математической логики ИМиМ им. Н.И. Лобачевского КФУ)
Название доклада: «О категоричности и би-вложимой категоричности разреженных линейных порядков».

Аннотация доклада: В докладе будут даны точные верхние и нижние оценки на уровни категоричности и уровни би-вложимой категоричности разреженных линейных порядков.

Для участия в семинаре необходимо подключиться 13 мая после 15:50 по московскому времени к конференции Zoom по ссылке:
https://us04web.zoom.us/j/2252869439?pwd=MUhEbS95QlNkM0h2eHFzb2ErTURDZz09

Идентификатор конференции: 225 286 9439
Пароль: 7TVbdK

Приглашаем Всех желающих принять участие!

13 мая (среда) 2020 г.
в 16:00
на платформе Zoom

Ямалеев Марс Мансурович
(к.ф.-м.н., старший научный сотрудник
НОМЦ Приволжского федерального округа)
Название доклада: «Об определимости в.п. степеней в 2-в.п. степенных структурах».

Аннотация: В докладе будут рассмотрены 2-в.п. степенные структуры, индуцированные тьюринговой, wtt- и m-сводимостями. Будут рассмотрены подходы для решения известной проблемы об определимости в.п. тьюринговых степеней в структуре 2-в.п. тьюринговых степеней. Также будут анонсированы успехи и продвижения при решении различных вариаций этой проблемы.

С презентацией доклада можно ознакомиться по ссылке.
Видеозапись семинара доступна по ссылке.

7 мая (четверг) 2020 г.
в 17:20 на платформе
Microsoft Teams

Бызов Виктор Александрович
(старший преподаватель кафедры прикладной математики и информатики Вятского государственного университета (ВятГУ, г. Киров)
Название доклада: «Исследование свойств орбит преобразования Донахью».

Приглашаем Всех желающих принять участие!
5 марта 2020 г.
17.00, ауд. 610,
II-ое высотное здание КФУ, ул.Кремлевская,
д. 35.

Пузаренко Вадим Григорьевич
(доктор физико-математических наук (доцент), ведущий научный сотрудник Института математики
им. С.Л. Соболева СО РАН, г. Новосибирск)
Название доклада: «Фридберговы представления в обобщенной вычислимости» (И.Ш. Калимуллин, В.Г. Пузаренко, М.Х. Файзрахманов)

Аннотация:
Будет приведен обзор результатов, посвящённых существованию разрешимых, позитивных и негативных представлений в аналитической иерархии и на допустимых множествах, полученных в настоящую пятилетку.

Приглашаем Всех желающих принять участие!
13 декабря (пятница), 17:20, ауд. 510,
II-ое высотное здание КФУ, ул. Кремлевская,
д. 35.

Благовещенская Екатерина Анатольевна
д.ф.-м.н., профессор, заведующая кафедрой «Высшей математики» Петербургского государственного университета путей сообщения Императора Александра I
(г. Санкт-Петербург)
Название доклада: «Теория прямых разложений абелевых групп без кручения».
Аннотация: Известно, что класс абелевых групп без кручения обладает свойством наличия неизоморфных прямых разложений. В случае групп конечного ранга натуральные числа, реализуемые как ранги неразложимых прямых слагаемых и одновременно как элементы разбиений ранга группы, определяются неоднозначно. В докладе представлена графическая теория прямых разложений, позволившая найти условия для различных разбиений одного и того же натурального числа n для их реализации в качестве параметров прямых разложений одной и той же группы ранга n. Также представлено обобщение этой теории на группы счетного ранга и описаны алгоритмы построений прямых разложений групп с заранее заданными параметрами.

Приглашаем Всех желающих принять участие!
29 ноября (пятница), 17:20, ауд. 510,
II-ое высотное здание КФУ, ул. Кремлевская,
д. 35.

Файзрахманов Марат Хайдарович
(кандидат физико-математических наук, доцент, научный сотрудник Регионального научно-образовательного математического центра, г. Казань)
Название доклада: «Полурешетки обобщенно вычислимых нумераций и спектры степеней счетных семейств»

Приглашаем Всех желающих принять участие!
22 ноября (пятница), 17:20, ауд. 510,
II-ое высотное здание КФУ, ул. Кремлевская,
д. 35.

В математическом центре состоялся круглый стол, посвященный актуальным вопросам
математической логики
8 ноября в Региональном научно-образовательном математическом центре состоялся круглый стол, посвященный актуальным вопросам теории вычислимости и теории моделей. В круглом столе приняли участие приглашенные гости Мельников Александр Геннадьевич и Пузаренко Вадим Григорьевич, которые в эти дни находятся с визитом в матцентре. В ходе круглого стола участниками был обозначен круг вопросов, на решении которых предстоит сосредоточиться в ходе совместных научных исследований.
8 ноября 2018 года