Изменения

# Зафиксируем любой язык программирования. Колмогоровской сложностью слова $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$.

# Колмогоровская сложность конкатенации. Докажите, что $K(xy) \le K(x) + K(y) + O(1)$.

# Колмогоровская сложность пары. Докажите, что $K(\langle x, y\rangle) \le K(x) + K(y) + O(\log |x|)$.