|
|
| КОНФЕРЕНЦИИ |
| Молодёжный коллоквиум по математической логике и её приложениям ( |
Цель коллоквиума — познакомить молодых исследователей, включая студентов и аспирантов, с перспективными направлениями развития математической логики и предоставить им возможность выступить с докладами по результатам своих исследований. Параллельно с выступлениями молодых исследователей в рамках коллоквиума планируется чтение нескольких мини-курсов (по 2–3 лекции каждый), ориентированных на широкую аудиторию:
Искандер Шагитович Калимуллин (КФУ): Теорема рекурсии и критерии полноты
Мини-курс посвящен двум взаимосвязанным классическим темам теории вычислимости. Первая тема связана с теоремой Клини о неподвижной точке и её различными модификациями, в том числе с критерием Арсланова о полноте. С помощью оракульного построения будет доказана теорема Джокуша–Соара о низком базисе, из которой следует, что критерий Арсланова не~может быть обобщен на произвольные оракулы. Вторая тема связана с проблемой Поста о существовании промежуточной перечислимой тьюринговой степени и подходам к её решению. Будет дано приоритетное построение, решающее проблему Поста (теорема Мучника–Фридберга). Будет дано также альтернативное доказательство, основанное на теореме о низком базисе.
Александр Александрович Разборов (МИАН, U. Chicago): Элементы теории сложности доказательств
Теория сложности доказательств изучает насколько простыми могут (или не могут) быть формальные доказательства истинных утверждений в различных естественных системах доказательств. Классы рассматриваемых утверждений и систем могут существенно варьироваться в зависимости от контекста, что определяет целый ряд неожиданных и важных взаимосвязей между теорией сложности доказательств и многими областями в математике и компьютерных науках.
Наш мини-курс начнётся с краткого введения в теорию ограниченной (англ. bounded) арифметики и её связей с теорией сложности вычислений. После этого мы перейдём к рассмотрению пропозициональных систем доказательств, естественно возникающих при изучении доказательств $\Sigma_0^b$-формул в ограниченной арифметике. В зависимости от наличия времени, я надеюсь рассказать как о традиционных системах «в стиле Гильберта» (системы Фреге, резолюции и т.д.) так и системах, основанных на простых идеях из алгебраической и полу-алгебраической геометрии: полиномиальное исчисление, «сумма квадратов», «секущие плоскости» и др.
Алексей Леонидович Таламбуца (МИАН): Алгоритмические проблемы для матричных полугрупп
Первые примеры алгоритмически неразрешимых проблем для матриц были найдены А. А. Марковым (мл.) в 1947 году с использованием результата Поста 1946 года о проблеме соответствия (ПСП). В дальнейшем, ПСП и её модификации много раз использовались для доказательства неразрешимости других алгоритмических проблем для матриц. Так, в 1970 году Патерсон доказал, что при $n \geqslant 3$ не~существует алгоритма, проверяющего по набору $S$ целочисленных матриц размера $n \times n$, выразима ли через произведения из $S$ нулевая матрица, а в 1991 году Кларнер, Бирже и Саттерфилд доказали, что неразрешима задача проверки, существует ли нетривиальное полугрупповое соотношение между матрицами из $S$. Алгоритмическая разрешимость каждой из этих проблем для $n = 2$ до сих пор остаётся открытым вопросом. Курс будет посвящён этим задачам, а также смежным к ним.
Валентин Борисович Шехтман (МФТИ): Семантики модальных предикатных логик
В курсе излагаются некоторые результаты о полноте и неполноте модальных предикатных логик в различных семантиках. Для семантики шкал Крипке рассматриваются канонические модели и их модификации. В частности, описывается игровой метод для построения селективной фильтрации. Вводятся обобщения семантики шкал Крипке: семантика Крипке-расслоений, функциональная семантика Гиларди, симплициальная семантика Скворцова. Для симплициальной семантики обсуждается теорема корректности и доказывается теорема полноты на основе канонических моделей. Устанавливаются теоремы о неполноте более слабых семантик (шкалы Крипке, Крипке-расслоения) с помощью более сильных семантик Гиларди и Скворцова.
К участию с докладом приглашаются молодые исследователи, в том числе студенты и аспиранты, при соблюдении следующих условий:
Важнейшие даты
Организации



























