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

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