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

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






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


Колмогоровская сложность вычислимых 0-1-последовательностей

Н. К. Верещагинab

a Московский государственный университет имени М. В. Ломоносова, механико-математический факультет
b Факультет компьютерных наук, Национальный исследовательский университет «Высшая школа экономики»
Видеозаписи:
MP4 629.7 Mb
MP4 286.0 Mb

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

Н. К. Верещагин
Фотогалерея


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

Аннотация: Наиболее естественным является определение колмогоровской сложности $K(x)$ вычислимой последовательности $x$, как длины кратчайшей программы, вычисляющей по любому натуральному n первые n членов последовательности. В статье Дюрана, Верещагина и Шеня установлены точные соотношения между этим определением и следующими тремя близкими: (1) длина кратчайшей программы, вычисляющей для всех достаточно больших n первые n членов последовательности, (2) наибольшая условная сложность начала длины n при известном n и (3) верхний предел условных сложностей начал длины n при известном n. Там же доказано, что сложность (2) не меньше чем $K(x)$, релятивизованной оракулом $0'$, а сложность (3) не меньше чем $K(x)$, релятивизованной оракулом $0"$. При этом оставалось неизвестным, верны ли эти неравенства в обратную сторону. В докладе будут даны ответы на эти вопросы.

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