#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

10 March 2025, 16.30 CET = 18.30 Moscow time

Existence of key-agreement, a Kolmogorov complexity characterization.

Bruno Bauwens

In a key-agreement protocol, Alice and Bob have a natural number n, exchange messages, and obtain with high probability the same string x. A time bounded adversery listen to the messages and guesses the key x. A common conjecture in cryptography is that there exist protocols in which the adversary fails to guess the key with probability 1 - 1/n^c for all c. In 2023, Ball, Liu, Mazor and Pass gave an equivalent formulation of this conjecture using Kolmogorov complexity ("Kolmogorov goes to cryptomania"). We present a simple proof this equivalence.

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (https://www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (https://homepage.mi-ras.ru/~sk/) и С.О. Сперанского (https://homepage.mi-ras.ru/~speranski/)

Время: 11 марта 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

Н.В. Лукашов (НИУ ВШЭ)

Сюрреальные числа Конвея

В своём докладе я совместной трансфинитной индукцией дам определение сюрреальных чисел и отношения порядка на них, как это делает Джон Конвей в своей книге «On Numbers and Games». Дальше мы покажем, что этот порядок является отношением предпорядка, и опишем все «конечные» сюрреальные числа, т.е. такие, которые получаются на конечных шагах. Затем мы обсудим, как вводятся операции сложения и умножения на сюрреальных числах, относительно которых они формируют упорядоченное Поле (Поле с большой буквы, поскольку сюрреальные числа образуют не множество, а собственный класс). В заключение мы подробно поговорим о шаге \omega в конструкции сюрреальных чисел, а также о том, как в них вкладываются вещественные числа, каким образом там представлены инфинитезимали, и, если останется время, о нормальных формах сюрреальных чисел.

❗Просьба ко всем потенциальным участникам зарегистрироваться на странице семинара. Ссылка для Контур.Толк будет отправлена зарегистрированным участникам накануне заседания.

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 12 марта.
Время проведения семинара 14:00.

‼Если у вас нет пропуска в МФТИ, то нужно заранее написать на почту kudinov.andrey@gmail.com.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Докладчик: Иван Слюсарев

Тема: Модальное расширение двойственной классической паранепротиворечивой логики

Аннотация
Паранепротиворечивые логики - направление неклассических логик, возникшее в 30-40е годы XX века, относительно которых верно, что существуют такие формулы A, B (в языке данных логик), что из {A,¬A} невыводима формула B (минимальный критерий паранепротиворечивости по Г. Присту) Паранепротиворечивыми логиками являются, например, дискуссивные логики (discussive logic) С. Яськовского, минимальная логика И. Йоханссона, бесконечная иерархия логик Н. да Косты, релевантные логики E и R, а также трехзначная логика Г. Приста.

В [1], [2] были введены две паранепротиворечивые логики с унарной логической связкой, двойная итерация которой совпадает по своим дедуктивным свойствам с классическим отрицанием. Данные логики были обозначены как CP (classical paraconsistent logic) и dCP (dual classical paraconsistent logic). Относительно данных логик доказаны основные металогические свойства (полнота и корректность относительно некоторых четырёхзначных семантик, построены секвенциальные исчисления с устранимым сечением и т. д.). Модальные и кванторные расширения данных логик ранее не рассматривались. В докладе будет начато рассмотрение данных расширений путем представления модальной версии логики dCP , будет описана семантика данной логики, аналогичная семантике модальной версии логики BK из [3]; будет доказана полнота и корректность данной логики (модальной версии логики dCP ) относительно этой семантики. Кроме того, предварительно будет дано некоторое историко-логическое введение, связанное с историей развития паранепротиворечивых логик.

Список литературы
[1] Belikov A., Grigoriev O., Zaitsev D. On connegation // Relevance Logics and other Tools for Reasoning. Essays in Honor of J. Michael Dunn. Vol. 46 of Tributes. United States: United States, 2022. P. 73 88.
[2] Kamide, N.(2017). Paraconsistent double negations as classical and intuitionistic negations, Studia Logica 105(6): 1167 1191.
[3] Odintsov, S. P., and H. Wansing, Modal logics with Belnapian truth values, Journal of Applied Non Classical Logics 20(3): 279 301, 2010.

➰ ВК

#матлог #учёба #просеминар

💥В четверг 13 марта на просеминаре по математической логике и информатике будет продолжение темы: "Колмогоровская сложность" (А.А.Оноприенко).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме:
https://news.1rj.ru/str/+8lzSUf8ghLAzMjRi

✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.
⛔К сожалению, сайт кафедры сейчас работает нестабильно, поэтому ориентируйтесь на информацию в группе кафедры ВК или в телеграм-канале!

➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Дата и время: 14.03.2025 в 16:20

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Видео докладов выкладываются на канале:
https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Анна Задаля

Название: Темпоральные логики LTL и CTL.

Аннотация.
Доклад будет посвящён темпоральным логикам LTL и CTL. Мы познакомимся с базовыми определениями, касающимися этой темы. Данные логики являются расширениями классической логики высказываний, полученными путём добавления специальных модальностей. Эти модальности (темпоральные операторы) позволяют формулировать утверждения про факты, истинность которых может меняться с течением времени.
Предварительных знаний не требуется, все определения будут даны в процессе доклада.

➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

17 March 2025, 16.30 CET = 18.30 Moscow time

Ivan Baburin
Universality in Asynchronous Cellular Automata

Abstract. Universality in Asynchronous Cellular Automata Ivan Baburin Kolmogorov Seminar Talk denoscription A cellular automaton is a dynamical system consisting of an infinite array of cells, such that each cell uses a local neighborhood to perform a transition. An asynchronous cellular automaton (ACA) is a modification of cellular automata where every cell can update at is own tempo, without the need for global synchronization. In this talk we survey computational abilities of asynchronous cellular automata and show that—despite their fundamental differences—most asynchronous automata can invariantly “simulate” their synchronous counterparts [1]. To achieve that, we present two characterizations of invariance in asynchronous automata: – An algebraic approach using the notion of commutativity, as introduced by G´acs [2]. – A novel computational approach using flip automata networks, which additionally allows for simpler simulations and can be used to construct some of the smallest universal ACAs [3]. Finally, we discuss the limits of asynchronous computation by demonstrating that for certain automata neither universality nor reliable simulation can be achieved. Further Reading More details can be found in the corresponding paper [3].

References
1. T. Worsch, “Towards intrinsically universal asynchronous ca,” Natural Computing, vol. 12, no. 4, pp. 539–550, 2013.
2. P. Gacs, “Deterministic computations whose history is independent of the order of asynchronous updating,” 2001.
3. I. Baburin, M. Cook, F. Gr¨otschla, A. Plesner, and R. Wattenhofer, “Universality frontier for asynchronous cellular automata,” 2025.

➰ ВК

#матлог #учёба #спецсеминар #не_мехмат #МИАН #ТД

Logic Online Seminar, Monday 16:00 MSK (UTC+3), only Kontur Talk (www.mathnet.ru/eng/conf876)

17.03.2025 семинара не будет

24.03.2025 В.Л. Селиванов, И.В. Смирнов (СПбГУ): Ординальные инварианты гомоморфных предпорядков к-размеченных лесов

В докладе обсуждается комбинаторная сложность хороших частичных порядков (ХЧП). Название является калькой английского термина WPO (Well Partial Order)-theory (часто встречается также название WQO-theory). К сожалению, в русскоязычной литературе нет общепринятого наименования этой теории, в которой изучаются частичные порядки, не имеющие бесконечно убывающих цепей и бесконечных антицепей; такие порядки и называются хорошими. Теория ХЧП имеет богатую историю и приложения к различным разделам математики и информатики.

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

В данной работе вычислены (в терминах ординалов Веблена) ординальные инварианты для конкретных указанных в заглавии ХЧП, введенных П. Хертлингом и нашедших приложения в дескриптивной теории множеств и теории автоматов на бесконечных словах.

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/)

