Колмогоровская сложность

[max(Im)]

Как известно, Колмогоровская сложность не является вычислимой функцией. Попробуем тогда рассмотреть функцию $f(n)$ натурального аргумента $n$ такую, что она возвращает минимальную колмогоровскую сложность натуральных чисел из $[n,+\infty).$ Как показать, что она тоже не вычислима?

Хочется попробовать свести непосредственно к KS. Например, если бы $f(n)$ была бы вычислимой, то можно было найти (вычислить) $KS(n)$. Однако, пока непонятно как... Например, если искать $f(n),f(n+1),\ldots$ последовательно, то можно получить только нижнюю оценку на KS для чисел из некоторого отрезка. Хотя и так понятно, что $KS(n) \geqslant f(n).$

С другой стороны, известно, что если $f(n)$ - нижняя оценка для $KS(n),$ то $f(n)$ если вычислима, то ограничена константой. А как показать, что такого быть не может?

[nikvic]

max(Im) в сообщении #653010 писал(а):

функцию натурального аргумента такую, что она возвращает минимальную колмогоровскую сложность натуральных чисел из Как показать, что она тоже не вычислима?

Через наоборот
Достаточно доказать, что для любой монотонной неограниченной ОРФ найдётся число, КС которого меньше значения этой ОРФ на этом числе.

[max(Im)]

А что такое ОРФ?

-- 02.12.2012, 17:52 --

Общерекурсивные функции? А почему они?

[nikvic]

ОРФ - это всего лишь вычислимая функция, определённая для всех натуральных чисел.
Так что Ваш вопрос - вопрос о существовании надлежащей ОРФ.

[Esp_]

max(Im) в сообщении #653010 писал(а):

Попробуем тогда рассмотреть функцию натурального аргумента такую, что она возвращает минимальную колмогоровскую сложность натуральных чисел из Как показать, что она тоже не вычислима?

Ваша функция - это и есть Колмогоровская сложность, у которой урезан Domain. Нечего здесь доказывать.

[nikvic]

Esp_ в сообщении #653059 писал(а):

max(Im) в сообщении #653010 писал(а):

Попробуем тогда рассмотреть функцию натурального аргумента такую, что она возвращает минимальную колмогоровскую сложность натуральных чисел из Как показать, что она тоже не вычислима?

Ваша функция - это и есть Колмогоровская сложность, у которой урезан Domain. Нечего здесь доказывать.

Нет, у автора - минимум КС по аргументам, не меньшим данного.

[max(Im)]

nikvic в сообщении #653056 писал(а):

ОРФ - это всего лишь вычислимая функция, определённая для всех натуральных чисел.
Так что Ваш вопрос - вопрос о существовании надлежащей ОРФ.

И все-таки, как находить эту ОРФ?

[nikvic]

max(Im) в сообщении #654370 писал(а):

И все-таки, как находить эту ОРФ?

Так нет такой ОРФ... Т.е. функция, в классическом смысле, есть, а вот алгоритм для её вычисления невозможен...

[max(Im)]

А почему нету? Как это доказать?

И все-таки даже так. Нужно доказать вот это?

nikvic в сообщении #653025 писал(а):

max(Im) в сообщении #653010 писал(а):

функцию натурального аргумента такую, что она возвращает минимальную колмогоровскую сложность натуральных чисел из Как показать, что она тоже не вычислима?

Через наоборот
Достаточно доказать, что для любой монотонной неограниченной ОРФ найдётся число, КС которого меньше значения этой ОРФ на этом числе.

Или несуществование какой-то другой ОРФ? Простите за сверхнепонимание, но хочется все-таки разобраться...

[nikvic]

max(Im) в сообщении #654678 писал(а):

А почему нету? Как это доказать?

И все-таки даже так. Нужно доказать вот это?

nikvic в сообщении #653025 писал(а):

max(Im) в сообщении #653010 писал(а):

функцию натурального аргумента такую, что она возвращает минимальную колмогоровскую сложность натуральных чисел из Как показать, что она тоже не вычислима?

Через наоборот
Достаточно доказать, что для любой монотонной неограниченной ОРФ найдётся число, КС которого меньше значения этой ОРФ на этом числе.

Или несуществование какой-то другой ОРФ? Простите за сверхнепонимание, но хочется все-таки разобраться...

Возьмём вычислимую монотонную неогранич. функцию, т.е. монотонную неогранич. ОРФ. Задавшись конкретным у, можем отыскать минимальное х, на котором наша ОРФ больше у. Стал быть, это у может служить кодом для х - и этот код "не лучше" колмоговского (само описание ОРФ - всего лишь константная добавка).

Попробуйте из этой конструкции извлечь понимание.

[max(Im)]

То есть мы таким образом научились вычислять $KS(x)$ с точностью до константы, если предположили вычислимость функции из условия?

[nikvic]

max(Im) в сообщении #654693 писал(а):

То есть мы таким образом научились вычислять $KS(x)$ с точностью до константы, если предположили вычислимость функции из условия?

Никак нет. Вполне возможно, что для точек роста нашей ОРФ есть коды гораздо короче.
По крайней мере для некоторых - факт. Например, для у - степеней двойки. Или сверхстепеней

[max(Im)]

А "наша" ОРФ - это и есть функция из условия, правильно я понимаю?

[nikvic]

max(Im) в сообщении #654708 писал(а):

А "наша" ОРФ - это и есть функция из условия, правильно я понимаю?

Ага.
Та, существование которой опровргаеца

[max(Im)]

Итак, мы предположили, что эта функция (пусть $f$) вычислима. И тогда хотим получить противоречие. Она монотонна, неограниченна, мы берем какое-то $y$ и мы можем найти минимальное $x,$ что $f(x) > y.$ Тогда $y$ может быть кодом для $x$ - оптимальный декомпрессор получает программу для вычисления $f$ и $y$ на вход, то есть $KS(x)$ не больше чем длина $y+\mathrm{const}.$ И что теперь? Можно сказать, что для тех $x,$ в которых нет точек роста, значение $KS$ отличается на не более, чем const, потому что точка роста рядом? Не факт же, что отрезки между ними не растут?

Мы в итоге хотим свести все к тому, что KS вычислима?