Цель коллоквиума — познакомить молодых исследователей, включая студентов и аспирантов, с перспективными направлениями развития математической логики и предоставить им возможность выступить с докладами по результатам своих исследований. Параллельно с выступлениями молодых исследователей в рамках коллоквиума планируется чтение нескольких мини-курсов (по 2–3 лекции каждый), ориентированных на широкую аудиторию:

Искандер Шагитович Калимуллин (КФУ): Теорема рекурсии и критерии полноты

Мини-курс посвящен двум взаимосвязанным классическим темам теории вычислимости. Первая тема связана с теоремой Клини о неподвижной точке и её различными модификациями, в том числе с критерием Арсланова о полноте. С помощью оракульного построения будет доказана теорема Джокуша–Соара о низком базисе, из которой следует, что критерий Арсланова не~может быть обобщен на произвольные оракулы. Вторая тема связана с проблемой Поста о существовании промежуточной перечислимой тьюринговой степени и подходам к её решению. Будет дано приоритетное построение, решающее проблему Поста (теорема Мучника–Фридберга). Будет дано также альтернативное доказательство, основанное на теореме о низком базисе.

Александр Александрович Разборов (МИАН, U. Chicago): Элементы теории сложности доказательств

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

Наш мини-курс начнётся с краткого введения в теорию ограниченной (англ. bounded) арифметики и её связей с теорией сложности вычислений. После этого мы перейдём к рассмотрению пропозициональных систем доказательств, естественно возникающих при изучении доказательств $\Sigma_0^b$-формул в ограниченной арифметике. В зависимости от наличия времени, я надеюсь рассказать как о традиционных системах «в стиле Гильберта» (системы Фреге, резолюции и т.д.) так и системах, основанных на простых идеях из алгебраической и полу-алгебраической геометрии: полиномиальное исчисление, «сумма квадратов», «секущие плоскости» и др.

Алексей Леонидович Таламбуца (МИАН): Алгоритмические проблемы для матричных полугрупп

Первые примеры алгоритмически неразрешимых проблем для матриц были найдены А. А. Марковым (мл.) в 1947 году с использованием результата Поста 1946 года о проблеме соответствия (ПСП). В дальнейшем, ПСП и её модификации много раз использовались для доказательства неразрешимости других алгоритмических проблем для матриц. Так, в 1970 году Патерсон доказал, что при $n \geqslant 3$ не~существует алгоритма, проверяющего по набору $S$ целочисленных матриц размера $n \times n$, выразима ли через произведения из $S$ нулевая матрица, а в 1991 году Кларнер, Бирже и Саттерфилд доказали, что неразрешима задача проверки, существует ли нетривиальное полугрупповое соотношение между матрицами из $S$. Алгоритмическая разрешимость каждой из этих проблем для $n = 2$ до сих пор остаётся открытым вопросом. Курс будет посвящён этим задачам, а также смежным к ним.

Валентин Борисович Шехтман (МФТИ): Семантики модальных предикатных логик

В курсе излагаются некоторые результаты о полноте и неполноте модальных предикатных логик в различных семантиках. Для семантики шкал Крипке рассматриваются канонические модели и их модификации. В частности, описывается игровой метод для построения селективной фильтрации. Вводятся обобщения семантики шкал Крипке: семантика Крипке-расслоений, функциональная семантика Гиларди, симплициальная семантика Скворцова. Для симплициальной семантики обсуждается теорема корректности и доказывается теорема полноты на основе канонических моделей. Устанавливаются теоремы о неполноте более слабых семантик (шкалы Крипке, Крипке-расслоения) с помощью более сильных семантик Гиларди и Скворцова.

К участию с докладом приглашаются молодые исследователи, в том числе студенты и аспиранты, при соблюдении следующих условий:

1. возраст докладчика на момент начала коллоквиума — до 39 лет включительно;
2. очный доклад (вместе с тем онлайн-участие без доклада будет возможно);
3. тезисы доклада должны быть оформлены в соответствии с прилагаемым шаблоном, иметь объём от одной до двух страниц, включая список литературы, и содержать ясную формулировку основных результатов.

Важнейшие даты

• регистрация на участие с докладом — не позднее 09.08.2026 (продлено с 01.08.2026)
• регистрация на участие без доклада — не позднее 30.08.2026
• даты проведения: c 31.08.2026 по 04.09.2026

Программа

Доклады

Организационный комитет
Кузнецов Степан Львович
Сперанский Станислав Олегович

Финансовая поддержка
Мероприятие проводится при финансовой поддержке Минобрнауки России (грант на создание и развитие МЦМУ МИАН, соглашение № 075-15-2025-303).

Организации
Математический институт им. В.А. Стеклова Российской академии наук, г. Москва
Математический центр мирового уровня «Математический институт им. В.А. Стеклова Российской академии наук» (МЦМУ МИАН)