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

Семинар "Категориальные грамматики" продолжает работу.
Ближайший семинар состоится 24 октября (24.10.2024).

Начало: 18:30 (24.10.24). Аудитория: 424.

Докладчик: С.Л. Кузнецов
Тема: "Грамматики Ламбека с итерацией Клини"

Аннотация:
Теорема Пентуса утверждает, что категориальные грамматики Ламбека задают в точности контекстно-свободные языки. Выразительные возможности категориальных грамматик сильно возрастают, если к исчислению добавить новые операции. В докладе будут рассмотрены грамматики, основанные на исчислении Ламбека с итерацией Клини в двух вариантах её аксиоматизации: инфинитарном (омега-правило) и индуктивном. Также в рассматриваемых исчислениях присутствуют аддитивные конъюнкция и дизъюнкция. Для первого случая доказано, что соответствующие грамматики порождают в точности все ко-перечислимые языки. Для второго случая получены частичные результаты: грамматики с итерацией, аксиоматизируемой правилом индукции, порождают все разрешимые языки, а также хотя бы один \Sigma^0_1-полный язык. Будут также сформулированы открытые вопросы для дальнейших исследований.

Если вам необходим пропуск в МГУ, необходимо заранее связаться по почте max.startjob@gmail.com

➰ ВК

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

