Видеотека
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления






Традиционная зимняя сессия МИАН–ПОМИ, посвященная теме «Математическая логика»
25 декабря 2018 г. 15:05–15:40, г. Москва, МИАН, ул. Губкина, д. 8, конференц-зал, 9 этаж
 


$\Pi_1^0$-полнота исчисления Ламбека с итерацией Клини

С. Л. Кузнецов

Математический институт им. В.А. Стеклова Российской академии наук, г. Москва
Видеозаписи:
MP4 861.7 Mb
MP4 391.4 Mb

Количество просмотров:
Эта страница:151
Видеофайлы:17

С. Л. Кузнецов
Фотогалерея


Видео не загружается в Ваш браузер:
  1. Проверьте с Вашим администратором, что из Вашей сети разрешены исходящие соединения на порт 8080
  2. Сообщите администратору портала о данной ошибке

Аннотация: Исчисление Ламбека аксиоматизирует операции умножения (поэлементного приписывания слов), левого и правого делений на формальных языках. Рассматривается естественное расширение исчисления Ламбека операцией итерации (звёздочки) Клини, где звёздочка Клини аксиоматизируется с помощью омега-правила. Доказано, что проблема выводимости в этом исчислении $\Pi_1^0$-полна (в частности, не является алгоритмически разрешимой и даже рекурсивно перечислимой). Результат усиливает ранее известную нижнюю $\Pi_1^0$-оценку для более широкой системы, включающей также операции объединения и пересечения [Бушковский 2007].

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2021