Изменения
Нет описания правки
# Что можно сказать про $H(A | A)$?
# Зафиксируем любой язык программирования. Колмогоровской сложностью слова $x$ называется величина $K(x)$ - минимальная длина программы на зафиксированном языке программирования, которая на пустом входе выводит $x$. Обозначим длину слова $x$ как $|x|$. Докажите, что $K(x) \le |x| + c$ для некоторой константы $c$.
# Предложите семейство слов $x_1, x_2, \ldots, x_n, \ldots$, где $|x_i|=i$ строго возрастает и начиная с некоторого $n$ выполнено $K(x_i) < i= o(|x_i|)$.# Предложите семейство слов $x_1, x_2, \ldots, x_n, \ldots$, где $|x_i|=i$ строго возрастает и начиная с некоторого $n$ выполнено $K(x_i) < = o(\log_2 i|x_i|)$.
# Колмогоровская сложность конкатенации. Докажите, что $K(xy) \le K(x) + K(y) + O(1)$.
# Колмогоровская сложность пары. Докажите, что $K(\langle x, y\rangle) \le K(x) + K(y) + O(\log |x|)$.