Семинар «Теория доказательств» / Logic Online Seminar (https://www.mathnet.ru/conf876),
28.10.2024, 16:00, ауд. 313 МИАН + Zoom
onsite talk, in Russian | очный доклад на русском языке

Максим Вишникин (МГУ, аспирант, https://www.mathnet.ru/person179526)
Выразительная сила категориальных грамматик с однозначным присвоением категорий

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

В данном докладе рассматривается подкласс категориальных грамматик, в которых каждому символу присвоена единственная категория. Это ограничение снижает выразительную мощность формализма (например, язык a^+ не может быть порожден). Главная цель – глубже понять, сколько выразительной мощности остается. Можно заметить, что даже если каждому символу назначена уникальная категория, это не означает полное отсутствие неоднозначности; последовательность категорий может иметь разные свертки, потому что все еще существует выбор, откуда в последовательности начать сокращение. Это наблюдение используется для доказательства того, что возможно закодировать любую контекстно-свободную грамматику в категориальную грамматику с единственным назначением категорий таким образом, чтобы слово w принадлежало языку контекстно-свободной грамматики тогда и только тогда, когда его кодирование находится в языке категориальной грамматики. Таким образом, в частности, получается усиление классической теоремы Грейбах о самом трудном языке.

Доклад основан на совместной работе с А.С. Охотиным.

🔗 Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar&


➰ ВК

#матлог #учёба #школа

Занятие просеминара 31 октября отменяется. Слушатели приглашаются на осеннюю школу «Логика и формальная философия 2024» https://llfp.hse.ru/announcements/955672040.html.

Все лекции будут проходить в ауд А-307 в корпусе на Старой Басманной (Ст. Басманная ул., д. 21/4, стр. 4).

После входа налево, подняться на третий этаж и дальше по указателям.

По вопросам пропусков пишите Оноприенко А.А.

🔗 Осенняя школа «Логика и формальная философия 2024»


➰ ВК

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

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

МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный

Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16

В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите заранее на почту kudinov.andrey@gmail.com. С собой иметь паспорт.

Заседание пройдет очно без трансляции.

Докладчик: Андрей Кудинов

Название: Топологическое произведение логик S4.1 и S4

Аннотация

За последние несколько десятков лет многие авторы изучали произведения модальных логик, которые определяются семантически: произведения модальных логик L1 и L2 (L1 x L2) определяются, как логика класса произведений L1-шкал и L2-шкал. В работе 2005 ван Бентем с соавторами определили топологическое произведения модальных логик L1 и L2 (L1 x_t L2), как логику класса произведений L1-пространств и L2-пространств. Т.к. для логик расширяющих S4 шкалы Крипке, являются частным случаем топологических пространств, а именно александровскими пространствами, то топологические произведения дают ту же или более слабую логику, чем обычное произведение, основанное на шкалах Крипке. В той же работе 2005 было доказано, что топологическое произведение S4 x_t S4 совпадает с соединением логик S4*S4. В дальнейшем Кремер показал, что топологическое произведение S5 x_t S5 совпадает с Крипке произведением S5 x S5, а S4 x_t S5 совпадает с, так называемым, полупроизведением этих логик (S4 x S5)^EX.

Топологические произведения пока слабо изучены и получено мало результатов о полноте. В нашем докладе мы найдем топологическое произведение S4.1 x_t S4 и покажем, что оно отличается и от соединения, и от произведения, и даже от полупроизведения. S4.1 это расширение логики S4 аксиомой Маккинси: \Box\Diamond p - \Diamond\Box p. Известно, что S4.1 полна относительно слабо-разреженных пространств. Топологическое пространство называется слабо-разреженным, если любое открытое подмножество содержит изолированную точку.
Это первый известный пример произведения, отличающегося и от соединения, и от произведения, и от полупроизведения.

➰ ВК

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

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

Date: Nov 4, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Nikolay Vereshchagin
Title: Goodman-Strauss theorem revisited
The Goodman-Strauss theorem states that for “almost every” substitution, the family of substitution tilings is sophic, that is, it can be defined by local rules for some decoration of the tiles. The proof of this theorem is very complicated and takes 38 pages in [C. Goodman-Strauss, Matching rules and substitution tilings, Ann. of Math. (2) 147 (1998), no. 1, 181–223]. Moreover, the conditions on the substitution that guarantee the sophicity of the family of substitution tilings are not stated explicitly, but are scattered throughout the proof. We propose a version of Goodman-Strauss theorem in which the conditions on the substitution are stated explicitly on two pages, and the proof takes 22 pages. These conditions are quite restrictive. For example, any substitution dealing with triangular tiles does not satisfy them. But we show that, in combination with two simple tricks (taking a sufficiently large power of the substitution and combining small tiles into larger ones), our version of Goodman-Strauss theorem can also prove the sophicity of a family of substitution tilings for “almost every” substitution.

➰ ВК

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

Занятие просеминара 7 ноября отменяется. Слушатели приглашаются на Международную конференцию «Формальная философия 2024».
https://llfp.hse.ru/announcements/968274219.html

Все доклады будут проходить в ауд А-307 в корпусе на Старой Басманной (Ст. Басманная ул., д. 21/4, стр. 4).

После входа налево, подняться на третий этаж и дальше по указателям.

По вопросам пропусков пишите Оноприенко А.А.

🔗 Международная конференция "Формальная философия 2024"


➰ ВК

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

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

МФТИ, радиотехнический корпус, ауд. РТ 113
Институтский пер., 9, стр. 1, Долгопрудный

Ссылка на яндекс-карту с пешим маршрутом от ст. Новодачная:
https://yandex.ru/maps/213/moscow/?ll=37.519439%2C55.929820&mode=routes&rtext=55.924397%2C37.527944~55.929869%2C37.516242&rtt=mt&ruri=ymapsbm1%3A%2F%2Ftransit%2Fstop%3Fid%3Dstation__lh_9601261~ymapsbm1%3A%2F%2Forg%3Foid%3D1109621791&utm_source=share&z=16

В здании пропускной режим, поэтому если у вас нет пропуска в МФТИ, то напишите заранее на почту kudinov.andrey@gmail.com. С собой иметь паспорт.

Заседание пройдет очно без трансляции.

Докладчик: Шехтман В.Б.

Название: Проблема полноты для модальных предикатных логик

Аннотация

Проблема семантической полноты для модальных логик предикатов оказалась очень нетривиальной. Естественная семантика Крипке применима лишь для ограниченного класса логик. Неизвестно, как ее модифицировать, чтобы все логики оказались полными. Однако в других семантиках дело обстоит несколько лучше. В докладе будет дан обзор некоторых результатов о полноте и неполноте модальных предикатных логик в различных семантиках.

➰ ВК

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

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

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

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

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

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

Докладчик: Александр Герасимов

Название: Бесконечнозначная первопорядковая логика Лукасевича: исчисления для поиска вывода и полнота инфинитарного аналитического исчисления для предварённых предложений. Часть вторая

Аннотация.
Бесконечнозначная первопорядковая логика Лукасевича относится к математическим нечётким логикам и служит для формализации приближённых рассуждений. Множество всех общезначимых предложений (и множество всех общезначимых предварённых предложений) этой логики неперечислимо; поэтому для неё не существует полного исчисления с рекурсивным множеством аксиом и конечным числом рекурсивных правил вывода. В докладе мы покажем, как удалось доказать полноту одного инфинитарного аналитического исчисления для предварённых предложений данной логики с помощью построений, полученных при разработке ориентированных на поиск вывода исчислений для рассматриваемой логики.
Доклад основан на статьях:
[1] A.S.Gerasimov, "Repetition-free and infinitary analytic calculi for first-order rational Pavelka logic", Siberian Electronic Mathematical Reports, Vol.17, 2020, pp.1869-1899, https://doi.org/10.33048/semi.2020.17.127;
[2] A.S.Gerasimov, "Comparing calculi for first-order infinite-valued Lukasiewicz logic and first-order rational Pavelka logic", Logic and Logical Philosophy, Vol.32, No.2, 2022, pp.269-318, https://doi.org/10.12775/LLP.2022.030;
а также на некоторых неопубликованных результатах докладчика.
В начале второй части доклада будет изложено основное из его первой части, прошедшей 27.09.2024; так что прослушивание первой части доклада не обязательно для понимания второй.

🔗 Логика в Москве


➰ ВК

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

Ближайший семинар «Категориальные грамматики» состоится 7 ноября (7.11.2024).

Начало: 18:30. Аудитория: 424.

Докладчик: Ф. Д. Холодилов
Тема: «Разложение языков относительно однозначного произведения»

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

➰ ВК

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

Семинар "Вычислимость и неклассические логики" работает по пятницам с 16.45 в аудитории 425 (2гум).

8 ноября 2024 г.
Докладчик: Ю.С.Капустин
Тема: "Функциональная система С_n и её свойства"

В докладе рассматриваются свойства функциональной системы С_n, порождённой обычными теоретико-множественными операциями и индикаторами мощности множеств до n включительно, носитель которой - множество подмножеств множества целых чисел. Будут рассмотрены основные свойства системы, предполные классы системы и представлен критерий относительной полноты в этой системе.

➰ ВК

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

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

Date: Nov 11, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Nikolay Vereshchagin
Title: Goodman-Strauss theorem revisited (continued)

The Goodman-Strauss theorem states that for “almost every” substitution, the family of substitution tilings is sophic, that is, it can be defined by local rules for some decoration of the tiles. The proof of this theorem is very complicated and takes 38 pages in [C. Goodman-Strauss, Matching rules and substitution tilings, Ann. of Math. (2) 147 (1998), no. 1, 181–223]. Moreover, the conditions on the substitution that guarantee the sophicity of the family of substitution tilings are not stated explicitly, but are scattered throughout the proof. We propose a version of Goodman-Strauss theorem in which the conditions on the substitution are stated explicitly on two pages, and the proof takes 22 pages. These conditions are quite restrictive. For example, any substitution dealing with triangular tiles does not satisfy them. But we show that, in combination with two simple tricks (taking a sufficiently large power of the substitution and combining small tiles into larger ones), our version of Goodman-Strauss theorem can also prove the sophicity of a family of substitution tilings for “almost every” substitution.

➰ ВК

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

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

Date: Nov 11, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Nikolay Vereshchagin
Title: Goodman-Strauss theorem revisited (continued)
The Goodman-Strauss theorem states that for “almost every” substitution, the family of substitution tilings is sophic, that is, it can be defined by local rules for some decoration of the tiles. The proof of this theorem is very complicated and takes 38 pages in [C. Goodman-Strauss, Matching rules and substitution tilings, Ann. of Math. (2) 147 (1998), no. 1, 181–223]. Moreover, the conditions on the substitution that guarantee the sophicity of the family of substitution tilings are not stated explicitly, but are scattered throughout the proof. We propose a version of Goodman-Strauss theorem in which the conditions on the substitution are stated explicitly on two pages, and the proof takes 22 pages. These conditions are quite restrictive. For example, any substitution dealing with triangular tiles does not satisfy them. But we show that, in combination with two simple tricks (taking a sufficiently large power of the substitution and combining small tiles into larger ones), our version of Goodman-Strauss theorem can also prove the sophicity of a family of substitution tilings for “almost every” substitution.

➰ ВК

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

На занятии просеминара 14 ноября будет тема "Выразимость предикатов" (Александр Калинин, студент кафедры).
Можно заранее порешать задачи (прикреплены к посту).

❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi

Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.

🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо


📝 opredelimost2024.pdf

➰ ВК

#матлог #учёба #миникурсы

На следующей неделе Степан Львович Кузнецов и Станислав Олегович Сперанский (Математический институт им. В.А. Стеклова РАН) в рамках своего визита в Новосибирский государственный университет прочтут мини-курсы.

Лекции пройдут очно в НГУ, возможно также подключение через Zoom. Для получения ссылки зарегистрируйтесь на странице мини-курсов https://sites.google.com/view/mca-logic

Расписание лекций.
ВНИМАНИЕ! Время везде указано новосибирское, т.е. +4 часа от московского, GMT+7.

В рамках мини-курса С.Л. Кузнецова "Лямбда-исчисление" запланировано три лекции:
(1) 18 ноября (понедельник), 16:20-17:55, ауд. 4140 НГУ,
(2) 19 ноября (вторник), 18:10-19:45, ауд. 4268 НГУ,
(3) 20 ноября (среда), 16:20-17:55, ауд. 4267 НГУ.

В рамках мини-курса С.О. Сперанского "Подход Крипке к формальной теории истины" запланировано три лекции:
(1) 18 ноября (понедельник), 18:10-19:45, ауд. 4140 НГУ,
(2) 19 ноября (вторник), 16:20-17:55, ауд. 4268 НГУ,
(3) 20 ноября (среда), 18:10-19:45, ауд. 4267 НГУ.

---
Аннотация курса С.Л. Кузнецова "Лямбда-исчисление":

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

---
Аннотация курса С.О. Сперанского "Подход Крипке к формальной теории истины":

Пусть L — первопорядковый язык арифметики Пеано, а L' — какое-нибудь его расширение. Из леммы о диагонализации легко следует теорема Тарского о неопределимости истины: если L'-структура M обогащает стандартную модель арифметики, то множество всех (гёделевых номеров) L'-предложений, истинных в M, не определимо в самой M. Стало быть, если L' получается из L добавлением особого одноместного предикатного символа T, и мы хотим интерпретировать T как истинностный предикат для всего L', то T должен принимать как минимум три значения: «истинно», «ложно» и «неопределено», где последнее, в частности, соответствует парадоксу лжеца и ему подобным утверждениям.

Наиболее известный трёхзначный подход к формальной теории истины был предложен Солом Крипке. Здесь роль допустимых (трёхзначных) интерпретаций истинностного предиката T играют наименьшие неподвижные точки специальных монотонных операторов. Основой этих операторов являются различные схемы означиваний, которые соответствуют тем или иным трёхзначным логикам, таким как, например, сильная или слабая логика Клини. Получающиеся в результате наименьшие неподвижные точки могут быть представлены как пределы трансфинитных последовательностей аппроксимирующих интерпретаций.

Цель данного мини-курса — познакомить слушателей с теорией истины по Крипке и её вычислительными аспектами.

🔗 МЦА


➰ ВК

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

Logic Online Seminar (https://www.mathnet.ru/conf876)
Monday 16:00 MSK (UTC+3), Room 313 MIAN + Zoom (online talk)

18.11.2024: no talk

25.11.2024 Johan van Benthem (Stanford, Tsinghua University, University of Amsterdam):
Two Perspectives on Recursion and Induction: Modal Provability Logic and Fixed-Point Logics
Recursion and induction are ubiquitous logical mechanisms. I will compare two styles of dealing with them: one based on well-founded orderings and one on general fixed-point logics, showing that the two are connected in interesting ways. I present some theorems and conjectures to this effect, and if time permits, I will also point out some implications of this theme for discussions of ‘logical constants’ in the philosophy of logic.

🔗 Семинары отдела математической логики "Теория доказательств" и "Logic Online Seminar&


➰ ВК

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

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

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

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

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

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

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

Название: Сложность логики LTL.
Темпоральные логики являются расширениями классической логики высказываний, полученными путём добавления специальных модальностей. Эти модальности, темпоральные операторы, позволяют формулировать утверждения, истинность которых может меняться с течением времени. Простота и выразительность темпоральных логик позволяют использовать их для описания работы различных систем, когда важно уделить внимание последовательности переходов между различными состояниями системы. Логика LTL, также известная как логика линейного времени, впервые была описана в [1].
Данный доклад будет посвящён вычислительной сложности логики линейного времени, а также некоторых её фрагментов.
[1] A. Pnueli. The temporal logic of programs, In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (Providence, RI.). IEEE, New York, 1971, pp. 46-57.

🔗 Логика в Москве


➰ ВК

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

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

Date: Nov 18, 2024. Time: 18:30 (MSK), 16:30 (CET)
Speaker: Nikolay Vereshchagin
Title: Goodman-Strauss theorem revisited (continued)

The Goodman-Strauss theorem states that for “almost every” substitution, the family of substitution tilings is sophic, that is, it can be defined by local rules for some decoration of the tiles. The proof of this theorem is very complicated and takes 38 pages in [C. Goodman-Strauss, Matching rules and substitution tilings, Ann. of Math. (2) 147 (1998), no. 1, 181–223]. Moreover, the conditions on the substitution that guarantee the sophicity of the family of substitution tilings are not stated explicitly, but are scattered throughout the proof. We propose a version of Goodman-Strauss theorem in which the conditions on the substitution are stated explicitly on two pages, and the proof takes 22 pages. These conditions are quite restrictive. For example, any substitution dealing with triangular tiles does not satisfy them. But we show that, in combination with two simple tricks (taking a sufficiently large power of the substitution and combining small tiles into larger ones), our version of Goodman-Strauss theorem can also prove the sophicity of a family of substitution tilings for “almost every” substitution.

➰ ВК

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

На занятии просеминара 21 ноября будет тема "Модальная логика" (Оноприенко А.А.).
Можно заранее порешать задачи (прикреплены к посту).

❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi

Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.

🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо


📝 modal2024.pdf

➰ ВК

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

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

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

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

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

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

Докладчик: Артем Сергеевич Пиманов

Название: Современные модификации онтологических структур времени

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

🔗 Логика в Москве


➰ ВК

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

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

Date: Nov 25, 2024. Time: 18:30 (MSK), 16:30 (CET)
Title: Word combinatorics and approximations of reals
(Following Matthieu Rosenfeld, LIRMM)

Let $\alpha$ be a real number that we try to approximate by rational numbers $m/n$. It can be done with arbitrary precision, but there is a tradeoff between the precision and the denominator. For given denominator $n$ we can obviously make the error smaller than $0.5/n$ (by rounding $\alpha n$); Dirichlet theorem says that for _some_ n the precision could be much better. Let us an approximation $\eps$-good if $|\alpha n -m|\le\eps$. So for every $n$ there is $1/2$-good approximation with denominator $n$ (obvious), and for every $\eps0$ there are infinitely many denominators that allow $\eps$-good approximations (Dirichlet)

What if we allow only some denominators? Then Dirichlet theorem is no more true. For example, if we allow only denominators $1,2,4,8,16,\ldots$, then $1/3$ = $0.0101010101\ldots$ in binary, has no $1/4$-good approximations ($n\alpha$ has fractional part $1/3$ or $2/3$).

Question: assume that we have some other sequence of denominators $n_1,n_2,\ldots$ that is sparse: $n_i2n_{i-1}$, and some $\eps0$. Is it always possible to find some $\alpha$ that has no $\eps$-good approximations, for some $\eps$ and for all the denominators in the sequence? (Note that we cannot take $\alpha$ randomly, since for every $\eps$ the probability of success in $2\eps$ and the union bound does not work for infinitely many denominators.)

People in number theory were interested in this question (and finally proved that the statement is true). Matthieu Rosenfeld noted that we can get a simple proof of this result if we use tools from word combinatorics (e.g., Joe Miller's potential argument for avoiding forbidden strings). This proof will be explained.

➰ ВК

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

На занятии просеминара 28 ноября будет тема "Доказуемо рекурсивные функции и теорема Гёделя" (Беклемишев Л.Д.).

❗По просьбам участников создан чат просеминара в телеграме:
https://t.me/+8lzSUf8ghLAzMjRi

Просеминар проходит по четвергам в 16:45-18:20 в аудитории 424 (2 гуманитарный корпус). Информацию о просеминаре можно найти на странице http://logic.math.msu.ru/proseminar/.

🔗 Просеминар по математической логике и информатике — Кафедра математической логики и теории алгоритмо


➰ ВК