Время: 18 марта 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

А.В. Грефенштейн (МИАН)

Инфинитарные исчисления для первопорядковой логики вероятности с распределением на носителе и её фрагментов

Первопорядковая логика вероятности с распределением на носителе — весьма известный формальный язык для рассуждения о вероятностях в теоретической информатике. В односортной версии этой логики имеются кванторы по элементам носителя, а в двухсортной добавляются кванторы по вещественным числам. Как было показано М. Абади и Дж. Хальперном, при почти всех сигнатурах двухсортная версия имеет как минимум ту же сложность, что и полная арифметика второго порядка, а потому для неё невозможно построить адекватное инфинитарное исчисление; см. также доклад С.О. Сперанского (https://www.mathnet.ru/php/seminars.phtml?presentid=45377&option_lang=rus).

Нас будет интересовать аксиоматизируемость односортной версии вышеупомянутой логики. Первый доклад будет посвящён построению сильно полного инфинитарного исчисления для неё. Здесь «инфинитарность» означает, что наше исчисление будет содержать омега-правила, т.е. правила со счётным числом посылок; однако сами формулы будут конечными. На втором докладе мы рассмотрим различные естественные фрагменты данной логики.

➰ ВК

#матлог #не_мехмат #ВШЭ

В пятницу 21 марта 2025 г. в 18:10 на Математическом семинаре ФКН ВШЭ состоится доклад Павла Соколова на тему "Теория типов и альтернативные основания математики".

Аннотация:

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

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

Место проведения: Покровский бульвар 11, аудитория R305.

Объявление и ссылку для регистрации см. на странице семинара:
https://cs.hse.ru/seminatfkn/

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 19 марта.
Время проведения семинара 14:00.

‼Если у вас нет пропуска в МФТИ, то нужно заранее написать на почту kudinov.andrey@gmail.com.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Докладчик: Константин Ковалев

Тема: Аналоги теоремы Шепердсона для языка с экспонентой

Аннотация: В 1964 году Дж. Шепердсон получил результат, который полностью характеризует модели теории IOpen (фрагмент арифметики Пеано с бескванторной индукцией), а именно, дискретно упорядоченное полукольцо M является моделью IOpen тогда и только тогда, когда соответствующее кольцо является целой частью вещественного замыкания R своего поля частных (то есть, для любого r из R найдется m из M, такое что m = r m + 1). На основе этого результата он построил рекурсивную нестандартную модель IOpen и получил явные результаты о недоказуемости некоторых простых утверждений (например, иррациональности корня из 2). Цель нашей работы – получить аналогичные результаты для расширения арифметического языка экспонентой или функцией возведения в степень. Мы получим результаты, устанавливающие аналогичные соответствия между моделями арифметических теорий IOpen(exp) (бескванторная индукция в языке с экспонентой), IOpen(x^y) (бескванторная индукция в языке с функцией возведения в степень) и IOpen + T_{x^y} (T_{x^y} – некоторые естественные арифметические аксиомы для x^y и неравенство Бернулли) и моделями некоторых фрагментов теории Th(\R, exp) (элементарная теория вещественных чисел со стандартной экспонентой). Основываясь на этих результатах, мы явно построим нестандартные модели (к сожалению, не рекурсивные) IOpen(exp) и IOpen(x^y) и получим аналогичные результаты о недоказуемости. В конце доклада, если останется время, сделаем обзор некоторых дальнейших результатов по этой теме.

➰ ВК

#матлог #учёба #просеминар

💥В четверг 20 марта на просеминаре по математической логике и информатике будет тема "Игры Эренфойхта" (А.А.Оноприенко).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме:
https://news.1rj.ru/str/+8lzSUf8ghLAzMjRi
✅Можно заранее порешать задачи (прикреплены к посту).

✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.

📝 Ehrenfeucht25.pdf

➰ ВК

#матлог #учёба #семинар #не_мехмат #ВШЭ

Уважаемые коллеги, приглашаем вас принять участие в заседании научного семинара "Современные проблемы математической логики" в ВШЭ.

Дата и время: 21.03.2025 в 16:20

Семинар пройдет в формате ZOOM, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Видео докладов выкладываются на канале: https://www.youtube.com/channel/UC_Aq6N03uRgVkEcvS6lJLog

Докладчик: Дудаков С.М. (ТвГУ, ВШЭ)

Название: О теориях алгебр подмножеств и решёток подалгебр

Аннотация.
Одним из способов построения новых алгебр является конструкция алгебры всех или некоторых подмножеств уже имеющейся. Например, для произвольной полугруппы S можно можно построить новую полугруппу exp S, элементами которой будут подмножества S, а операция определена поточечно. В докладе будут рассмотрены теории таких подалгебр exp A, когда исходная алгебра A снабжена бинарной операцией (то есть A — группоид). Будет показано, что при определённых условиях теория exp A позволяет интерпретировать элементарную арифметику (и даже - арифметику второго порядка) или, как минимум, арифметические операции для начального фрагмента натурального ряда. Аналогичный результат будет показан для теории решётки lat A подалгебр алгебры A. Далее, для любого класса K алгебр можно рассмотреть классы exp K и lat K. Первый из них состоит из всех алгебр вида exp A, а второй - из всех решёток вида lat A, когда A берётся из K. Будет показано, что для широко распространённых классов K теории классов exp K и lat K тоже допускают интерпретацию элементарной арифметики. В частности, они неразрешимы и не имеют рекурсивной аксиоматизации.

➰ ВК

#матлог

--------------------------------------------------------------
↪ Логика, лингвистика и формальная философия

21 марта (пятница) в 18.30 состоится очередное заседание исследовательского семинара "Формальная философия".

Тема доклада: Метафизика в философии математики и эпистемологические последствия для доказательства.

Докладчик: Илья Гущин (УрФУ).

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

Ждём вас в кабинете А-117 или в Zoom!

Анонс: https://llfp.hse.ru/announcements/1025647859.html

➰ ВК

#матлог #наука #конференция

Ломоносовские чтения 2025, кафедра математической логики и теории алгоритмов

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

2 апреля 2025 г., среда, 18:30

Главное здание, сектор "А", ауд. 16-04

✅О теореме Гудман-Штрауса. Доклад профессора Верещагина Н. К.
✅О конструктивном исчислении предикатов. Доклад доцента Плиско В. Е.
✅Предикатные модальные логики ограниченной альтернативы. Доклад профессора Шехтмана В. Б.

➰ ВК

#матлог #учёба #спецсеминар

Kolmogorov seminar on complexity (for receive the zoom link, please email nikolay.vereshchagin@gmail.com)

24 March 2025, 16.30 CET = 18.30 Moscow time

Andrei Romashchenko
On the reduction of Kolmogorov complexity by relativization

Alexander Shen asked the following question: let us have a tuple of strings x_1,...,x_n and their Kolmogorov complexities v=(C(x_1),...,C(x_n)). For every string y we get the values of conditional complexities w=(C(x_1|y),...,C(x_n|y)). Which values w of conditional complexities can we obtain? Can we, for example, find a y such that each value C(x_i|y) is (approximately) a half of C(x_i)?

We show that the answer to the last question is positive for n=1 (trivial) and for n=2 (can be proven with Muchnik's theorem on condtional denoscriptions or with Shen's topological argument).

For n=3, the answer is negative: there exists a triple (x_1, x_2, x_3) such that C(x_1)=2n, C(x_2)=2n, C(x_3)=3n, and there is no y such that C(x_1|y)=n, C(x_2|y)=n, C(x_3|y)=1.5n. This negative result follows from combinatorial properties of discrete projective planes over prime fields (Bourgain, Katz, Tao).

➰ ВК

#матлог #учёба #спецсеминар

Семинар «Вероятностные и субструктурные логические системы» (www.mathnet.ru/conf2533) под руководством С.Л. Кузнецова (homepage.mi-ras.ru/~sk/) и С.О. Сперанского (homepage.mi-ras.ru/~speranski/)

Время: 25 марта 2025, начало — в 16:00
Место: МИАН, ком. 303 + Контур.Толк

А.В. Грефенштейн (МИАН)

Инфинитарные исчисления для первопорядковой логики вероятности с распределением на носителе и её фрагментов — 2

На прошлом докладе было представлено инфинитарное исчисление для (односортной версии) первопорядковой логики вероятности с распределением на носителе и изложена схема доказательства соответствующей теоремы о сильной полноте. Настоящий доклад будет посвящён завершению этого доказательства и построению исчислений для естественных фрагментов рассматриваемой логики. В частности, нас будут интересовать линейный и базовый сублинейный фрагменты, а также «чисто вероятностный» фрагмент, в котором всякая классическая формула находится под \mu. В каждом из случаев мы обсудим, как нужно модифицировать исходное исчисление и как при этом меняется конструкция канонической модели и доказательство основной семантической леммы.

➰ ВК

#матлог #не_мехмат #МИАН

Научный семинар кафедры методов современной математики (базовая кафедра МИАН в МФТИ),
25 марта, вторник, 18.00, только онлайн (для получения ссылки пишите учёному секретарю кафедры Оноприенко А.А.)

К. А. Ковалёв. Об аксиоматизации арифметики Бюхи

Аннотация: Арифметикой Бюхи (с основанием p = 2) называется теория натуральных чисел в языке с нулем, функцией последователя, сложением и специальной функцией, обозначаемой V_p, которая число n отображает в наибольшую степень p, делящую n. Хорошо известно, что данная теория является разрешимой, однако неизвестно никакой явной аксиоматизации этой теории (есть некоторые отрицательные результаты, полученные А. Запрягаевым). Цель данной работы состоит в отыскании такой аксиоматизации. Наша аксиоматизация состоит из некоторого конечного числа простых аксиом (похожих на арифметику Робинсона) и схемы аксиом вида ∃x φ(x) → ∃x ≤ n_φ φ(x), где натуральное число n_φ подбирается так, чтобы данная формула была истинна в стандартной модели. Выбор такого числа n_φ опирается на важное свойство арифметики Бюхи, а именно, что любое определимое в рассматриваемом языке множество A является p-автоматным (т. е., множество p-ичных записей элементов A распознаваемо некоторым конечным автоматом).

➰ ВК

#матлог #учёба #просеминар

💥В четверг 27 марта на просеминаре по математической логике и информатике будет продолжение темы "Игры Эренфойхта" (А.А.Оноприенко).

✅Просеминар проходит по четвергам в 16:45-18:20 в аудитории 436 (2 гуманитарный корпус).
✅По просьбам участников создан чат просеминара в телеграме:
https://news.1rj.ru/str/+8lzSUf8ghLAzMjRi
✅Информацию о просеминаре можно найти на странице logic.math.msu.ru/proseminar/.

➰ ВК

#матлог #спецсеминар #не_мехмат #МФТИ

Уважаемые коллеги, приглашаем вас на логический семинар лаборатории им. Манина Высшей школы современной математики МФТИ (ВШМ).
Семинар пройдет в среду 26 марта.
Время проведения семинара 14:00.

‼Если у вас нет пропуска в МФТИ, то нужно заранее написать на почту kudinov.andrey@gmail.com.

Место проведения: МФТИ, Административный корпус, ауд. 322,
Первомайская ул. д.7, Долгопрудный.

К семинару можно подключиться дистанционно, для получения ссылки пишите на почту kudinov.andrey@gmail.com.

Докладчик: Константин Ковалев

Тема: Аналоги теоремы Шепердсона для языка с экспонентой (продолжение доклада предыдущей недели)

➰ ВК

#матлог #новости

⚡Встреча кафедры математической логики и теории алгоритмов со студентами 2 курса состоится 1 апреля в 18:30 в аудитории 1408 (это не шутка, а чистая правда...)

На встрече вы можете больше узнать о научных направлениях кафедры и выбрать своего будущего научного руководителя.

Видеозапись встречи с кафедрой 2022 года можно посмотреть по ссылке vk.com/wall-70743963_1238.

Подробнее о кафедре вы можете узнать по следующим ссылкам.
📎Презентация зав.кафедрой А.Л.Семёнова: https://prezi.com/view/t0oiMzfyh0FkG3UcDz5N/
📎Деятельность кафедры logic.math.msu.ru/about/
📎Направления исследований кафедры logic.math.msu.ru/research/
📎Примеры задач, которые вы можете решать на кафедре logic.math.msu.ru/problems/