На главную

Научно-исследовательский семинар
по математической логике
руководители:
академик РАН
чл.-корр. РАН
академик РАН
Сергей Иванович Адян
Лев Дмитриевич Беклемишев
Алексей Львович Семёнов

проходит по средам 18:30–21:00 в ауд. 16-04 ГЗ МГУ

YouTube-канал семинара


  1. 2017.04.24: Ломоносовские чтения 2019
    Видеозапись: YouTube
    Доклады:
    1. Об одном информационном неравенстве и его комбинаторном применении.
      Докладчик: проф. Н. К. Верещагин.
    2. Критерии аксиоматизируемости в модальной логике.
      Докладчик: с.н.с. Е. Е. Золин.
    3. Программа Гильберта, теорема о полноте, теорема о неполноте для математика.
      Докладчик: акад. РАН А. Л. Семёнов.
    4. О фрагментах модальных логик предикатов с одной переменной.
      Докладчик: проф. В. Б. Шехтман.
  2. 2019.04.11: Логика Гейтинга — Оккама и гиперинтенсиональность
    Докладчик: Одинцов Сергей Павлович (Новосибирский государственный университет)
    Внимание: доклад состоится в четверг в 18:30 в ауд. 13-04 на совместном заседании НИС и «Объединенного семинара» .
    Аннотация. Поводом для доклада послужило выступление Ханнеса Ляйтгеба на LP18, где он ввел логику HYPE для рассуждений о гиперинтенсиональных контекстах. Оказалось, что эта логика близка к логике Гейтинга — Оккама, введенной в процессе исследования логических программ с отрицанием, т.е. с совершенно иной мотивацией. К тому же обе логики имеют примечательную характеризацию в рамках теории отрицания Вакарелова. Наконец, после представления упрощенной семантики Крипке и алгебраической семантики для HYPE станет ясно, что это типичный пример интенсиональной логики. В значительной степени это будет исторический доклад, включающий краткие обзоры теории отрицания Вакарелова и сведений о дедуктивных базах для немонотонных логик.
  3. 2019.04.10: Конференция студентов, аспирантов и молодых учёных «Ломоносов 2019»
    Видеозапись: YouTube
    Доклады:
    1. Ищенко Дарья Дмитриевна
      (МГУ, 3-й курс, научый руководитель: с.н.с. Е. Е. Золин)
      Бисимуляции для градуированного модального языка)
    2. Коновалов Александр Юрьевич
      (МГУ, к.ф.-м.н., научный руководитель: доц. В. Е. Плиско)
      Понятие общерекурсивной реализуемости
    3. Никитин Игорь Александрович
      (МГУ, 6-й курс, научный руководитель: проф. Н. К. Верещагин)
      Сравнение коммуникационных протоколов (для предикатов)
    4. Оноприенко Анастасия Александровна
      (МГУ, асп. 1 года, научный руководитель: чл.-корр. РАН Л. Д. Беклемишев)
      Пропозициональная логика задач и высказываний
    5. Пшеницын Тихон Григорьевич
      (МГУ, 2 курс)
      Групповые грамматики и контекстно-свободные грамматики
    6. Царегородцев Кирилл Денисович
      (МГУ, асп. 2 года каф. высшей алгебры, научный руководитель: доц. А. Е. Панкратьев)
      О взаимно-однозначном соответствии между правильными семействами булевых функций и реберными ориентациями с единственным стоком на булевых кубах

  4. ВЕСНА 2019
  5. 2019.03.20: Апериодические траектории для внешних биллиардов и компьютер в доказательствах
    Докладчик: Рухович Филипп Дмитриевич (МФТИ, Москва)
    Видеозапись доклада: YouTube
    Аннотация. Рассмотрим многоугольник G. Из точки A на плоскости проведем (правую) касательную к G. Она пройдет через вершину M многоугольника, отразим точку A относительно этой вершины. Полученное преобразование точек называется преобразованием внешнего биллиарда. При последовательном применении преобразования траектория точки может оказаться периодической, апериодической, а также вырожденной (попадет на сторону многоугольника).

    Ситуация проста для треугольника, четырех- и шести- угольника (все не вырожденные траектории периодичны), исследована для пяти- и десяти- угольника. Автор получил результаты для восьми- и двенадцати- угольника.

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

  6. 2019.03.06: Unsound rules and proof macros
    Докладчик: Matthias Baaz (Vienna University of Technology)
    Видеозапись доклада: YouTube
    Abstract. We give examples of analytic sequent calculi LK+ and LK++ that extend Gentzen's sequent calculus LK by unsound quantifier rules in such a way that

    (i) derivations lead only to true sequents;
    (ii) cut free proofs may be non-elementary shorter than cut free LK proofs.

    This research is based on properties of Hilbert's epsilon calculus and is part of efforts to complement Hilber's stepwise concept of proof by useful global concepts. We use these ideas to provide analytic calculi for Henkin quantifiers and demonstrate soundness, (cut free) completeness and cut elimination. Furthermore, we show that, in the case of quantifier macros such as Henkin quantifiers for a partial semantics, global calculi are the only option to preserve analyticity.

  7. 2019.02.20: Исследование вычислительной сложности задач о независимом множестве и о вершинной k-раскраске в некоторых классах графов
    Докладчик: Сироткин Дмитрий Валерьевич (НИУ ВШЭ, Нижний Новгород)
    Видеозапись доклада: YouTube
    Аннотация. Хорошо известно, что задачи о независимом множестве (НМ) и вершинной раскраске в три цвета (Раскраска) NP-полны в классе всех графов. В докладе рассматриваются вопросы о том, что произойдет, если тем или иным способом сузить класс графов: для каких классов графов задачи НМ и Раскраска остаются NP-полными, а для каких становятся разрешимыми за полиномиальное время. Для этого определяются некоторые локальные преобразования на графах, сохраняющие наличие независимого множества или 3-раскраски. При помощи данных преобразований, а также новых приемов алгоритмической теории графов, получены ответы на эти вопросы для некоторых подклассов класса планарных графов, определяемых запрещенными порожденными структурами малого размера.
  8. ОСЕНЬ 2018
  9. 2018.12.19: Заседание, посвященное памяти проф. В. А. Успенского
    Видеозапись (3:44:23): YouTube (смотреть с 59:42, это связано с переносом на 1 час начала заседания)
    Видеозапись (2:49:27): YouTube (видео выступлений; но ближе к концу рассинхронизация звука и видео)
    Доступны также фотографии (за них благодарим Ксению Семёнову)
    С докладами выступили:
    • к.ф.-м.н. Александр Шень и
    • проф. Владимир Александрович Плунгян
    с обзором, соответственно, математического и нематематического научного наследия заведующего (с 1993 по 2018 гг.) кафедрой математической логики и теории алгоритмов профессора В. А. Успенского (27.11.1930–27.06.2018).

    Своими воспоминаниями о В. А. Успенском также поделились (ссылки на соответствующий момент видеозаписи):
    • акад. Сергей Иванович Адян,
    • акад. Алексей Львович Семёнов,
    • проф. Владимир Михайлович Тихомиров,
    • проф. Елена Наумовна Зарецкая,
    • проф. Екатерина Владимировна Рахилина.

  10. 2018.12.05: Алгоритмическая выразительность неклассических предикатных логик, задаваемых классами шкал Крипке, не определимыми в логике первого порядка
    Докладчик: Рыбаков Михаил Николаевич (Тверской государственный университет)
    Видеозапись доклада: YouTube
    Аннотация. Известно, что для всякого класса шкал Крипке, определимого в языке первого порядка, соответствующий ему класс предикатных модальных логик рекурсивно аксиоматизируем. То же верно для предикатных суперинтуиционистских логик. В то же время известно, что добавление существенно второпорядковых условий (в различных их формах) к семантике во многих случаях приводит к потере рекурсивной перечислимости получающейся логики.

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

    (а) бесконечные классы предикатных модальных (и суперинтуиционистских) неперечислимых логик и неполных по Крипке исчислений;

    (б) примеры полных по Крипке рекурсивно аксиоматизируемых предикатных модальных логик, которые не полны относительно первопорядково определимых классов шкал (и/или классов порождённых корневых шкал).

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

  11. 2018.11.21: Секвенциальные исчисления с нефундированными выводами для логик Гжегорчика
    Докладчик: Саватеев Юрий Вячеславович
    Видеозапись доклада: YouTube
    Аннотация. В докладе будут предложены секвенциальные исчисления с нефундированными выводами для логики Гжегорчика Grz и слабой логики Гжегорчика wGrz. Для этих исчислений строится оператор удаления сечения как неподвижная точка нерастягивающего отображения в ультраметрическом пространстве.
  12. 2018.11.07: Сложность конечных автоматов в терминах количества состояний и ее поведение при различных операциях
    Докладчик: Раскин Михаил Александрович
    Видеозапись доклада: YouTube
    Аннотация. Детерминированные и недетерминированные конечные автоматы распознают одно и то же семейство языков. Хорошо известно, что детерминизация может приводить к экспоненциальному росту числа состояний. (Естественно напрашиваются аналогии с проблемой перебора.) Можно выделить некоторые промежуточные классы конечных автоматов, например, однозначные конечные автоматы, а также различные другие модификации конечных автоматов. Операции над языками при разных представлениях будут по-разному влиять на количество состояний.

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

  13. 2018.10.24: Computability aspects in multidimensional symbolic dynamics (на английском языке)
    (Алгоритмические свойства многомерных замощений)
    Докладчик: Pierre Guillon (Пьер Гийон) (CNRS & Centre interdisciplinaire franco-russe Poncelet)
    Видеозапись доклада: YouTube
    Abstract. A 1D subshift of finite type (SFT) is a set of biinfinite words over a given finite alphabet, defined by prohibiting a finite set of finite patterns. 1D SFT can be studied thanks to linear algebra, graph theory, automata theory. The 2D version of this object, however, corresponds to tilings by Wang tiles, and relies strongly on computability theory.

    We will survey some uncomputability and characterization results in this setting: domino problem, language, entropies, traces, periods, quasiperiods, Kolmogorov complexity, Turing degrees. If time permits, we will conclude with open questions, especially in the larger setting of Cayley graphs.

  14. 2018.10.10: Экспандеры и связь коммуникационной и вопросной сложности
    Докладчики: Козачинский Александр Николаевич и Верещагин Николай Константинович
    Видеозапись доклада: YouTube
    Аннотация. Доклад посвящён техникам получения нижних оценок для трёх видов сложности вычислений: схемной (рассматривавшейся начиная с 1950-х годов), коммуникационной и вопросной. Будет описана техника сведения одних оценок к другим и приведены результаты автора, относящиеся к ограниченности этой техники.
  15. Избранные доклады прошлых лет
  16. 2018.04.04: Замощения Аммана
    Докладчик: Верещагин Николай Константинович
    Аннотация. Доклад по статье Верещагина, Дюрана и Шеня: On the structure of Ammann A2 tilings.
  17. 2017.11.22: Конструктивные семантики логических языков, основанные на обобщённой вычислимости
    Докладчик: Коновалов Александр Юрьевич
    Аннотация. Краткое изложение результатов представляемой к защите диссертации.
    Научный руководитель: доц. В.Е.Плиско.
  18. 2017.11.15: Interpolation, Amalgamation and Combination (на английском языке)
    Докладчик: Silvio Ghilardi (Сильвио Гиларди)
  19. 2017.05.31: О некоторых вопросах алгоритмической статистики
    Докладчик: Милованов Алексей Сергеевич
    Аннотация. Краткое изложение результатов представляемой к защите диссертации.
    Научный руководитель: проф. Н.К.Верещагин.
  20. 2017.04.19: Ломоносовские чтения 2017
    Доклады:
    1. Нестохастические объекты в алгоритмической статистике.
      Докладчики: Верещагин Николай Константинович (проф.), Милованов Алексей Сергеевич (асп.).
    2. О спектрах консервативности для арифметических теорий.
      Докладчик: Беклемишев Лев Дмитриевич (проф., чл.-корр. РАН).
    3. О моделировании знания в социальных сетях.
      Докладчик: Крупский Владимир Николаевич (доц.).
    4. Кратчайшая перестройка данных графов, одного в другой:
      линейный алгоритм или сведение к целочисленному линейному программированию
      .
      Докладчик: Любецкий Василий Александрович (проф.).
    5. О конструктивной теории перечислимых видов.
      Докладчик: Плиско Валерий Егорович (доц.).
    6. О понятии исчисления.
      Докладчики: Семёнов Алексей Львович (проф., академик РАН), Успенский Владимир Андреевич (проф.).
    7. О пространствах выразимости.
      Докладчик: Семёнов Алексей Львович (проф., академик РАН).
    8. Структура пространств выразимости для следования на целых числах.
      Докладчик: Семёнов Алексей Львович (проф., академик РАН), Сопрунов Сергей Федорович (с.н.с. ВЦ РАН).
    9. О полноте некоторых предикатных модальных логик.
      Докладчик: Шехтман Валентин Борисович (проф.).
  21. 2017.04.12: Конференция студентов, аспирантов и молодых учёных «Ломоносов 2017»
    Доклады:
    1. Власов Илья Игоревич
      (Казанский (Приволжский) государственный университет)
      Умеренно низкие и супернизкие множества (аннотация)
    2. Запрягаев Александр Александрович
      (МГУ, 5-й курс, научный руководитель: чл.-корр. РАН Л. Д. Беклемишев)
      Интерпретации арифметики Пресбургера в себя
  22. 2017.02.15: Об элиминации итеративных операторов в некоторых теориях первого порядка
    Докладчик: Золотов Александр Сергеевич (Казанский федеральный университет)
    Аннотация. Доклад посвящен исследованию алгоритмических свойств разрешимых арифметических теорий первого порядка, обогащенных итеративными операторами: оператором транзитивного замыкания и оператором фиксированной точки. В некоторых случаях удается эффективно элиминировать данные операторы, что позволяет сделать выводы о разрешимости обогащений. В других случаях обогащение оказывается неразрешимым. Также для фрагмента теории целых чисел с функцией следования и одноместным оператором наименьшей фиксированной точки, применяемым только к экзистенциальным формулам, установлена полнота проблемы разрешимости в классе гиперэкспоненциальной временной сложности.
  23. 2016.11.02: Сравнение игровыми методами понятий префиксной и обычной колмогоровской сложности
    Докладчик: Андреев Михаил Александрович
    Аннотация. Краткое изложение результатов представляемой к защите диссертации.
    Научный руководитель: проф. Н.К.Верещагин.
  24. 2016.04.27: Ломоносовские чтения 2016
    Доклады:
    1. Бисимуляционные игры и неклассические логики
      Докладчик: Шехтман Валентин Борисович (профессор, д.ф.-м.н.)
    2. Модальные логики операций на шкалах Крипке
      Докладчик: Золин Евгений Евгеньевич (с.н.с., к.ф.-м.н.)
  25. 2016.04.13: Конференция студентов, аспирантов и молодых учёных «Ломоносов 2016»
    Доклады:
    1. Вахрушева Полина Викторовна
      (МГУ, аспирант, научный руководитель: проф. В. Б. Шехтман)
      Свойства некоторых временных гибридных логик
    2. Запрягаев Александр Александрович
      (МГУ, 4-й курс, научный руководитель: чл.-корр. РАН Л. Д. Беклемишев)
      Интерпретации арифметики Пресбургера в себя
    3. Маслов Николай Александрович
      (научный руководитель: проф. В. Б. Шехтман)
      Бисимуляционная игра Эренфойхта для предикатных моделей Крипке с постоянной областью
    4. Милованов Алексей Сергеевич
      (МГУ, аспирант, научный руководитель: проф. Н. К. Верещагин)
      Некоторые свойства антистохастических слов
  26. 2015.04.15: Конференция студентов, аспирантов и молодых учёных «Ломоносов 2015»
    Доклады:
    1. Осипов Илья Игоревич
      Теоремы о характеризации для бимодальной логики
  27. 2014.05.21: Некоторые результаты об автоматах на сверхсловах, полученные с помощью прямого и полупрямого произведения
    Докладчик: Раскин Михаил Александрович
  28. 2014.04.16: Ломоносовские чтения 2014
    Доклады:
    1. Коммуникационная сложность приближённого нахождения колмогоровской сложности
      Докладчик: Верещагин Николай Константинович (профессор, д.ф.-м.н.)
    2. Локальный аналог теоремы Гольдблатта-Томасона в модальной логике
      Докладчик: Золин Евгений Евгеньевич (с.н.с., к.ф.-м.н.)
  29. 2013.09.18: Отношение совместимости в двух вариантах исчисления Ламбека
    Докладчик: Сорокин Алексей Андреевич
    Аннотация. Краткое изложение результатов представляемой к защите диссертации.
    Научный руководитель: проф. М.Р.Пентус.
  30. 2013.05.22: Применения графов в теории колмогоровской сложности
    Докладчик: Мусатов Даниил Владимирович
    Аннотация. Краткое изложение результатов представляемой к защите диссертации.
    Научный руководитель: проф. Н.К.Верещагин.
  31. 2013.04.24: Ломоносовские чтения 2013
    Доклады:
    1. Вычисление небольшого списка, содержащего короткое описание данного объекта
      Докладчик: Верещагин Николай Константинович (профессор, д.ф.-м.н.)
    2. Клетчатые произведения модальных логик
      Докладчики: Шехтман Валентин Борисович (профессор, д.ф.-м.н.), Шапировский Илья Борисович (с.н.с. ИППИ РАН, к.ф.-м.н.)
  32. 2013.04.10: Конференция студентов, аспирантов и молодых учёных «Ломоносов 2013»
    Доклады:
    1. Андреев Михаил Александрович
      (МГУ, 5-й курс, научные руководители: проф. Н. К. Верещагин, А. Шень)
      Различные варианты α-нулевых множеств и их сравнение
    2. Колесниченко Игнатий Игоревич
      (МГУ, аспирант, научные руководители: асс. М. А. Бабенко, проф. Н. К. Верещагин)
      О минимальных окончаниях подслов
  33. 2012.12.05: Конструкция Хрушовского и гипотезы Шануэля и Андрэ
    Докладчик: Зильбер Борис Иосифович
    Аннотация. Конструкция Хрушовского является (eдинственным) источником контрпримеров к гипотезе докладчика о том, что все теории, категоричные в несчётных мощностях, сводятся к алгебраической геометрии. Тем не менее, более глубокий анализ показывает, что эти контрпримеры не очень далеки от алгебраической геометрии и связаны с классическими трансцендентными функциями. При этом один из ключевых элементов конструкции Хрушовского соответствует условию, сформулированному в частном случае в известной гипотезе Шануэля, и её глубокому обобщению — гипотезе Ива Андрэ.
  34. 2012.10.31:
    1) Разрешимость теории иерархий согласованных со сложением функций
    Докладчик: Снятков Алексей Сергеевич (Тверской государственный университет)
    Аннотация. Краткое изложение результатов представляемой к защите диссертации.
    Научный руководитель: д.ф.-м.н., доц. С.М.Дудаков.

    2) Эффективные алгоритмы для некоторых задач обработки слов
    Докладчик: Стариковская Татьяна Андреевна
    Аннотация. Краткое изложение результатов представляемой к защите диссертации.
    Научный руководитель: к.ф.-м.н. М.А.Бабенко.
  35. 2012.04.11: Конференция студентов, аспирантов и молодых учёных «Ломоносов 2012»
    Доклады:
    1. Андреев Михаил Александрович (МГУ, 4-й курс)
      Эффективная хаусдорфова размерность и случайность по классам мер
    2. Пахомов Федор Николаевич (МГУ, 5-й курс)
      PSPACE-полнота замкнутого фрагмента полимодальной логики доказуемости
    3. Савин Арсений Анатольевич (МГУ, 4-й курс)
      Тотально вычислимая колмогоровская сложность
  36. 2012.03.28:
    1) О пропозициональных исчислениях, представляющих понятие доказуемости
    Докладчик: Дашков Евгений Владимирович
    Аннотация. Краткое изложение результатов представляемой к защите диссертации.
    Научный руководитель: проф. Л.Д.Беклемишев.
    2) Категориальные грамматики, основанные на вариантах исчисления Ламбека
    Докладчик: Кузнецов Степан Львович
    Аннотация. Краткое изложение результатов представляемой к защите диссертации.
    Научный руководитель: проф. М.Р.Пентус.
  37. 2011.12.14: Добавление случайных аксиом и теорема Гёделя
    Докладчик: Шень Александр
    Аннотация. Теорема Гёделя в форме Чейтина показывает, что утверждения вида «колмогоровская сложность x больше c», где x — конкретное слово, а c — конкретное число, недоказуемы для всех достаточно больших с. С другой стороны, мы практически уверены, что бросание честной монеты позволяет получить пары (x, c), для которых такие утверждения истинны (считая противное невероятным). Что будет, если добавлять такие утверждения в качестве аксиом? Можно ли таким образом преодолеть ограничения, накладываемые теоремой Гёделя? В докладе этот вопрос будет уточнён и показано (в некотором точном смысле), что надежды получить новые интересные утверждения таким способом нет, а вот сокращение доказательств тут возможно.
  38. 2011.11.16: Ломоносовские чтения 2011
    Доклады:
    1. Проблема глобальной выполнимости в полимодальных градуированных логиках
      Докладчик: Золин Евгений Евгеньевич (с.н.с., к.ф.-м.н.)
    2. Квадраты модальных логик с дополнительными связками
      Докладчик: Шехтман Валентин Борисович (профессор, д.ф.-м.н.)
    3. Интерполяционные свойства логик доказуемости и нормализация термов рефлексивной комбинаторной логики
      Докладчик: Шамканов Данияр Салкарбекович (аспирант)
      Аннотация. Краткое изложение результатов представляемой к защите диссертации.
      Научные руководители: проф. Л.Д.Беклемишев, доц. В.Н.Крупский.
  39. 2010.09.22: О некоторых суперинтуиционистских логиках, связанных с логикой задач Колмогорова – Медведева
    Докладчик: Шатров Тимофей Анатольевич
    Научный руководитель: проф. В.Б.Шехтман

Собрал информацию: уч. секретарь кафедры Е.Е.Золин
HTML 4.01   CSS 3