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

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





Для просмотра файлов Вам могут потребоваться






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


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

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

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

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

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


Видео не загружается в Ваш браузер:
  1. Установите Adobe Flash Player    

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

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

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