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

[nikvic]

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

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

В итоге мы доказываем, что для KS не существует нетривиальной монотонной вычислимой оценки снизу.

[max(Im)]

Фух, я вас просто не понимал.

Это мы докажем, что

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

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

Я ж просто запутался. Надо просто сказать, что $f(n)$ не ограничена константой и всё?

[max(Im)]

Но кстати, почему она неограничена, непонятно, может быть всегда будут находиться слова с константной сложностью?
Да, проблемы с пониманием, но может ответ на этот вопрос ответит и на все остальное...

[nikvic]

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

Но кстати, почему она неограничена, непонятно, может быть всегда будут находиться слова с константной сложностью?
Да, проблемы с пониманием, но может ответ на этот вопрос ответит и на все остальное...

Кодов длиной 10 всего 1024...