ИСТИНА

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