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

ВИДЕОТЕКА


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

Колмогоровская сложность вычислимых 0-1-последовательностей Н. К. Верещагин^ab ^a Московский государственный университет имени М. В. Ломоносова, механико-математический факультет ^b Факультет компьютерных наук, Национальный исследовательский университет «Высшая школа экономики»
Аннотация: Наиболее естественным является определение колмогоровской сложности $K(x)$ вычислимой последовательности $x$, как длины кратчайшей программы, вычисляющей по любому натуральному n первые n членов последовательности. В статье Дюрана, Верещагина и Шеня установлены точные соотношения между этим определением и следующими тремя близкими: (1) длина кратчайшей программы, вычисляющей для всех достаточно больших n первые n членов последовательности, (2) наибольшая условная сложность начала длины n при известном n и (3) верхний предел условных сложностей начал длины n при известном n. Там же доказано, что сложность (2) не меньше чем $K(x)$, релятивизованной оракулом $0'$, а сложность (3) не меньше чем $K(x)$, релятивизованной оракулом $0''$. При этом оставалось неизвестным, верны ли эти неравенства в обратную сторону. В докладе будут даны ответы на эти вопросы.